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 A₁,A₂,¼,A_n denote finite sets and let a_i (1 £ i £ n) denote the sum of the cardinalities of the intersections of the sets taken i at a time. Write down, and prove, the Inclusion-Exclusion Formula giving |A₁ÈA₂ȼÈA_n| in terms of the a_i.

(b) Two integers are said to be relatively prime if they have no common factors except for the factor 1. How many positive integers less than 500 are relatively prime to both 12 and 21?

(c) How many permutations are there of the digits 1,2,¼,9 in which none of the patterns 12, 34, 56 appears?

3. (a) Use generating functions to find the number of ways in which a sum of 20 can be obtained when 8 distinct dice are rolled.

(b) Let S(n,k) denote the number of partitions of an n-set into k parts. Show that

• S(n,1) = S(n,n) = 1;
• S(n,k) = S(n-1,k-1)+kS(n-1,k);
• S(n,2) = 2^n-1-1     (n ³ 2).

[Hint: For (iii) use induction on n.]

4. (a) Let p(n) denote the number of partitions of the positive integer n and let p(n|P) denote the number of partitions of n having property P. Write down the generating functions of each of the following

• p(n);
• p(n| all parts are distinct);
• p(n| all parts are odd);
• p(n| no part appears more than twice);
• p(n| no part is a multiple of 3).

Show that

(b) Using Ferrers diagrams, show that

• The number of partitions of 3n into n parts is equal to the number of partitions of 2n into at most n parts.
• [(ii)] The number of partitions of n into exactly m parts is equal to the number of partitions of n such that the largest part equals m.