Answer TWO questions

Hence show that

2. In this question, p(n|P) denotes the number of partitions of the positive integer n having property P.

• Let P₁ be the property ``No part in the partition appears more than k times'' and let P<sub>2</sub> be the property ``No part in the partition is divisible by k+1''. Prove that p(n|P₁) = p(n|P₂).
• Let n ³ 8. Show, by induction on n or otherwise, that

  p(n| Each part equals 3 or 5) ³ 1.

• Let

  en = p(n| Even number of parts, all distinct)

  and

  on = p(n| Odd number of parts, all distinct).

  Write down an expression for e_n-o_n and explain how this relationship can be used to obtain a recursive method for computing p(n), the number of parts of n.

3. Let S(n,k) denote the number of partitions of an n-set into k parts. Show that

• S(n,k) = S(n,n) = 1;
• S(n,k) = S(n-1,k-1)+kS(n-1,k)     (2 £ k £ n-1);
• S(n,2) = 2^n-1-1     (n ³ 2);
• S(n,3) = ¹/₂(3^n-1-2ⁿ+1)     (n ³ 3).

[Hint: For (iii) and (iv) use induction on n.]

Show that the number of surjections from an n-set to a k-set is k!S(n,k).

Let A be the set of ``words'' containing five letters from the set{a,e,i,o,u,p,q,r,s,t} (repetitions allowed, order of choice significant) with the property that, for every word in A, the number of distinct vowels is one while the number of distinct consonants is two. Find |A|.