Page 573 - Discrete Mathematics and Its Applications

552 8 / Advanced Counting Techniques

b) What are a 1 ,b 1 ,c 1 , and d 1 ? that is, p o (n) = p d (n).[Hint: Show that the generating
functions for p o (n) and p d (n) are equal.]
c) Use parts (a) and (b) to find a 3 ,b 3 ,c 3 , and d 3 .
∗∗ 56. (Requires calculus) Use the generating function of p(n)
d) Use the recurrence relations in part (a), together with C n
√
the initial conditions in part (b), to set up three equa- to show that p(n) ≤ e for some constant C. [Hardy
√
√
√
tions relating the generating functions A(x), B(x), and Ramanujan showed that p(n) ∼ e π 2/3 n /(4 3n),
and C(x) for the sequences {a n }, {b n }, and {c n }, re- which means that the ratio of p(n) and the right-hand side
spectively. approaches 1 as n approaches infinity.]
Suppose that X is a random variable on a sample space S such
e) Solve the system of equations from part (d) to get
that X(s) is a nonnegative integer for all s ∈ S. The proba-
explicit formulae for A(x), B(x), and C(x) and use
bility generating function for X is
these to get explicit formulae for a n , b n , c n , and d n .
∞
Generating functions are useful in studying the number of k
different types of partitions of an integer n.A partition of G X (x) = p(X(s) = k)x .
a positive integer is a way to write this integer as the sum k = 0
of positive integers where repetition is allowed and the order 57. (Requires calculus) Show that if G X is the probability
of the integers in the sum does not matter. For example, the generating function for a random variable X such that
partitions of 5 (with no restrictions) are 1 + 1 + 1 + 1 + 1, X(s) is a nonnegative integer for all s ∈ S, then
1 + 1 + 1 + 2, 1 + 1 + 3, 1 + 2 + 2, 1 + 4, 2 + 3, and 5. a) G X (1) = 1. b) E(X) = G (1).

Exercises 51–56 illustrate some of these uses. 2 X

c) V(X) = G (1) + G (1) − G (1) .

X
X
X
51. Show that the coefficient p(n) of x n in the formal 58. Let X be the random variable whose value is n if the
2
3
power series expansion of 1/((1−x)(1−x )(1−x ) ··· ) first success occurs on the nth trial when independent
equals the number of partitions of n. Bernoulli trials are performed, each with probability of
52. Show that the coefficient p o (n) of x n in the formal success p.
3
5
power series expansion of 1/((1−x)(1−x )(1−x ) ··· ) a) Find a closed formula for the probability generating
equals the number of partitions of n into odd integers, that function G X .
is,thenumberofwaystowritenasthesumofoddpositive b) Find the expected value and the variance of X using
integers, where the order does not matter and repetitions Exercise 57 and the closed form for the probability
are allowed. generating function found in part (a).
n
53. Show that the coefficient p d (n) of x in the formal power 59. Let m be a positive integer. Let X m be the random vari-
3
2
series expansion of (1 + x)(1 + x )(1 + x ) ··· equals able whose value is n if the mth success occurs on the
the number of partitions of n into distinct parts, that is, (n + m)th trial when independent Bernoulli trials are per-
the number of ways to write n as the sum of positive in- formed, each with probability of success p.
tegers, where the order does not matter but no repetitions a) Using Exercise 32 in the Supplementary Exercises
are allowed. of Chapter 7, show that the probability generating
m
m
(x) = p /(1 − qx) ,
function G X m is given by G X m
54. Find p o (n), the number of partitions of n into odd parts where q = 1 − p.
with repetitions allowed, and p d (n), the number of par- b) Find the expected value and the variance of X m using
titions of n into distinct parts, for 1 ≤ n ≤ 8, by writing Exercise 57 and the closed form for the probability
each partition of each type for each integer. generating function in part (a).
55. Show that if n is a positive integer, then the number of 60. ShowthatifX andY areindependentrandomvariableson
partitions of n into distinct parts equals the number a sample space S such that X(s) and Y(s) are nonnegative
of partitions of n into odd parts with repetitions allowed; integers for all s ∈ S, then G X+Y (x) = G X (x)G Y (x).
8.5 Inclusion–Exclusion
Introduction
A discrete mathematics class contains 30 women and 50 sophomores. How many students
in the class are either women or sophomores? This question cannot be answered unless more
informationisprovided.Addingthenumberofwomenintheclassandthenumberofsophomores
probably does not give the correct answer, because women sophomores are counted twice. This
observation shows that the number of students in the class that are either sophomores or women is
the sum of the number of women and the number of sophomores in the class minus the number
of women sophomores. A technique for solving such counting problems was introduced in