Difference between revisions of "Combinatorial identity"
(yay! hockey-stick picture!) |
Thomaslang (talk | contribs) (→Hockey-Stick Identity) |
||
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>. |
Revision as of 14:38, 3 August 2010
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.