Difference between revisions of "Combinatorial identity"

Revision as of 08:37, 12 March 2009

Hockey-Stick Identity

For $n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}$ .

int c(int n,int r){
 int res=1;
 for(int i=0;i<r;i++){
  res=res*(n-i)/(i+1);
  }
 return res;
 }
for(int n=0;n<10;n++){
 for(int i=0;i<=n;i++){
  label(string(c(n,i)),(11-i,-n);
  }
 }
 (Error making remote request. Unknown error_msg)

This identity is known as the hockey-stick identity because, on Pascal's triangle, when the addends represented in the summation and the sum itself are highlighted, a hockey-stick shape is revealed.

Proof

Inductive Proof

This identity can be proven by induction on $n$ .

Base Case Let $n=r$ .

$\sum^n_{i=r}{i\choose r}=\sum^r_{i=r}{i\choose r}={r\choose r}=1={r+1\choose r+1}$ .

Inductive Step Suppose, for some $k\in\mathbb{N}, k>r$ , $\sum^k_{i=r}{i\choose r}={k+1\choose r+1}$ . Then $\sum^{k+1}_{i=r}{i\choose r}=\left(\sum^k_{i=r}{i\choose r}\right)+{k+1\choose r}={k+1\choose r+1}+{k+1\choose r}={k+2\choose r+1}$ .

Algebraic Proof

It can also be proven algebraically with Pascal's Identity, ${n \choose k}={n-1\choose k-1}+{n-1\choose k}$ . Note that

${r \choose r}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}$ $={r+1 \choose r+1}+{r+1 \choose r}+{r+2 \choose r}+\cdots+{r+a \choose r}$ $={r+2 \choose r+1}+{r+2 \choose r}+\cdots+{r+a \choose r}=\cdots={r+a \choose r-1}+{r+a \choose r}={r+a+1 \choose r+1}$ , which is equivalent to the desired result.

Combinatorial Proof

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Urns, there are ${n+k-1\choose k-1}$ ways to do this. Alternatively, we can first give $0\le i\le n$ candies to the oldest child so that we are essentially giving $n-i$ candies to $k-1$ kids and again, with Balls and Urns, ${n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}$ , which simplifies to the desired result.

Vandermonde's Identity

Vandermonde's Identity states that $\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r$ , which can be proven combinatorially by noting that any combination of $r$ objects from a group of $m+n$ objects must have some $0\le k\le r$ objects from group $m$ and the remaining from group $n$ .

Another Identity

$\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}$

Hat Proof

We have $2k$ different hats. We split them into two groups, each with k hats: then we choose $i$ hats from the first group and $k-i$ hats from the second group. This may be done in $\binom{k}{i}^2$ ways. Evidently, to generate all possible choices of $k$ hats from the $2k$ hats, we must choose $i=0,1,\cdots,k$ hats from the first $k$ and the remaining $k-i$ hats from the second $k$ ; the sum over all such $i$ is the number of ways of choosing $k$ hats from $2k$ . Therefore $\sum_{i=0}^k \binom{k}{i}^2=\binom{2k}{k}$ , as desired.

Page

Toolbox

Search