Difference between revisions of "Combinatorial identity"

m (fix format)
m (Examples)
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
==Vandermonde's Identity==
 
==Vandermonde's Identity==
 
Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>.
 
Vandermonde's Identity states that <math>\sum_{k=0}^r\binom mk\binom n{r-k}=\binom{m+n}r</math>, which can be proven combinatorially by noting that any combination of <math>r</math> objects from a group of <math>m+n</math> objects must have some <math>0\le k\le r</math> objects from group <math>m</math> and the remaining from group <math>n</math>.
 +
 +
===Video Proof===
 +
 +
https://www.youtube.com/watch?v=u1fktz9U9ig
 +
 +
~avn
 +
 
==Hockey-Stick Identity==
 
==Hockey-Stick Identity==
 
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.
 
For <math>n,r\in\mathbb{N}, n>r,\sum^n_{i=r}{i\choose r}={n+1\choose r+1}</math>.
Line 54: Line 61:
 
'''Combinatorial Proof 1'''
 
'''Combinatorial Proof 1'''
  
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Urns, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Urns, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.
+
Imagine that we are distributing <math>n</math> indistinguishable candies to <math>k</math> distinguishable children. By a direct application of Balls and Holes, there are <math>{n+k-1\choose k-1}</math> ways to do this. Alternatively, we can first give <math>0\le i\le n</math> candies to the oldest child so that we are essentially giving <math>n-i</math> candies to <math>k-1</math> kids and again, with Balls and Holes, <math>{n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}</math>, which simplifies to the desired result.
  
 
'''Combinatorial Proof 2'''
 
'''Combinatorial Proof 2'''
  
 
We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people.  We can divide this into <math>n-k+1</math> disjoint cases.  In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee.  This can be done in <math>\binom{n-x+1}{k}</math> ways.  Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath>
 
We can form a committee of size <math>k+1</math> from a group of <math>n+1</math> people in <math>{{n+1}\choose{k+1}}</math> ways. Now we hand out the numbers <math>1,2,3,\dots,n-k+1</math> to <math>n-k+1</math> of the <math>n+1</math> people.  We can divide this into <math>n-k+1</math> disjoint cases.  In general, in case <math>x</math>, <math>1\le x\le n-k+1</math>, person <math>x</math> is on the committee and persons <math>1,2,3,\dots, x-1</math> are not on the committee.  This can be done in <math>\binom{n-x+1}{k}</math> ways.  Now we can sum the values of these <math>n-k+1</math> disjoint cases, getting <cmath>{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.</cmath>
 +
 +
'''Combinatorial Proof 3'''
 +
 +
Think of the right hand side as picking <math>r</math> people from <math>m</math> men and <math>n</math> women. Think of the left hand side as picking <math>k</math> men from the <math>m</math> total men and picking <math>r-k</math> women from the <math>n</math> total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.
  
 
'''Algebraic Proof 2'''
 
'''Algebraic Proof 2'''
  
Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+(\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n)=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity. -- EVIN-
+
Apply the finite geometric series formula to <math>(1+x)</math>: <cmath>1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}</cmath> Then expand with the Binomial Theorem and simplify: <cmath>1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n</cmath> Finally, equate coefficients of <math>x^m</math> on both sides: <cmath>\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}</cmath> Since for <math>i<m</math>, <math>\binom{i}{m}=0</math>, this simplifies to the hockey stick identity.
  
 
==Another Identity==
 
==Another Identity==
Line 83: Line 94:
 
* [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]
 
* [http://artofproblemsolving.com/wiki/index.php/2015_AIME_I_Problems/Problem_12 2015 AIME I Problem 12]
 
* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]
 
* [https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems/Problem_7 2020 AIME I Problem 7]
 +
* [https://artofproblemsolving.com/wiki/index.php/2016_AMC_10A_Problems/Problem_20 2016 AMC 10A Problem 20]
  
 
==See also==
 
==See also==

Latest revision as of 00:54, 17 January 2021

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

Video Proof

https://www.youtube.com/watch?v=u1fktz9U9ig

~avn

Hockey-Stick Identity

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

[asy] int chew(int n,int r){  int res=1;  for(int i=0;i<r;++i){   res=quotient(res*(n-i),i+1);   }  return res;  } for(int n=0;n<9;++n){  for(int i=0;i<=n;++i){   if((i==2 && n<8)||(i==3 && n==8)){    if(n==8){label(string(chew(n,i)),(11+n/2-i,-n),p=red+2.5);}    else{label(string(chew(n,i)),(11+n/2-i,-n),p=blue+2);}    }   else{    label(string(chew(n,i)),(11+n/2-i,-n));    }   }  } [/asy]

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 is 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 1

Imagine that we are distributing $n$ indistinguishable candies to $k$ distinguishable children. By a direct application of Balls and Holes, 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 Holes, ${n+k-1\choose k-1}=\sum_{i=0}^n{n+k-2-i\choose k-2}$, which simplifies to the desired result.

Combinatorial Proof 2

We can form a committee of size $k+1$ from a group of $n+1$ people in ${{n+1}\choose{k+1}}$ ways. Now we hand out the numbers $1,2,3,\dots,n-k+1$ to $n-k+1$ of the $n+1$ people. We can divide this into $n-k+1$ disjoint cases. In general, in case $x$, $1\le x\le n-k+1$, person $x$ is on the committee and persons $1,2,3,\dots, x-1$ are not on the committee. This can be done in $\binom{n-x+1}{k}$ ways. Now we can sum the values of these $n-k+1$ disjoint cases, getting \[{{n+1}\choose {k+1}} ={{n}\choose{k}}+{{n-1}\choose{k}}+{{n-2}\choose{k}}+\hdots+{{k+1}\choose{k}}+{{k}\choose{k}}.\]

Combinatorial Proof 3

Think of the right hand side as picking $r$ people from $m$ men and $n$ women. Think of the left hand side as picking $k$ men from the $m$ total men and picking $r-k$ women from the $n$ total women. The left hand side and right hand side are the same, thus Vandermonde's identity must be true.

Algebraic Proof 2

Apply the finite geometric series formula to $(1+x)$: \[1+(1+x)+(1+x)^2+...+(1+x)^n=\frac{(1+x)^{n+1}-1}{(1+x)-1}\] Then expand with the Binomial Theorem and simplify: \[1+(1+x)+(1+2x+x^2)+...+ \left (\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+...+\binom{n}{n-1}x^{n-1}+\binom{n}{n}x^n \right )=\binom{n+1}{1}+\binom{n+1}{2}x+...+\binom{n+1}{n+1}x^n\] Finally, equate coefficients of $x^m$ on both sides: \[\binom{0}{m}+\binom{1}{m}+\binom{2}{m}+...+\binom{n}{m}=\binom{n+1}{m+1}\] Since for $i<m$, $\binom{i}{m}=0$, this simplifies to the hockey stick identity.

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.

Proof 2

This is a special case of Vandermonde's identity, in which we set $m=n$ and $r=m$.


Examples

See also

Invalid username
Login to AoPS