** Next:** Special Sequences of Integers
** Up:** Selection and Binomial Coefficients
** Previous:** Selections
** Contents**

*Proof*.
For: choosing a

-subset is the same as choosing an

-subset to
reject.

*Proof*.
This is trivial if

or

, so assume

and

.
Choose a special element in the

-set. Any

-subset will either contain
this special element (there are

such) or not contain it
(there are

such).

In fact

*Proof*.
Trivial if

, so let

. Both sides are polynomials of degree

and are equal on all elements of

and so are equal as polynomials
as a consequence of the Fundamental Theorem of Algebra. This is
the ``polynomial argument''.

This can also be proved from the definition, if you want to.

*Proof*.
If

or

then both sides are zero. Assume

.
Assume

(the general case follows by the polynomial argument).
This is ``choosing a

-subset contained in an

-subset of a

-set''.

*Proof*.
We may assume

and

. This is ``choosing a

-team
and its captain''.

*Proof*.
For

and so on.

A consequence of this is that
, which is obtained by multiplying
the previous result by . This can be used to sum
.

*Proof*.
We can replace

by

and

by

and so we may assume that

. So we have to prove:

Take an

-set and split it into an

-set and an

-set. Choosing
an

-subset amounts to choosing a

-subset from the

-set and an

-subset from the

-set for various

.

** Next:** Special Sequences of Integers
** Up:** Selection and Binomial Coefficients
** Previous:** Selections
** Contents**
root
2002-06-10