Answer THREE questions

(b) Let S(n,k) denote the number of partitions of an n-set into k parts. Write down, without proof, the number of surjections from an n-set to a k-set in terms of n, k and S(n,k).

(c) Show that

(d) Each of twenty rooms contains five persons. Thirty persons are to be selected from these hundred with the condition that at least one person from each room is to be selected. Show that the number of ways in which this can be done is

2. (a) An experiment consists in tossing a coin until two heads appear (the two heads need not be consecutive). At the second head the experiment stops. Let a_n, (n ³ 2) be the number of possible experiments that end on the nth toss or sooner.

Find a recurrence relation for a_n and hence obtain the value of a_n.

[Hint: Consider separately those experiments that end exactly at the nth toss and those that end earlier.]

(b) Show that the number of partitions of n is equal to the number of partitions of 2n into exactly n parts and it is also equal to the number of partitions of 2n with the largest part equal to n.

3. Solve the recurrence relation

4. (a) Write down (without proof) the coefficient of x^k in the power series expansion of (1-x)ⁿ.

(b) Ten letters are to be chosen (order not important) using the letters a,b,c. In how many ways can this be done if:

• Each of the three letters can be chosen an unlimited number of times?
• The letter a must be chosen at least once (but otherwise an unlimited number of times), the letter b cannot be chosen more than five times, and the letter c can be chosen an unlimited number of times?

(c) Let g(x) = å_{r = 0}^¥ a_rx^r and f(x) = å_{r = 0}^k x^r. Write down the coefficient of x^k in the product f(x)g(x) in terms of the coefficients of g(x).

(d) Write down the generating functions for:

• p(n), the number of partitions of the integer n;
• p(0)+p(1)+...+p(n), the number of partitions that add up to at most n;
• The number of partitions that add up to an even number at most 2n.