UNIVERSITY OF MALTA UNIVERSITY OF MALTA

FACULTY OF SCIENCE

Department of Mathematics

B.Sc. Part I EXAMINATION

September Session 1994


MA171 Combinatorial Theory 5 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 n be a positive integer whose prime factorisation is given by

n = p1e1p2e2... prer
where the pi are distinct primes. Let d(n) be the number of positive integers which are divisors of n and let f(n) be the number of postive integers less than or equal to n which are relatively prime to n. Obtain expressions for d(n) and f(n).


How many positive integers less than or equal to 9944 have an odd number of divisors?


Show that if n ³ 3 then f(n) is even.



2. The sequence < an > satisfies the recurrence relation

an+2-3aan+1+2a2an = bn        (n ³ 0)
(where a,b are nonzero constants) subject to the initial conditions a0 = a1 = 0. Solve this recurrence relation (obtaining an in terms of a and b) in the three cases:

  1. b ¹ a or 2a;
  2. b = a;
  3. b = 2a.



3. Let p(n|P) denote the number of partitions of the positive integer n which satisfy the property P. Prove the following:

  1. p(n| no. of parts = k) = p(n| largest part = k);
  2. p(n| no. of parts £ m) = p(n+m| no. of parts = m);
  3. p(n| Ferrers Diagram of partition is self-conjugate) = p(n| all parts distinct and odd);
  4. p(n| all parts distinct) = p(n| each part is odd).

File translated from TEX by TTH, version 2.00.
On 23 Dec 1999, 13:16.