MAT 344 (1999S) Test #2: Solutions

[30] 1. How many ways are there to buy 25 pens if there are 10 different colours, at most 6 pens of each colour are available, and at least one pen of each colour must appear?

Answer: This is equivalent to the number of integer solutions to e₁ + e₂ + ...e₁₀ = r where 1 <= e_i <= 6. The generating function which models this is

g(x) = ( x + x² + x³ + x⁴ + x⁵ + x⁶ ) ¹⁰

and we are interested in its x²⁵ coefficient

[ x²⁵ ] g(x)
     = [ x²⁵ ] ( x + x² + x³ + x⁴ + x⁵ + x⁶ ) ¹⁰
     = [ x²⁵ ] x¹⁰ ( 1 + x + x² + x³ + x⁴ + x⁵ ) ¹⁰
     = [ x¹⁵ ] ( 1 + x + x² + x³ + x⁴ + x⁵ ) ¹⁰
     = [ x¹⁵ ] ( 1 - x⁶ ) ¹⁰ / ( 1 - x ) ¹⁰
     = [ x¹⁵ ] ( C(10,0) x⁰ - C(10,1) x⁶ + C(10,2) x¹² - ... ) ( C(9,0) x⁰ + C(10,1) x + C(11,2) x² + ... )
     = C(10,0) C(24,15) - C(10,1) C(18,9) + C(10,2) C(12,3)
     = 811,404

[30] 2. How many ways are there to distribute 10 different sweaters among 3 people, A, B and C, so that each person gets at least sweater? In how many of these distributions will person A get 4 sweaters?

Answer: There are 3¹⁰ ways in which zero or more people get none, 3*2¹⁰ ways in which one or more get none, and 3*1¹⁰ in which two get none. There are therefore 3¹⁰ - 3*2¹⁰ + 3*1¹⁰ = 55,980 ways in which each person gets at least one sweater.

If you would rather do this with exponential generating functions, then you need to calculate

[ x¹⁰/10! ] ( e^x - 1 ) ³ = [ x¹⁰/10! ] ( e^3x - 3e^2x + 3e^x - 1 )

which works out to the same value.

For the second part, there are C(10,4) ways to choose which sweaters A gets, and ( 2⁶ - 2 ) ways in which to decide how to split the rest between B and C. The total number of distributions is therefore C(10,4) * ( 2⁶ - 2 ) = 18,600.

(Still under construction)