Difference between revisions of "Combinatorial identity"
(There was an error in the Algebraic Proof of the hockey-stick identity, which I fixed.) |
Mathgeek2006 (talk | contribs) (→Proof) |
||
Line 52: | Line 52: | ||
<math>={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}</math>, which is equivalent to the desired result. | <math>={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}</math>, which is equivalent to the desired result. | ||
− | '''Combinatorial Proof''' | + | '''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 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. | ||
+ | |||
+ | '''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> | ||
==Another Identity== | ==Another Identity== |
Revision as of 18:19, 25 August 2011
Contents
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
.
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 1
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.
Combinatorial Proof 2
We can form a committee of size from a group of
people in
ways. Now we hand out the numbers
to
of the
people. We can divide this into
disjoint cases. In general, in case
,
, person
is on the committee and persons
are not on the committee. This can be done in
ways. Now we can sum the values of these
disjoint cases, getting
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.