|
|
Combinatorial interpretation of an alternating binomial sum For all $0\le k\le n$:$$\sum_{i=k}^n (-1)^{i-k} \binom{i}{k} \binom{n+1}{i+1}=1$$
Proof by @bof
Rewrite the identity with the index of summation changed from $i$ to $j$ where $j=i-k+1$:
$$\sum_{j=1}^{n+1-k}(-1)^{j-1}\binom{n+1}{k+j}\binom{k+j-1}k=1.$$
Define a "good word" to be a word of length $n+1$ over the alphabet $\{A,B,C\}$ satisfying the conditions: there are exactly $k$ $C$'s, there is at least one $B$, and the first $B$ precedes all the $C$'s.
If $j$ is the number of $B$'s in a good word, then we must have $1\le j\le n+1-k$; moreover, the number of good words with exactly $j$ $B$'s is given by the expression
$$\binom{n+1}{k+j}\binom{k+j-1}k.$$
The combinatorial meaning of the identity is that the number of good words with an odd number of $B$'s is one more than the number of good words with an even number of $B$'s. Here is a bijective proof of that fact.
Let $w$ be the word consisting of a single $B$ preceded by $n-k$ $A$'s and followed by $k$ $C$'s; this is a good word with an odd number of $B$'s. Let $W$ be the set of all good words different from $w$; we have to show that $W$ contains just as many words with an odd as with an even number of $B$'s. To see this, observe that the operation of switching the last non-$C$ letter in a word (from $A$ to $B$ or from $B$ to $A$) is an involution on $W$ which changes the parity of the number of $B$'s. |
|
零定义
Posted 2013-8-7 17:46
kuing
Posted 2013-8-7 19:54
