METU Department of Mathematics Math 405 Combinatorics Spring 2010

PROBLEM LIST

Partition Theory

Problem 1. How many ways to collect $24 from 4 children and 6 adults if each person gives at least $1, but each child can give at most $4 and each adult at most $6 ?

Problem 2. Ten gentlemen came to a party and checked their hats at the entrance. After the party, the man at service was a bit drunk and gave the hats back in an arbitrary order. Estimate the probability that none of the gentlemen received his own hat.

Problem 3. (1) List all the partitions of 7; (2) show the corresponding Ferrers (Young) diagrams; (3) determine which partitions are conjugate to each other.

Problem 4. Find p_{3}(10) using a recursive formula for p_{k}(n).

Problem 5. Ten students should be split into three teams. In how many ways they can do it if

(1) each team should contain at least one student;

(2) each teem should contain at least two students;

(3) each team should contain at least one and at most three students ?

Problem 6. Consider f(x) = (1 + x)^{−1}(1 + x^{2})^{−1}(1 + x^{5})^{−1} as a generating function. What is the meaning of its coefficients (describe the corresponding combinatorial problem)?

Problem 7. Give a combinatorial proof of the relation p_{k}(n) = p_{k}(n−k)+p_{k−1}(n− k) + ⋯ + p_{1}(n − k).

Problem 8. Prove that p_{2}(n) = [\frac{n}{2}] and p_{3}(n) = [\frac{n^{2}+3}{12}] (use a suitable form of induction).

Problem 9. Prove that St(n, 2) = 2^{n−1} − 1 and St(n, n − 1) = \binom{n}{2}.

Problem 10. Prove that St(n, k) = \frac{1}{k!} ∑_{j=i} k(−1)^{k+j}\binom{k}{j}j^{n}.

Problem 11. Eight non-distinguishable apples should be distributed between four children. In how many ways it can be done if

(1) there is no restrictions on the number of apples for each child;

(2) each child should receive at least one apple;

(3) each child should receive at least one and at most three apples Assume that you need to prepare four packets with eight apples totally to be distributed later between children. In how many ways you can distribute apples between these non-distinguishable (and non-empty) packets ?

Problem 12. Estimate the number of permutations of 6 elements which split into three cycles.

Problem 13. Given multiplication scheme (ab)(((cd)e)(fg))

(1) find the corresponding rooted binary tree;

(2) find the corresponding triangulation of a polygon (show its base);

(3) find the corresponding Dyck’s word.

Problem 14. Given Dyck’s word XXY XY XY Y XY

(1) connect 10 points on a circle by non-intersecting chords in accord with this word (show the base arc on a circle);

(2) show the corresponding Young Tableaux;

(3) show the corresponding multiplication scheme.

Problem 15.

(1) Determine which of the following permutations are stack sortable: P_{1} = 34512, P_{2} = 42315, P_{3} = 21543; give the reason (if a permutation is not stack sortable);

(2) show the stack sorting scheme for the stack sortable permutations;

(3) find the corresponding Dick words;

(4) find the corresponding binary trees.

Recursion and generating functions

Problem 16. Use binomial expansion to evaluate

(1) ∑_{k=0}^{m} \binom{m}{k}\binom{n}{r+k}

(2) ∑_{k=1}^{r}(−1)^{k}\binom{n}{k}\binom{n}{r−k}

(3) ∑_{k=0}^{n} 2^{k}\binom{n}{k}

Problem 17. Show that the binomial sum s_{n} = \binom{n+1}{0} + \binom{n}{1} + \binom{n−1}{2} + … satisfies the Fibonacci relation.

Problem 18. Show that (1−x−x^{2}−x^{3}−x^{4}−x^{5}−x^{6})^{−1} is the generating function for the number of ways a sum n can occur if a die is rolled any number of times.

Problem 19. Find a generating function for the number of integer solutions of 2x + 3y + 7z = n with

(1) x, y, z ≥ 0

(2) 0 ≤ z ≤ 2 ≤ y ≤ 8 ≤ x

Problem 20. Find a generating function for the number of ways to distribute n identical objects into

(1) three indistinguishable boxes

(2) n indistinguishable boxes Problem 21.

(1) Show that the number of partitions of 10 into distinct summands is equal to the number of partitions of 10 into odd summands by listing all the partitions of these types.

(2) Show algebraically that the generating functions for partition of n into distinct summands is equal to the generating functions for partitions of n into odd summands, and hence the number of these two types of partitions are equal.

Problem 22. Show that 2(1−x)^{−3}[(1−x)^{−3} +(1+x)^{−3}] is the generating function for the number of ways to toss n identical dice and obtain an even sum.

Problem 23. Find generating functions whose coefficients a_{n} are

a_{n} = 5; a_{n} = n; a_{n} = 3n^{2}; a_{n} = 3n + 7; a_{n} = n(n − 1)(n − 2)(n − 3). Use these generating functions to evaluate sums

(1) 0 + 1 + 2 + 3 + ⋯ + n

(2) 0 + 3 + 12 + ⋯ + 3n^{2}

(3) 7 + 10 + ⋯ + (3n + 7).

Problem 24. Verify the following identities for Fibonacci numbers F_{i} by induction or combinatorial argument. Here F_{0} = F_{1} = 1.

(1) ∑_{i=0}^{n} F_{i} = F_{n+2} − 1

(2) ∑_{i=0}^{n} F_{i}^{2} = F_{n}F_{n+1}

(3) ∑_{i=0}^{n} F_{2i} = F_{2n+1}

(4) F_{1} − F_{2} + F_{3} − ⋯ − F_{2n} = −F_{2n−1}

Problem 25.

(1) Show that F_{n+m} = F_{m}F_{n} + F_{m−1}F_{n−1}.

(2) Conclude that F_{n−1} divides F_{kn−1}.

Problem 26. Solve the following recurrence relations (1) a_{n} = 2a\frac{n}{2} + 5

(2) a_{n} = 2a\frac{n}{4} + n

(3) a_{n} = 3a\frac{n}{3} + 4

Problem 27. Find a recurrence relation for the number of ways to distribute n distinct objects into five boxes. What is the initial condition?

Problem 28. Find a recurrence relation for the number of regions created by n mutually overlapping circles on a piece of paper (no three circles have a common intersection point).

Problem 29. Find a recurrence relation for the number of regions created by n lines on a piece of paper if k of the lines are parallel and the other n − k lines intersect all other lines (no three lines have a common intersection point).

Problem 30. Solve the following recurrence relations.

(1) a_{n} = 3a_{n−1} + 4a_{n−2}, a_{0} = a_{1} = 1

(2) a_{n} = a_{n−2}, a_{0} = a_{1} = 1

(3) a_{n} = 2a_{n−1} − a_{n−2}; a_{0} = a_{1} = 2

Problem 31. Prove that that the number of ways to partition a convex (n+1)-gon by non-crossing diagonals into triangles and one quadrilateral is \binom{2n−3}{n−3}.