1.  In this question your answers should be given in the final form as natural numbers.

Six different toys and five identical balloons are all handed out to a group of four children.

(a)  What is the number of possible distributions if every child gets at least one

toy?

Solution:    The number of distributions of the toys is the number of sur- jective functions from a set of cardinality 6 to a set of cardinality 4 and so equals 4! S(6, 4) = 24 . 65 = 1560.  The number of distributions of the bal- loons is the number of unordered selections of 5 things from 4 possibilities

with repetition allowed and so equals  l4 +5(5) _ 1、  =  l 、3(8)  = 56.  By the

Product Principle, the total number of distributions is 1560 . 56 = 87360.

(b)  What is the number of possible distributions if every child gets at least one

balloon and those children who get only one balloon should get at least one toy?

Solution:     First give one balloon to each child.  The remaining balloon and the toys should be distributed in such a way that no child misses out with these seven different objects.   Hence, the number of distributions is 4! S(7, 4) = 24 . 350 = 8400.

A few other ways to get this number are as follows. The remaining balloon can be given to any of the four children. The toys should then be distributed in such a way that each of the other three children gets at least one toy.     Now calculate the number of distributions such that at least one of the three children misses out.  By the Inclusion-Exclusion Principle, this number is found by 36  + 36  + 36  _ 26  _ 26  _ 26  + 1 =  1996.   Hence the number of distributions where each of the three children gets a toy equals 46 _ 1996 = 2100.   Therefore, by the Product Principle, the total number of possible distributions is 4 . 2100 = 8400.

Alternatively, there are  l  、k(6)  ways to choose k toys and there are 3! S(k, 3)

ways to distribute them among those three children. Hence, the total number of possible distributions is counted by

4 k 奁(6)3  l  、k(6) 3! S(k,3) = 24 (20 + 15 . 6 + 6 . 25 + 90) = 8400.

Yet another way to count is to note that if no child misses out with the toys, then there are 4 ways to distribute the balloons yielding 4 . 4! S(6, 4) = 4 . 24 . 65 = 6240 distributions.  If only one child misses out with the toys,

then this child should get two balloons.  This yields another 4 . 3! S(6, 3) = 4 . 6 . 90 = 2160 distributions so that the total number is 6240+2160 = 8400.

2.  Let n be a natural number and x be a variable. Both sides of the identity

(1 + x)4n  = (1 + 2x + x2 )2n  are polynomials in x whose coefficients can be found from the Binomial and Multinomial Theorems, respectively. By equating suitable coefficients or otherwise, prove the identity

m 4n一m  l 2(2)m(n)、  l m(2m)、= l2(4)n(n)、.

Solution:   By the Multinomial Theorem,

(1 + 2x + x2 )2n  = k,l,m∈N,  k←l←m奁2n  、(2x)l x2m .

Take the coefficient of x2n .  We must have l + 2m = 2n so that l = 2n _ 2m and k = m. Therefore, this coefficient can be written as

m 22n一2m lm, 2n 2n_2m, m、= m 4n一m l 2(2)m(n)、l m(2m)、.

On the other hand, by the Binomial Theorem, the coefficient of x2n  in the polyno-

mial (1 + x)4n  equals  l2(4)n(n)、 which yields the required identity.

3.     (a)  Suppose there are n > 8 students, each of whom must be assigned to one of

4 labs on Monday, Tuesday, Wednesday and Thursday. How many ways are there to assign the students to the labs with the constraint that every lab must have at least two students? Write your answer in terms of the Stirling numbers.

Solution:   The number of the assignations with the condition that every lab has at least one student is 4!S(n, 4). We need to subtract from this number the number of assignations in which at least one of the labs gets exactly one student. Let A1  be the set of all assignations in which the Monday lab gets exactly one student (and all the others get at least one), and similarly define A2 , A3  and A4 . Then nAi n = n 3! S(n _ 1, 3) for all i, while nAi ∩ Aj n = n (n _ 1) 2! S(n _ 2, 2) for all i < j, and nAi  ∩ Aj  ∩ Ak n = n(n _ 1)(n _ 2) for all i < j < k . Since nA1 ∩ A2 ∩ A3 ∩ A4 n = 0, by the Inclusion-Exclusion Principle, the answer to the question is

4! S(n, 4) _ 4 n 3!S(n _ 1, 3)

+ l 、2(4) n (n _ 1) 2! S(n _ 2, 2) _ l 、3(4) n(n _ 1)(n _ 2)

which equals

24 S(n, 4) _ 24 n S(n _ 1, 3) + 12 n(n _ 1) S(n _ 2, 2) _ 4 n(n _ 1)(n _ 2).