Solutions: Combinatorics conundrums for RMO and INMO practice

(These set of problems and solutions are due Laszlo Lovasz, “Combinatorial Problems and Exercises, AMS-Chelsea Publishing:

http://www.amazon.in/Combinatorial-Problems-Exercises-Laszlo-Lovasz/dp/0821887084/ref=sr_1_1?s=books&ie=UTF8&qid=1477076752&sr=1-1&keywords=combinatorial+problems+and+exercises )

Problem 1)

Prove the identity:

$\sum_{i=0}^{n}(-1)^{i}{n \choose i}i^{k} = 0$ when $0 \leq k < n$ and is $(-1)^{n}n!$ if $k=n$ .

Proof:

Some basics of the inclusion-exclusion principle are in order (by the way, this is also known as the sieve theory, named after the Sieve of Eratosthenes):

One powerful tool in the theory of enumeration as well as in prime number theory is the inclusion-exclusion principle (sieve of Eratosthenes). This relates the cardinality of the union of certain sets to the cardinalities of intersection of some of them, these latter cardinalities often being easier to handle. However, the formula does have some handicaps: it contains terms alternating in signs, and in general, it has too many of them!

(a) The Sieve Formula:

Let $A_{1}, \ldots, A_{n}$ be arbitrary events of a probability space $(\Omega, P)$ . For each, $I \subseteq \{ 1, \ldots, n\}$ , let

$A_{I} = \prod_{i \in I}A_{i}$ ; $A_{\phi}=\Omega$

and let $\sigma_{k} = \sum_{|I| = k}P(A_{I})$ , $\sigma_{0}=1$

Then, $P(A_{1}+ \ldots + A_{n}) = \sum_{j=1}^{n}(-1)^{j-1}\sigma_{j}$

(b) (Inclusion-Exclusion Principle)

Let $A_{1}, \ldots, A_{n} \subseteq S$ where S is a finite set, and let $A_{I} = \bigcap_{i \in I}A_{i}$ ; $A_{\phi} = S$ .

Then, $|S-(A_{1}\cap \ldots A_{n})|= \sum_{I \subseteq \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|$

Solution :

Let $|X| = k$ , $Y = \{ y_{1}, \ldots , y_{n}\}$ . Then, the number of those tmappings of X into Y which are onto Y is, obviously,

$0$ if $k < n$ , and $n!$ , if $k=n$ .

On the other hand, let $A_{i}$ denote the set of mappings of X into $Y - y_{i}$ and let S be the set of all mappings of X into Y. Then, we are interested in $S - (A_{1} \bigcap \ldots \bigcap A_{n})$ . By the inclusion-exclusion formula:

$|S-(A_{1}\cap \ldots A_{n})|= \sum_{I \subseteq \{ 1, \ldots n\}}(-1)^{|I|}|A_{I}|$

Here, $A_{I}$ is the set of mappings of X into $Y - \{ y_{i}: i \in I\}$ , hence,

$|A_{I}| = (n-|I|)^{k}$ . So,

$|S- (A_{1} \bigcup \ldots \bigcup A_{n})| = \sum_{j=0}^{n}(-1)^{j}{n \choose j}(n-j)^{k} = \sum_{j=0}^{n}(-1)^{n-j}{n \choose n}j^{k}$ which proves the assertion.

If $k >n$ , the result of the same inclusion-exclusion procedure is the number of mappings of X onto Y, which is $n! \{ \begin{array}{c} k \\ n \end{array}\}$ .

Problem 2)

Prove the following Abel identities:

(2a) $\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(y+n-k)^{n-k} = (x+y+n)^{n}$

Proof (2a):

We prove (2a) by induction on n. For $n=0$ , it is trivial. Let $n>0$ . We have

$\frac{\partial}{\partial{y}}(x+y+n)^{n} = n(x+y+n)^{n-1}=n(x+(y+1)+(n-1))^{n-1}$

$\frac{\partial}{\partial{y}}\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}y+n-k)^{n-k}$

$= \sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(n-k)(y+n-k)^{n-k-1}$

$= n\sum_{k=0}^{n-1}{{n-1} \choose k}x(x+k)^{k-1}((y+1)+(n-1)-k)^{(n-1)-k}$

The two right-hand sides here are equal by the induction hypothesis. To prove the identity, it suffices to show that (a) holds for any one value of n. Choose $y = -x-n$ . Then, the right hand side vanishes while the left hand side is

$\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(-x-k)^{n-k}$

