Difference between revisions of "Combinatorial identity"
m (double-dollars are _so_ deprecated ;) (also, Another Identity needs a name!)) |
(asy code that doesn't work but might work in the future) |
||
Line 1: | Line 1: | ||
==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>. | ||
+ | |||
+ | <asy> | ||
+ | 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); | ||
+ | } | ||
+ | } | ||
+ | </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 are highlighted, a hockey-stick shape is revealed. | 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=== | ===Proof=== |
Revision as of 08:37, 12 March 2009
Contents
[hide]Hockey-Stick Identity
For .
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 .
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.