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 sets taken i at a time. Write down, without proof, 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) Suppose there are m boxes labelled 1,2,...,m respectively and n balls (m ³ n) labelled 1,2,....n respectively. The balls are put into the boxes such that no two balls are in the same box and no ball labelled i is put into box i, for all 1 £ i £ n. Show that the number of ways in which this can be done is

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) Suppose that n straight lines are drawn in the plane such that no two lines are parallel and no three lines pass through the same point. Find the number of regions into which the plane is divided by these lines.

(b) Solve the following recurrence relation