Section 4.6 Probability
301
This exercise provides an alternate to the inductive proof given in Section 4.3 of the principle of inclusion
and exclusion. Equation (1) is correct if for any x in {A 1 c c c A n }, x is counted exactly once by the right
side of the equation.
a. Suppose x is an element of k of the n sets {A 1 , … , A n }. Let B equal the set of A i s of which x is a member.
Then x is counted once in the right side of (1) for each of the intersections that include only sets from
B. Show that in the intersections of m sets from {A 1 , … , A n }, 1 ≤ m ≤ k, there are C(k, m) that include
only sets from B.
b. Using the result of part (a), write a sum of terms that represents the number of times x is counted in the
right side of (1).
c. Use Exercise 17 to show that this sum of terms equals 1.
24. Pascal’s triangle has many interesting properties. If you follow diagonal paths through the triangle and
sum the values on each path, the result is the Fibonacci sequence (see (a) below). The values along the
diagonals are easier to understand if the rows of the triangle are written one row per line with each row
beginning one position to the right of the previous row (see (b) below). Then the diagonals are the table
columns.
1
1 1
1
1
1
1 5 10 10
. . .
5 1
4
6 4 1
3 3 1
2 1
1
1 2 3
5
8
6
7
8
5
4
3
2
1
0
0
1
1
1
1
2
1
2
3
4
5
6
7
8
1
1
2
3
5
8
13 21 34
1
1
3
1
3
1
4
1
6
4
1
5
10 10
1
6
15
1
7
1
a. Prove that the values in column n, n ≥ 2, read from bottom to top, are given by the expression
∙
n∙2
k=0
C(n − k, k) if n is even and by ∙
(n−1)∙2
k=0
C(n − k, k) if n is odd.
b. Prove that the sum of the values in column n, n ≥ 0, equals F(n + 1).
S e c t i o n 4 . 6 Probabilit y
introduction to finite Probability
Probability is an extension of the combinatorics (counting) ideas we have already
been using. If some action can produce Y different outcomes and X of those Y
outcomes are of special interest, we may want to know how likely it is that one of
the X outcomes will occur. Probability had its beginnings in gaming or gambling,
and we have pretty good intuition for simple cases.
(a)
(b)
301
This exercise provides an alternate to the inductive proof given in Section 4.3 of the principle of inclusion
and exclusion. Equation (1) is correct if for any x in {A 1 c c c A n }, x is counted exactly once by the right
side of the equation.
a. Suppose x is an element of k of the n sets {A 1 , … , A n }. Let B equal the set of A i s of which x is a member.
Then x is counted once in the right side of (1) for each of the intersections that include only sets from
B. Show that in the intersections of m sets from {A 1 , … , A n }, 1 ≤ m ≤ k, there are C(k, m) that include
only sets from B.
b. Using the result of part (a), write a sum of terms that represents the number of times x is counted in the
right side of (1).
c. Use Exercise 17 to show that this sum of terms equals 1.
24. Pascal’s triangle has many interesting properties. If you follow diagonal paths through the triangle and
sum the values on each path, the result is the Fibonacci sequence (see (a) below). The values along the
diagonals are easier to understand if the rows of the triangle are written one row per line with each row
beginning one position to the right of the previous row (see (b) below). Then the diagonals are the table
columns.
1
1 1
1
1
1
1 5 10 10
. . .
5 1
4
6 4 1
3 3 1
2 1
1
1 2 3
5
8
6
7
8
5
4
3
2
1
0
0
1
1
1
1
2
1
2
3
4
5
6
7
8
1
1
2
3
5
8
13 21 34
1
1
3
1
3
1
4
1
6
4
1
5
10 10
1
6
15
1
7
1
a. Prove that the values in column n, n ≥ 2, read from bottom to top, are given by the expression
∙
n∙2
k=0
C(n − k, k) if n is even and by ∙
(n−1)∙2
k=0
C(n − k, k) if n is odd.
b. Prove that the sum of the values in column n, n ≥ 0, equals F(n + 1).
S e c t i o n 4 . 6 Probabilit y
introduction to finite Probability
Probability is an extension of the combinatorics (counting) ideas we have already
been using. If some action can produce Y different outcomes and X of those Y
outcomes are of special interest, we may want to know how likely it is that one of
the X outcomes will occur. Probability had its beginnings in gaming or gambling,
and we have pretty good intuition for simple cases.
(a)
(b)