UNIVERSITY OF MALTA

UNIVERSITY OF MALTA UNIVERSITY OF MALTA

FACULTY OF SCIENCE / I.T. BOARD OF STUDIES

Department of Mathematics

B.Sc.,B.Ed.,B.A. Year I / B.Sc.(I.T.) Year II

January Session 2000

MA141 Discrete Methods 25 January 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.

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

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

2. (a) You are given that the sequence ád_n ń satisfy the recurrence relation

d_n = (n-1)(d_n-1 + d_n-2) (n ł 3).

You are also given that d₁ = 0 and d₂ = 1.

Now, let a_n = d_n - n d_n-1 for all n ł 2. What is the value of a₂? Show that a_n = -a_n-1. Deduce that a_n = (-1)ⁿ for all n ł 2.

Hence write down a first-order recurrence relation for d_n. Solve this recurrence relation. [You may leave your answer as a summation of terms involving factorials.]

What is the value of

lim
nŽĽ

d_n

3. Solve the following recurrence relation

a_n-5a_n-1+6a_n-2 = Kⁿ (n ł 2)

given that a₀ = a₁ = 0 in the two cases: (i) K = 2, (ii) K = 4.

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

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) Use generating functions to find

The number of ways of placing 2r identical balls into eight distinct boxes such that each box gets an even number of balls.
The number of ways in which a sum of 20 can be obtained when 8 distinct dice are rolled. [You may leave binomial coefficients in your answer.]

File translated from T_EX by T_TH, version 2.00.
On 29 Sep 2000, 13:16.