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 <n \\ (-1)^{n}n!  & \mbox{if  } k=n\end{cases}

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

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