$= x \sum_{k=0}^{n}{n \choose k}(-1)^{n-k}(x+k)^{n-1} =$

$= \sum_{j=0}^{n-1}{(n-1) \choose j}x^{n-j}\sum_{k=0}^{n}{n \choose k}k^{j}(-1)^{n-k}=$

$=\sum_{j=0}^{n-1}{{n-1} \choose j}x^{n-j}S(j,n)n!=0$ as $y<n$ .

Note: In the last step we have used the following:

$\{ \begin{array}{c} n \\ k \end{array} \} = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j}j^{n}$ .

(2b) Prove:

$\sum_{k=0}^{n}{n \choose k}(x+k)^{k-1}(y+n-k)^{n-k-1}=(\frac{1}{x}+\frac{1}{y})(x+y+n)^{n-1}$

Proof:

The left hand side of (2a) can be rewritten as

$\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(y+n-k)^{n-k-1}(y+n-k) =$

$= \sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}y(y+n-k)^{n-k+1}+ \sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}(y+n-k)^{n-k-1}(n-k)$

Here, the second term is

$\sum_{k=0}^{n-1}{{n-1} \choose k} x (x+k)^{k-1}((y+1)+(n-1)-k)^{(n-1)-k}$

$= n(x+(y+1)+(n-1))^{n-1} = n(x+y+n)^{n-1}$ by 2a. Hence,

$\sum_{k=0}^{n}{n \choose k}x(x+k)^{k-1}y(y+n-k)^{n-k-1} = (x+y+n)^{n}-n(x+y+n)^{n-1} =$

$= (x+y)(x+y+n)^{n-1}$

Dividing by $xy$ identity (b) follows.

(2c) Prove:

$\sum_{n-1}^{k=1}{n \choose k}k^{k-1}(n-k)^{n-k-1}=2(n-1)n^{n-2}$

Proof:

Subtract $\frac{1}{x}(y+n)^{n-1}+\frac{1}{y}(x+n)^{n-1}$ from both sides of $(b)$ then we get,

$\sum_{k=1}^{n-1}{n \choose k}(x+k)^{k-1}(y+n-k)^{n-k-1} =$

$\frac{1}{x}((x+y+n)^{n-1}-(y+n)^{n-1}) + \frac{1}{y}((x+y+n)^{n-1}-(x+n)^{n-1})$

Letting $x, y \rightarrow 0$ , we obtain (c).

Problem 3:

Let $f_{n}(x) = x(x-1) \ldots (x-n+1)$ . Prove that $f_{n}(x+y) = \sum_{k=0}^{n}{n \choose k}f_{k}(x)f_{n-k}(y)$ . Find other examples of such equations of polynomials.

Proof: TBD.

Problem 4:

Proof: TBD.

Problem 5:

The number of non-congruent triangles with circumference $2n$ and integer sides is equal to the number of non-congruent triangles with circumference $2n-3$ and integer sides. This number is also equal to the number of partitions of n into exactly three terms. Determine this number.

Proof:

The first assertion is easy. If integers a, b, c are the sides of a triangle with circumference $2n-3$ , then $a+1, b+1, c+1$ trivially also satisfy the triangle inequality, and so they are the sides of a triangle with circumference $2n$ . Conversely, if a, b, c are the sides of a triangle with circumference $2n$ , then

$(a-1)+(b-1)-(c-1) = a +b -c - 1 \geq 0$

and since, $a+b-c-1=2n-2c-1$ is odd, we have

$(a-1)+(b-1)-(c-1) >0$

Hence, $a-1$ , $b-1$ , $c-1$ are the sides of a triangle with circumference $2n-3$ .

To prove the second assertion, observe that if $n = x+y+z$ , where x, y, z are positive integers, then

$(x+y)+(x+z)+(y+z) = 2n$

$(x+y)+(x+z) = y+z + 2x>y+z$ , that is, $x+y, y+z,, x+z$ are the sides of a triangle with circumference 2n. Conversely, if integers a, b, c are the sides of such a triangle then, setting $x=n-a, y=n-b. z = n-c$ , we have

$x = \frac{b+c-a}{2}>0$ , $y>0$ , $z>0$ and also

$x+y=c, x+z=b, y+z =a$ .

Thus, we have a one-to-one correspondence between partitions of n and triangles with circumference $2n$ (and integer sides).

To determine the number of partitions of n into exactly three terms we observe first that the number of partitions of m into exactly two terms not exceeding a is

$0$ , when $a < \frac{m}{2}$