MA141 Discrete Methods
MCU202 Combinatorial Theory
MA141 (Faculty of Science) students:
Answer THREE questions. Time allowed TWO hours.
MCU202 (I.T. Board) students:
Answer TWO questions. Time allowed ONE AND A HALF hours.
|
2.
(a) 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
|
(b) How many integers are there in the range 1 to 999 (inclusive)
which are not divisible by any of 2, 5 or 23?
(c) 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).
(d) Show that
|
Continued next page
3. (a) [In this question, p(n|P) denotes the number of partitions
of the positive integer n having property P.]
Write down the generating function for p(n), the number of partitions of 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) Show that the number of partitions of n is equal to the number of
partitions of 2n with the largest part equal to n.
Show also that the number of partitions of n is equal to the number of partitions of 2n into exactly n parts.
[Hint: For part (b) consider Ferrers Diagrams.]
4. (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 an, (n ³ 2) be the number of possible experiments that
end on the nth toss or sooner.
Find a recurrence relation for an and hence obtain the value of an.
[Hint: Consider separately those experiments that end exactly at the nth toss and those that end earlier.]
(b) Write down the coefficient of xk in the expansion
of (1-x)-n in ascending powers of x.
Find the coefficients of x20 in each of the following products: