METU Department of Mathematics Math 405 Combinatorics Spring 2010

Final, Part I

May 27 2010

Name:

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

Problem 2(4 pts). Find the number of terms in a general form of a polynomial of degree 5 in two variables. (Examples: for degree one there are three terms ax+by+c, for degree two there are six terms ax^{2} + bxy + cy^{2} + dx + ey + f, etc.)

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

Problem 4(3 pts). Write the recurrence relation for the Stirling numbers of the first and of the second kind.

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

Problem 6(3 pts). What is the number of labelled trees such that three of its vertices have degrees 10, 20 and 30 and the remaining vertices are leaves ? (Give a formula in terms of factorials, do not calculate.)

Problem 7(2 pts). Write the recurrence relation for the partition number p_{k}(n). Problem 8(2 pts). In how many ways one can triangulate a convex 10-gon ? Problem 9(2 pts). In how many ways one can connect pairwise 10 points on a circle by 5 line segments which do not intersect each other ? Problem 10(2 pts). How many matchings can be found in a complete bipartite graph K_{n,n} ? Problem 11(2 pts). What is the determinant of the Hadamard matrix of size n × n?

Final, Part II

May 27 2010

Name:

Problem 1 (10 pts). Consider the following network.

a) Find a maximal flow between vertices v_{1} and v_{6}; decompose it into simple flows.

b) Find a minimal edge-cut between v_{1} and v_{6}.

Problem 2(20 pts). Consider Latin square A = [ \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \end{matrix} ],

a) Show the four corresponding matchings in a bipartite graph K_{4,4}.

b) Find the Latin square B obtained from A by permutation of its symbols 2 and 3. Using permutations of rows and columns find a reduced Latin square B′ isotopic to B.

c) Find the presentation array of A. Find the conjugate Latin square C obtained by cyclic permutation (2, 3, 1) of elements in the triples of the array.

d) Determine which pair of the Latin squares A, B, and C are orthogonal ? (Explain your answer). e) Find a pair of orthogonal 5 × 5 Latin squares A and B corresponding to the families of lines y = x + a and y = 3x + a in the finite plane over ℤ_{5}.

Problem 3(8 pts). Prove that matrix \frac{1}{\sqrt{n}}H is orthogonal for any Haramard n×n matrix H. Deduce from this that the transpose matrix H^{T} is also an Hadamard matrix.

Problem 4(12 pts). a) Starting from matrix [ \begin{matrix}−1 & 1 \\ 1 & 1 \end{matrix} ] construct 4×4 Hadamard

matrix B and 8 × 8 Hadamard matrix C (using the iteration method).

b) Normalize the Hadamar matrix B by alternating the signs of its rows and columns. Is it possible to obtain the same normalized matrix by permutation of the rows and columns of B ?

c) Write the binary codes of the columns of B and find the corresponding family of subsets of S = {1, 2, 3, 4}. Formulate the property of this family of subsets reflecting that B is an Hadamard matrix.