METU Department of Mathematics Math 405 Combinatorics Spring 2010

QUIZ 3

Problem 1. Find the number of derangements of {1, 2, 3, 4, 5}, that is such permutations in which each number is placed in “wrong” order. (Give a formula and calculate the answer).

Problem 2. Find p(5) = p_{1}(5) + p_{2}(5) + … by giving a list of all unordered partitions of 5.

Problem 3. Sketch the Ferrers diagrams for all the unordered partitions of 6 into 3 summands.

Problem 4. Find the generating function f(x) for the recurrence relation a_{n+1} = 2a_{n}, a_{0} = 1. Which equation for f(x) follows from this recurrence relation ?