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 1998
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.
1. (a) Let A1,A2,¼,An denote finite sets and let ai
(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 |A1ÈA2ȼÈAn| in terms of the ai.
(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 1000 are relatively prime
to both 1000 and 90?
(c) Show that there are
|
|
9
å
i = 0
|
(-1)i |
æ
ç
è
|
9
i
|
ö
÷
ø
|
(9-i)n |
|
n-digit numbers using the digits 1,2,¼,9 and such that each of the
nine digits is used at least once.
[Hint: Let Ak, 1 £ k £ 9,
be the set of all those n-digit numbers in which
the digit k is not used.]
2. (a) 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 25 can be obtained when
10 distinct dice are rolled.
(b) Using Ferrers diagrams, show that
- The number of partitions of 2n into n parts is equal to
the number of partitions of n.
- [(ii)] The number of partitions of n such that each part occurs an
even number of times is equal to the number of partitions of n such that
each part is even.
3. (a) Solve the following recurrence relation
|
an = n an-1 + (n+1)! (n ³ 1) |
|
given that a0 = 1.
(b) Let an denote the number of regions created by n mutually
overlapping circles drawn on a sheet of paper such that no three circles
have a common point of intersection.
Obtain and solve a recurrence relation for an.
[Hint: Two overlapping circles intersect at exactly two points. Consider
by how much the number of regions increases when the nth circle is drawn.]
4. The sequence áan ñ satisfies the recurrence relation
|
an+2-2aan+1 + a2 an = bn (n ³ 0) |
|
(where a,b are non-zero constants) subject to the initial conditions
a0 = a1 = 0.
Solve this recurrence relation (obtaining an in terms of a, b
and n) in the two cases:
File translated from TEX by TTH, version 2.00.
On 23 Dec 1999, 14:23.