# 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 13: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.