Answer TWO questions
(b) Let S(n,k) denote the number of ways of partitioning an n-set
into k parts. Prove that
|
(c) In how many ways can six identical balls be distributed amongst four
distinguishable boxes so that no box is empty?
(d) In how many ways can six distinguishable balls be distributed amongst
four distinguishable boxes so that no box is empty?
2. (a) Let p(n) denote the number of partitions of the positive
integer n and let p(n|P) denote the number of partitions
satisfying a given property P. Write down the generating function
for p(n).
Let k ³ 1 be fixed, let P1 be the property ``No part in the partition appears more than k times'' and let P2 be the property ``No part in the partition is divisible by k+1''. Prove that p(n|P1) = p(n|P2).
(b) Let A1,A2,...,An be finite sets, and let ai denote
the sum of the cardinalities of the intersections of the sets taken i
at a time. Prove that
|
Let N = {1,2,...,2n}. Show that the number of permutations f on N with the property f(2i) ¹ 2i, 1 £ i £ n is given by
|
3. (a) Solve the following recurrence relation
|
(b) Solve the following recurrence relation
|