MA141 Discrete Methods September 2000

MCU202 Discrete Methods

MA141 (Faculties of Science, Education, Arts) students:

Answer THREE questions. Time allowed TWO hours.

MCU202 (I.T. Board) students:

Answer TWO questions. Time allowed ONE AND A HALF hours.

(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 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) Find the number of five-letter words that use letters from the set {a,b,g} and such that none of these three letters is missing from any word.

(c) How many permutations are there of the digits 1,2,¼,100 in which no odd number appears in its natural position?

[In (c) you may give your answer as a summation of terms involving factorials.]

3. Solve the following recurrence relation

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) Solve the following recurrence relation