Section 5.1 Relations
355
62. From Exercise 61, you might be looking for a closed-form formula giving the value of P n . Although Bell
numbers have been extensively studied, no closed-form formula has been found. Bell numbers can be
computed via a recurrence relation. Let P 0 have the value 1. Prove that for n ≥ 1,
P n = ∙
n−1
k=0
C(n − 1, k)P k
(Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member
of a set with n elements. In each term of the sum, n − k represents the size of the partition block that
contains x.)
63. Use the formula of Exercise 62 to compute P 1 , P 2 , P 3 , and P 4 , and compare your answers to those in
Exercise 61.
64. Use the formula of Exercise 62 to compute P 5 and P 6 .
65. Let S(n, k) denote the number of ways to partition a set of n elements into k blocks. The numbers S(n, k)
are called Stirling numbers.
a. Find S(3, 2).
b. Find S(4, 2).
66. Prove that for all n ≥ 1, S(n, k) satisfies the recurrence relation
S(n, 1) = 1
S(n, n) = 1
S(n + 1, k + 1) = S(n, k) + (k + 1)S(n, k + 1) for 1 ≤ k ≤ n
(Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member of
a set with n + 1 elements, and put x aside. Partition the remaining set of n elements. A partition of the
original set could be obtained either by adding 5x6 as a separate block or by putting x in one of the existing
blocks.)
67. Use the formula of Exercise 66 to rework Exercise 65.
68. The recurrence relation of Exercise 66 is similar to Pascal’s formula, Equation (1) of Section 4.5. Use this
relation to compute the numeric values in the first five rows of Stirling’s triangle, which begins
S(1, 1)
S(2, 1) S(2, 2)
S(2, 1) S(3, 2) S(3, 3)
(
69. Prove that
P n = ∙
n
k=1
S(n, k)
70. Use the formula of Exercise 69 and Stirling’s triangle (Exercise 68) to compute P 1 , P 2 , P 3 , and P 4 .
71. Find the number of ways to distribute 4 different-colored marbles among 3 identical containers so that no
container is empty.
72. Find the number of ways in which 5 different jobs can be assigned to 3 identical processors so that each
processor gets at least 1 job.
355
62. From Exercise 61, you might be looking for a closed-form formula giving the value of P n . Although Bell
numbers have been extensively studied, no closed-form formula has been found. Bell numbers can be
computed via a recurrence relation. Let P 0 have the value 1. Prove that for n ≥ 1,
P n = ∙
n−1
k=0
C(n − 1, k)P k
(Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member
of a set with n elements. In each term of the sum, n − k represents the size of the partition block that
contains x.)
63. Use the formula of Exercise 62 to compute P 1 , P 2 , P 3 , and P 4 , and compare your answers to those in
Exercise 61.
64. Use the formula of Exercise 62 to compute P 5 and P 6 .
65. Let S(n, k) denote the number of ways to partition a set of n elements into k blocks. The numbers S(n, k)
are called Stirling numbers.
a. Find S(3, 2).
b. Find S(4, 2).
66. Prove that for all n ≥ 1, S(n, k) satisfies the recurrence relation
S(n, 1) = 1
S(n, n) = 1
S(n + 1, k + 1) = S(n, k) + (k + 1)S(n, k + 1) for 1 ≤ k ≤ n
(Hint: Use a combinatorial proof instead of an inductive proof. Let x be a fixed but arbitrary member of
a set with n + 1 elements, and put x aside. Partition the remaining set of n elements. A partition of the
original set could be obtained either by adding 5x6 as a separate block or by putting x in one of the existing
blocks.)
67. Use the formula of Exercise 66 to rework Exercise 65.
68. The recurrence relation of Exercise 66 is similar to Pascal’s formula, Equation (1) of Section 4.5. Use this
relation to compute the numeric values in the first five rows of Stirling’s triangle, which begins
S(1, 1)
S(2, 1) S(2, 2)
S(2, 1) S(3, 2) S(3, 3)
(
69. Prove that
P n = ∙
n
k=1
S(n, k)
70. Use the formula of Exercise 69 and Stirling’s triangle (Exercise 68) to compute P 1 , P 2 , P 3 , and P 4 .
71. Find the number of ways to distribute 4 different-colored marbles among 3 identical containers so that no
container is empty.
72. Find the number of ways in which 5 different jobs can be assigned to 3 identical processors so that each
processor gets at least 1 job.