1

Evaluate the expression

$$\binom{m}{i} - \binom{m}{1}\binom {m-1}{ i} + \binom{m}{2}\binom{m - 2}{i} - \ldots + (-1)^{m-i} \binom{m}{m-i}\binom{ i }{i} $$

I'm really stumped about trying to get anything meaningful out of this. For some context I am trying to find the determinant of a matrix consisting of binomial coefficients, and have been given the hint "it may be helpful to evaluate [above expression]".

N. F. Taussig
  • 76,571
A. Rober
  • 51
  • 1
    Not that it necessarily helps, but this is equivalent to evaluating the power series $$\sum_{k=i}^{m-i} \binom{m}{k}\binom{m-k}{i}x^k$$ at $x=-1$. Also, rewriting the binomial coefficients in terms of multinomial coefficients yields $\binom{m}{k,i,m-k-i}$ which is suggestive of some trinomial expansion e.g. $(1+x+y)^k$. – Semiclassical Mar 17 '16 at 15:59

2 Answers2

1

Hint: Each term is of the form $\binom{m}{k}\binom{m-k}{i}$ where $k \leq m-i$. But this can be rewritten as \begin{align} \binom{m}{k}\binom{m-k}{i} &=\frac{m!}{k!(m-k)!}\frac{(m-k)!}{i!(m-k-i)!}\\ &=\frac{m!}{k!\,i!\,(m-k-i)!}\\ &=\frac{m!}{i!(m-i)!}\frac{(m-i)!}{k!(m-k-i)!}=\binom{m}{i}\binom{m-i}{k}. \end{align}

Consequently we can factor $\binom{m}{i}$ from the original series to get

$$\binom{m}{i}\left[\binom{m-i}{0}-\binom{m-i}{1}+\cdots+(-1)^{m-i}\binom{m-i}{m-i}\right].$$ So in this case we can eliminate the products of binomial coefficients, leaving a series which is hopefully more manageable.

Semiclassical
  • 15,842
1

Here’s a combinatorial version Semiclassical’s computational argument.

You have a box of white balls numbered $1$ through $n$. For some $r$ such that $0\le r\le m-i$ you pick $r$ of the balls and coler them red, and then you pick $i$ of the remaining white balls and color them blue; for a given value of $r$ there are $\binom{m}r\binom{m-r}i$ possible outcomes. Your expression is

$$\sum_{r=0}^{m-i}(-1)^r\binom{m}r\binom{m-r}i\;;\tag{1}$$

clearly this is the number of outcomes with an even number of red balls minus the number of outcomes with an odd number of red balls.

Every outcome has exactly $i$ blue balls. Let $\mathscr{I}$ be the family of all sets of $i$ balls from the box. For each $I\in\mathscr{I}$ and $r$ such that $0\le r\le m-i$ there are $\binom{m-i}r$ outcomes having $r$ red balls and $I$ as its set of blue balls. The contribution of these outcomes to $(1)$ is

$$\sum_{r=0}^{m-i}(-1)^r\binom{m-i}r\;,\tag{2}$$

and $|\mathscr{I}|=\binom{m}i$, so

$$\sum_{r=0}^{m-i}(-1)^r\binom{m}r\binom{m-r}i=\binom{m}i\sum_{r=0}^{m-i}(-1)^r\binom{m-i}r\;.$$

Finally, $(2)$ is the number of even-sized subsets of $[m-i]$ minus the number of odd-sized subsets of $[m-i]$, and it’s well known that this is $0$ unless $m=i$, in which case it’s $1$. Thus,

$$\sum_{r=0}^{m-i}(-1)^r\binom{m}r\binom{m-r}i=\begin{cases} 1,&\text{if }i=m\\ 0,&\text{otherwise}\;. \end{cases}$$

Brian M. Scott
  • 616,228