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}

a - \lfloor{\frac{m-1}{2}}\rfloor when \frac{m}{2} \leq a \leq m,

\lfloor \frac{m}{2} \rfloor, if a \geq m.

Hence, the number of partitions n = a+b+c, where a \geq b \geq c is

\sum_{\frac{n-a}{2} \leq a <n-a}(a-\lfloor \frac{n-a-1}{2}\rfloor) + \sum_{n-a \leq a}\lfloor \frac{n-a}{2}\rfloor

or equivalently,

\sum_{\frac{n}{3} \leq a < \frac{n}{2}}(a-\lfloor \frac{n-a-1}{2}\rfloor)+\sum_{\frac{n}{2}\leq a \leq n}\lfloor \frac{n-a}{2}\rfloor

It is seen that the result depends on the residue of n mod 6, example, if n = 6k, then the result is 3k^{2}.

More conundrums coming soon …!

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s