METU Department of Mathematics Math 405 Combinatorics Spring 2010

Midterm 1

April 14 2010, 17:30 – 19:00

Name:

Problem 1.

(1) Find the values p_{3}(n) (number of partitions n = a_{1} +a_{2} +a_{3}, 1 ≤ a_{1} ≤ a_{2} ≤ a_{3}) for n ≤ 8, and sketch the corresponding Ferrers diagrams for n = 8.

(2) Find p_{4}(8) and p_{4}(12) using recurrence relation (giving a complete list and counting all the partitions will NOT be considered as a solution).

(3) Find the number of partitions 16 = a_{1} + a_{2} + a_{3} + a_{4}, such that 2 ≤ a_{1} ≤ a_{2} ≤ a_{3} ≤ a_{4}.

(4) Find the number of partitions 16 = a_{1} + a_{2} + a_{3} + a_{4}, such that 2 ≤ a_{1} ≤ a_{2} ≤ a_{3} ≤ a_{4} are all even integers.

Problem 2.

(1) Seven students should split into three teams. In how many ways it can be done if each team should include at least one student? Express as a Stirling number and give an inclusion-exclusion formula for this number.

(2) Show how this number can be calculated using recurrence formulas.

(3) Seven different cars should be painted: in black, in blue, or in grey (all three colors should be used). In how many ways it can be done ? Explain how this problem is related to the preceding one.

Problem 3.

(1) For a given Dyck’s word XXXYYXYYXY find the corresponding Young Tableaux and the corresponding multiplication scheme.

(2) For a given multiplication scheme (ab)(((c(de))(fg))h) sketch the corresponding binary tree and find the corresponding triangulation of a polygon (mark its base-side).

(3) Which of the following permutations are stack sortable:

1245736 3217654 7261345

Find the binary tree and Dyck’s word corresponding to this (ONLY to stacksortable) permutation(s).

Problem 4. Let a_{k} be defined by recurrence relation a_{n} = a_{n−1} + 6a_{n−2} and the initial values a_{0} = 2 and a_{1} = 1.

(1) Find a_{n} using method of characteristic equation.

(2) Find a relation for the characteristic function f(x) of sequence {a_{n}}, and deduce a formula for f(x).

(3) Find the characteristic function g(x) for sequence b_{n} = na_{n}.