METU Department of Mathematics Math 405 Combinatorics Spring 2010

Makeup, Part I (15 pts)

June 11, 2010

Name:

Problem 1(2 pts). Find the coefficient at x^{4}y^{3}z^{5} in (3x + y − 2z − 4)^{15} (express in terms of powers, factorials, etc., but do not calculate the result).

Problem 2(2 pts). Write the recurrence relation for the multi-nomial coefficients \binom{n}{m_{1}m_{2}...m_{k}}.

Problem 3(2 pts). Write the recurrence relation for the Catalan numbers C_{n}.

Problem 4 (1 pts). What is the number of stack sortable permutations of {1, 2, …, 7}.

Problem 5 (1 pts). In how many ways one can split a convex 9-gon into triangles by non-intersecting diagonals ?

Problem 6 (1 pts). There are 12 points marked on a circle. In how many ways one can connect them pairwise by 6 line segments which do not intersect each other ?

Problem 7 (2 pts). Give a definition of an Hadamard matrix. Problem 8 (2 pts). Explain what is the ”normalized Hadamard matrix”? Problem 9(2 pts). Formulate the marriage theorem.

Makeup, Part II (65 pts)

June 11 2010

Name:

Problem 1(15 pts). (a) Solve the following recurrence relation a_{n} = a_{n−1} + 12a_{n−2}, a_{0} = 2, a_{1} = 15.

(b) Find a particular solution of the recurrence relation a_{n} = a_{n−1}−a_{n−2}+2n−1.

(c) Solve the following recurrence relation a_{n} = 3a\frac{n}{3} + 4, a_{1} = 1.

Problem 2(5 pts).

Find three pairwise orthogonal 7 × 7 Latin squares.

Problem 3(5 pts). (a) Find a labelled tree with the Prüfer code 5453522.

(b) What is the number of labelled trees such that four of its vertices, v_{1}, v_{2}, v_{3}, v_{4}, have degrees 5, 15, 25, and 30 and the remaining vertices are leaves ? (Give a formula in terms of factorials, do not calculate.)

Problem 4 (10 pts). In how many ways one can distribute ten people into four rooms ? Solve it if

(a) some rooms can be empty

(b) no room can be empty

(c) there should be at least two people in each room Problem 4(15 pts).

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

(2) For a given multiplication scheme (ab)(((cd)(e(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:

7546321 1426735 2174365

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

Problem 5(15 pts). (a) For the following oriented graph Γ find the incidence matrix A

(b) Is there an oriented Hamiltonian path in this graph ? (Either find it, or explain why it does not exist).

(c) Give examples of three different spanning trees in graph Γ

(d) Find matrix AA^{T} and use it to find the number of spanning trees in graph Γ.

(e) Consider a network in which edge v_{k} has capacity k, for all k ≤ 7. Find the flow from v_{5} to v_{4}.