Give a combinatorial proof for

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

For hint, we can denote $A_i$ denote the set of distributions of stars to kids such that kid i gets at least 2 stars.

My approach

LHS is the count for giving k stars to n students.

RHS is ...??? (looks like intersection principle, but I'm no sure)

Thank you!!!

  • $\begingroup$ Yes, you can use inclusion-exclusion to show this with the interpretation that $k$ children can be selected from $n$ in LHS ways or you can select $k$ children from $n$ by putting $k$ stars in $n$ boxes ($n-1$ bars separating boxes) so that each box had at most $1$ star in RHS ways. Alternatively The LHS is the $x^k$ coefficient of $(1+x)^n$ and the RHS is the $x^k$ coefficient of $\left(\frac{1-x^2}{1-x}\right)^n$ but then $1-x^2=(1-x)(1+x)$ so we are back to $(1+x)^n$ again! :) $\endgroup$ – N. Shales Feb 20 '18 at 18:26
  • $\begingroup$ I guess the second of those would be algebraic. But they represent exactly the same thing. $\endgroup$ – N. Shales Feb 20 '18 at 18:53
  • $\begingroup$ the second of those? Can you solve it without using boxes? I guess you are using it with balls and bins strategy. What about the second of RHS part? I agree both does samething but why is it separated? $\endgroup$ – John Baek Feb 20 '18 at 19:22
  • $\begingroup$ I will elaborate in an answer. $\endgroup$ – N. Shales Feb 20 '18 at 20:46

Method 1: Inclusion-exclusion

There are two ways of viewing distributions of $k$ stars to $n$ students. The first is simply to distribute $k$ stars, $1$ per student:

$$\begin{array}{c|c|c|c|c|c|c|c|}\text{student}&1&2&3&\cdots &n-2&n-1&n\\\hline \text{distribution}&\star &&\star &\cdots &\star &\star &\end{array}$$

and there are $\binom{n}{k}$ ways to do this.

The other way to view distributions is by using the separating bars as a second set of identical objects, the above distribution looks like this:

$$\begin{array}{c|c|c|c|c|c|}\star &&\star &\cdots &\star &\star \end{array}$$

Now, there are clearly $n+k-1$ objects here: $k$ stars and $n-1$ bars. That means there are $\binom{n+k-1}{k}$ arrangements of these. But many of those will have several stars between two bars or on ends, thus representing distributions not counted by $\binom{n}{k}$.

What we need to do is count arrangements of stars and bars so that there is no more than $1$ star between any two bars or on ends.

We call set $A_i$ the set of the arrangements where student $i$ has more than $1$ star. It is clear that:


because, if student $i$ has at least $2$ stars there are $k-2$ remaining to arrange with the $n-1$ bars.

Similarly for the set of arrangements where students $i_1$ and $i_2$ both have at least 2 stars each:

$$S_2=|A_{i_1}\cap A_{i_2}|=\binom{n+k-2(2)-1}{k-2(2)}$$

and in general for $j$ students each having at least two stars:

$$S_j=|A_{i_1}\cap\cdots \cap A_{i_j}|=\binom{n+k-2j-1}{k-2j}$$

So, using the principle of inclusion-exclusion, the size of the set containing none of the elements of $A_{1}\cup\cdots \cup A_{n}$ is:

$$|(A_{1}\cup\cdots \cup A_{n})'|=\sum_{j=0}^{n}(-1)^j\binom{n}{j}S_j$$

which is $\binom{n}{k}$.

Here $S_0=\binom{n+k-1}{k}$ is the size of the set of all arrangements of $n-1$ bars and $k$ stars.

So we have, finally:

$$|(A_{1}\cup\cdots \cup A_{n})'|=\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}=\binom{n}{k}$$

which is not quite what you have in the question but checks out nonetheless.

The upper limit on $j$ in the summation is taken care of by defining $\binom{a}{b}=0$ for $b\gt a$ and for $b\lt 0$.

Method 2:Generating Functions

The generating function for distributing $k$ stars to $n$ students with each student getting at most $1$ star is $(1+x)^n$ since each of the $n$ students may successively receive a star ('$x$') or not ('$1$'). Thus the $x^k$ coefficient is:


Alternatively, since $1+x$ is a finite geometric series it can be written:


so that:

$$\begin{align}(1+x)^n&=\left(\frac{1-x^2}{1-x}\right)^n\\[2ex]&=(1-x^2)^n(1-x)^{-n}\\[2ex]&=\left(\sum_{j=0}^{n}(-1)^j\binom{n}{j}x^{2j}\right)\left(\sum_{k\ge 0}\binom{n+k}{k}x^k\right)\\[2ex]&=\sum_{k\ge 0}\left(\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}\right)x^k\end{align}$$

then we also have:

$$[x^k](1+x)^n=\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}$$

hence, again:

$$\binom{n}{k}=\sum_{j\ge 0}(-1)^j\binom{n}{j}\binom{n+k-2j-1}{k-2j}$$


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.