UNIVERSITY OF MALTA

UNIVERSITY OF MALTA UNIVERSITY OF MALTA

FACULTY OF SCIENCE / I.T. BOARD OF STUDIES

Department of Mathematics

B.Sc.(Hons) Year I / B.Sc.(Hons) I.T. Year II

January Session 1999

MA141 Discrete Methods 25 January 1999

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.

1. (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) How many permutations are there of the digits 1,2,¼,9 in which none of the patterns 23, 56, 89 appears?

[You may leave factorials in your answers but any results on derangements must be derived and written out in full.]

2. (a) Solve the following recurrence relation

a_n = n² a_n-1 + [(n+1)!]² (n ³ 1)

given that a₀ = 1.

[You may use the fact that å₁ⁿ i² = n(n+1)(2n+1)/6.]

(b) Solve the recurrence relation

a_n-5a_n-1+6a_n-2 = 3ⁿ (n ³ 2)

given that a₀ = a₁ = 0.

3. (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

p(n| all parts are distinct) = p(n| all parts are odd)

and

p(n| no part appears more than twice) = p(n| no part is a multiple of 3).

[You may need to use 1+y = (1-y²)/(1-y) and 1+y+y² = (1-y³)/(1-y).]

(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.

4. (a) Let S(n,k) denote the number of partitions of an n-set into k parts (subsets). Write down a recurrence relation giving S(n,k) in terms of S(n-1,k-1) and S(n-1,k). Find the values of S(6,k), 1 £ k £ 6.

(b) In how many ways can six golf balls labelled 1 to 6 be put into four identical boxes so that at most one box is empty.

S(n,2) = 2^n-1-1.

File translated from T_EX by T_TH, version 2.00.
On 23 Dec 1999, 14:23.