3
$\begingroup$

I am supposed to manipulate the equation $\sum^{n}_{i=0}{(-1)^{i}\binom{n}{ i}\binom{n +m - i}{j-i}}$, where n,m,j are natural numbers and $n \leq j \leq n+m$ into something without a sum.

The only comment is to interpret this combinatorially and use the Principle of Inclusion and Exclusion.

I have tried writing out the binomial coefficients, but to no avail. Combinatorially I am lost as well.

I have no idea on how to proceed. Any help would be greatly appreciated.

$\endgroup$
  • $\begingroup$ Just a thought, but this reminds me of the partition of a set of elements into 2 subsets (say two colours) and there is an identity very similar when you count in two different manners the amount of subsets of the total set, classifying the subsets according to the number of elements of each colour they contain. I strongly suspect that the answer you are looking for may have something to do with this. $\endgroup$ – Rogelio Molina Nov 1 '13 at 10:03
2
$\begingroup$

My hunch was wrong, it has to do with the exclusion-inclusion principle. Consider a set of $n+m$ elements (labeled $1,2,... n+m$) Define the set $S$ as the set of all subsets of $S$ with $j$ elements (ignoring the ordering), such set has cardinality $|S| = \binom{n+m}{j}$, an element of $S$ looks something like $(1,3,4,9,\cdots, \cdot)$ with $j$ numbers inside. Now, let $A_k$ be the subset of $S$ given by all elements of $S$ which contain the number $k$, we let this number take the values $k=1,2, \cdots, n$, since repetitions are not allowed, and all possible collections are counted, the cardinality of such set is easily computed by fixing one element to be $k$, leaving $j-1$ slots to fill, from $n+m-1$ numbers, hence:

$|A_k| = \binom{n+m-1}{j-1}$

There are $n$ such sets

It is easy also to show that (using the same argumentation, now two numbers are fixed $k,l$ with $k\neq l$ so there remain $j-2$ slots to be filled with $n+m-2$ numbers)

$|A_k \cap A_l| = \binom{n+m-2}{j-2} $

In general now we have

$$|\bigcap_{a=1}^i A_{l_a} | =\binom{n+m-i}{j-i} $$ and there are $\binom{n}{i}$ such intersections (all sets carry $i$ distinct subindices). The exclusion inclusion principle is now applied to the set $S$ and the subsets $A_i$ this is just substitution:

$$ |S - \bigcup_{i=1}^n A_i| = \sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-i}{j-i} $$ Compute now the cardinality of the set directly: it is the subset of elements of $S$ which do not contain any of the numbers $1,2, \cdots, n$, so these are all the combinations of just $m$ numbers in $j$ slots. This number is $\binom{m}{j}$, so we conclude that:

$$ \sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-i}{j-i} = \binom{m}{j} $$

$\endgroup$
4
$\begingroup$

Here is an answer using generating functions. We seek to evaluate $$\sum_{k=0}^n {n\choose k} (-1)^k {n+m-k\choose j-k}$$ where $n\le j \le n+m.$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

Now we need to bring the given sum into the right format. We get $$\frac{1}{(n+m-j)!} \sum_{k=0}^n {n\choose k} \frac{(-1)^k}{(j-k)!} (n+m-k)!$$ This gives for $A(z)$ that $$A(z) = \sum_{k\ge 0} \frac{(-1)^k}{(j-k)!} \frac{z^k}{k!} = \frac{1}{j!} \sum_{k\ge 0} {j\choose k} (-z)^k = \frac{1}{j!} (1-z)^j.$$ For $B(z)$ we get that $$B(z) = \sum_{k\ge 0} (k+m)! \frac{z^k}{k!} = m! \sum_{k\ge 0} {k+m\choose k} z^k = m! \frac{1}{(1-z)^{m+1}}.$$ Therefore the closed form of the sum is given by $$\frac{1}{(n+m-j)!} n! [z^n] A(z) B(z) = \frac{1}{(n+m-j)!} n! [z^n] \frac{m!}{j!} \frac{1}{(1-z)^{m+1-j}}$$ This is $$\frac{1}{(n+m-j)!} n! \frac{m!}{j!} {n+m-j\choose n} = \frac{1}{(n+m-j)!} n! \frac{m!}{j!} \frac{(n+m-j)!}{n!(m-j)!} = {m\choose j},$$ QED. I do think the mechanics of this calculation make it attractive.

There is another calculation of this type at this MSE link -- I and at this MSE link -- II.

$\endgroup$

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.