# Combinatorics conundrums for RMO and INMO practice

Problem 1) Prove the identity

$\sum_{i=0}^{n}(-1)^{k}{n \choose i}(i)^{k} = \begin{cases}0 & \mbox{if } 0 \leq k

What do we get if $k>n$ ?

Hint: Count the number of mappings of a set of k given elements onto a set of n given elements.

Problem 2) Prove the following Abel identities:

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

Problem 2b) $\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}$

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

Hint: To prove problem 2a, differentiate both sides with respect to y, and use induction on n. The other two sub-problems will follow from this sub-problem a.

Problem 3) Let $f_{n} = 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 sequences of polynomials.

Hint: Use $f_{n}(x) = n! {x \choose n}$

Problem 4) Evaluate the determinants:

$\left| \begin{array}{cccc} (1,1) & (1,2) & \ldots & (1,n) \\ (2,1) & (2,2) & \ldots & (2,n) \\ \vdots & \vdots & \vdots & \vdots \\ (n,1) & (n,2) & \ldots & (n,n)\end{array} \right|$

and

$\left|\begin{array}{cccc} (2,2) & (2,3) & \ldots & (2,n) \\ (3,2) & (3,3) & \ldots & (3,n) \\ \vdots & \vdots & \vdots & \vdots \\ (n,2) & (n,3) & \ldots & (n,n) \end{array} \right|$

where $(i,j)$ denotes the greatest common divisor of i and j.

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 the number.

More conundrums to follow…(no hints for problems 4 and 5 above ! :-))

Nalin Pithwa

This site uses Akismet to reduce spam. Learn how your comment data is processed.