Prove that for all integers $j,k,n, k \ge 0$, we have

$$ \sum\limits_{i=0}^n ({-1})^{n-i} \binom {n}{i} \binom {ki}{j} = \begin{cases} 0, & \text{if } 0 \le j < n; \\ k^n, & \text{if } j = n. \end{cases} $$

The alternating sum suggests use of inclusion-exclusion principle, but I am unable to setup a situation. The sum becomes 0 which is strange for me. How do you incorporate that. Using inclusion -exclusion for counting something like surjective functions always we count something.

I am trying to learn combinatorics, so would prefer a combinatorial argument.


Consider $n$ groups of $k$ objects. The quantity ${n\choose i}{ki\choose j}$ represents the number of ways to choose $i$ of the groups, then select $j$ objects from the chosen groups. By inclusion-exclusion, the left hand side is the number of ways to choose $j$ objects total from a collection of $n$ groups of $k$ objects, such that each group has at least one object selected from it. It is not hard to see the right hand side counts the same thing.


This problem also has an algebraic proof which I submit for enrichment. Suppose we seek to evaluate

$$\sum_{q=0}^n (-1)^{n-q} {n\choose q} {kq\choose j}.$$

We introduce

$${kq\choose j} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} (1+z)^{kq} \; dz.$$

With $j$ non-negative this integral correctly represents the binomial coefficient and vanishes when $j$ is out of range. We then get for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} \sum_{q=0}^n {n\choose q} (-1)^{n-q} (1+z)^{kq} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{j+1}} (-1+(1+z)^k)^n \; dz.$$

This is

$$[z^j] \left({k\choose 1}z + {k\choose 2}z^2 + \cdots + {k\choose k}z^k\right)^n.$$

The first power of $z$ that occurs here is $z^n$ so the value is zero for $j\lt n.$ Moreover the coefficient on $z^n$ can only be achieved in one way, namely by taking the first term of the sum being exponentiated. This has coefficient $k$ so the answer for $j=n$ is $$k^n.$$

Remark. We can use this technique for larger values of $j.$ For example we get for $j=n+2$ the result

$${n\choose 1} k^{n-1} {k\choose 3} + {n\choose 2} k^{n-2} {k\choose 2}^2.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.