Difference between revisions of "Combinatorial identity"
(asy code that doesn't work but might work in the future) |
(yay! hockey-stick picture!) |
||
Line 3: | Line 3: | ||
<asy> | <asy> | ||
− | int | + | int chew(int n,int r){ |
int res=1; | int res=1; | ||
− | for(int i=0;i<r; | + | for(int i=0;i<r;++i){ |
− | res=res*(n-i) | + | res=quotient(res*(n-i),i+1); |
} | } | ||
return res; | return res; | ||
} | } | ||
− | for(int n=0;n< | + | for(int n=0;n<9;++n){ |
− | for(int i=0;i<=n;i++){ | + | for(int i=0;i<=n;++i){ |
− | label(string( | + | 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)); | ||
+ | } | ||
} | } | ||
} | } |
Revision as of 15:19, 12 March 2009
Contents
Hockey-Stick Identity
For .
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 .
Base Case
Let .
.
Inductive Step
Suppose, for some ,
.
Then
.
Algebraic Proof
It can also be proven algebraically with Pascal's Identity, .
Note that
, which is equivalent to the desired result.
Combinatorial Proof
Imagine that we are distributing indistinguishable candies to
distinguishable children. By a direct application of Balls and Urns, there are
ways to do this. Alternatively, we can first give
candies to the oldest child so that we are essentially giving
candies to
kids and again, with Balls and Urns,
, which simplifies to the desired result.
Vandermonde's Identity
Vandermonde's Identity states that , which can be proven combinatorially by noting that any combination of
objects from a group of
objects must have some
objects from group
and the remaining from group
.
Another Identity
Hat Proof
We have different hats. We split them into two groups, each with k hats: then we choose
hats from the first group and
hats from the second group. This may be done in
ways. Evidently, to generate all possible choices of
hats from the
hats, we must choose
hats from the first
and the remaining
hats from the second
; the sum over all such
is the number of ways of choosing
hats from
. Therefore
, as desired.