UNIVERSITY OF MALTA
UNIVERSITY OF MALTA
FACULTY OF SCIENCE
Department of Mathematics
B.Sc. Part II FINAL EXAMINATION
September Session 1994
MA271 Combinatorial Theory 9 September 1994
0900 - 1015 hrs
Answer TWO questions
1. Let A1,A2,...,An be finite subsets of a set S. Show that
|
|A1Ç...ÇAn| = |
n
å
i = 1
|
(-1)i-1ai |
|
where ai denotes the sum of the cardinalities of all the
intersections of the sets taken i at a time.
Let dn be the number of permutations of the set {1,2,...,n} in which
no integer i appears in the ith position, and let qn be the number
of permutations of the set {1,2,...,n} in which none of the n-1
patterns 12,23,34,...,(n-1)n appear.
Find expressions for dn and qn, and find
|
|
lim
n®¥
|
|
dn
n!
|
and |
lim
n®¥
|
|
qn
n!
|
. |
|
2. Giving careful consideration to any special cases which arise, solve
the recurrence relation
|
an+2-2an+1cosa+an = 2sin2a (n ³ 0) |
|
given that a0 = cosa, a1 = 1+cosa and a is a constant,
0 £ a £ p.
3. Let en be the number of partitions of the positive integer
n having an even number of parts, all distinct, and let on be the number
of partitions of n with an odd number of parts, all distinct. Show
that
|
en-on = |
ì
í
î
|
| |
|
|
if n = [1/2]m(3m±1) (m ³ 1) |
| |
|
| |
|
Indicate how this relationship between en and on can be used to obtain
a recursive method for computing p(n), the number of partitions of n.
File translated from TEX by TTH, version 2.00.
On 23 Dec 1999, 13:18.