2000 MAT344S Test #2

1. Suppose that a fair coin is tossed 15 times, and that 6 tails occur. Find the probability that no run of 5 (or more) consecutive heads occurs.

There are C(15,6) equally probable ways to get 6 of 15 tails. We can model the problem of arranging the heads to avoid consecutivity as that of placing 0-4 nondistinct heads in each of 7 distinct boxes that are separated by tails. There are then C(7,1) ways of choosing which box gets at least five heads and C(4+7-1,4) ways of distributing the remaining four heads. The probability is therefore (C(15,6)-C(7,1)*C(4+7-1,4))/C(15,6) = 3535/5005 or about 71%.

Alternately, you can calculate the numerator as C(15,6)-C(11;6,4,1)+C(10;6,3,1). Figuring out why this is so is left up to you.

You can also use ordinary generating functions to do the same. We want [x⁹](1-x⁵)⁷(1-x)^-7, which we can calculate using two applications of the Binomial Theorem.

2. Find the number of integer solutions of the equation 2x + 3y + 7z = 84, where 0 <= z <= 3 <= y <= 8 <= x. (Hint: express your answer in terms of a coefficient in a particular generating function.)

This is equivalent to placing 84 nondistinct balls into three distinct boxes, with the restrictions that the number of balls in box #1 is divisible by two and at least 8, the number of balls in box #2 is 9, 12, 15, 18, 21 or 24, and the number of balls in box #3 is 1, 7, 14 or 21. This is the same as the coefficient of x⁸⁴ in (1 + x⁷ + x¹⁴ + x²¹) (x⁹ + x¹² + x¹⁵ + x¹⁸ + x²¹ + x²⁴) (x⁸ + x¹⁰ + x¹² + ...) which is the same as [x⁵⁹] ((1-x²⁸) (1-x¹⁸)) / ((1-x⁷) (1-x³) (1-x²)). This is an acceptable form for the final answer. You may also expand this to get the actual numerical value 12.

3. Let m and n be given positive integers, with m <= n. Using a generating function, find an expression for the number of ways to distribute r distinct objects into n different boxes, with exactly m non-empty boxes.

There are C(n,m) ways of choosing which m of the n are non-empty. The number of ways of distributing r distinct objects into m distinct non-empty boxes is the same as the number of codewords of length r made from an alphabet of size m, with each letter used at least once. Using exponential generating functions, this is the same as the coefficient [x^r/r!] (e^x-1)^m and it's also the same as m! S(r,m) where S(r,m) is a Stirling number of the second kind. The final answer is therefore n^m S(r,m).

You can also solve this using ordinary generating functions, but it's a lot messier. Assume first that the boxes are identical and ignore the choice of m from n, as we can multiply by C(n,m)*m! at the end. For m=1, we would want [x^r](x/1-x). For m=2, we want to place from 1 to r-1 objects in the first m-1 boxes, and have respectively 2^r-2 down to 2⁰ choices for the rest, giving the ordinary generating function coefficient [x^r] x²/((1-x)(1-2x)). Continuing on similarly we obtain for general m the ordinary generating function coefficient [x^r] x^m / ((1-x) (1-2x) ... (1-mx)), which we immediately recognize as the Stirling number of the second kind S(r,m). This gives the same final answer as before, n^m S(r,m).

4. How many ways are there to select 300 candies from seven types if each type comes in a box of 20 (and only a whole box can be taken, you can't break up a box) and if at least one but not more than five boxes of each type may be chosen.

Model this as the number of integer solutions to e₁ + e₂ + e₃ + e₄ + e₅ + e₆ + e₇ = 15 with 1 <= e_i <= 5. This is the ordinary generating function coefficient [x¹⁵] (x + x² + x³ + x⁴ + x⁵)⁷ = [x⁸] (1-x⁵)⁷ (1-x)^-7 = C(14,8) - C(7,1)*C(9,3) = 2415.

You should also be able to get C(14,8)-C(7,1)*C(9,3) directly, without using generating functions.