# Give a combinatorial proof (n, k)

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!!!

• 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! :) – N. Shales Feb 20 '18 at 18:26
• I guess the second of those would be algebraic. But they represent exactly the same thing. – N. Shales Feb 20 '18 at 18:53
• 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? – John Baek Feb 20 '18 at 19:22
• I will elaborate in an answer. – 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:

$$S_1=|A_i|=\binom{n+k-2-1}{k-2}$$

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:

$$\binom{n}{k}=[x^k](1+x)^n$$

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

$$1+x=\frac{1-x^2}{1-x}$$

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}$$