Next: Selections Up: Induction and Counting Previous: Recursive Definitions   Contents

# Selection and Binomial Coefficients

We define a set of polynomials for as

which is pronounced  to the falling''. We can do this recursively by and for . We also define  to the rising'' by

We further define (read  choose '') by

It is also convienient to extend this definition to negative by if , . By fiddling a little, we can see that for , we have:

Proposition 8.5.1   The number of -subsets of a given -set is .

Proof. We can choose the first element to be included in our -subset in ways, then then next in ways, down to the which can be chosen in ways. However, ordering of the -subset is not important (at the moment), so divide to get the answer.

Theorem 8.5.2 (The Binomial Theorem)   For and , then

There are many proofs of this fact. We give one and outline a second.

Proof. , so the coefficient of is the number of -subsets of an -set -- so the coefficient is .

Proof. This can also be done by induction on , using the fact that

There are a few conseqences of the binomial expansion.
1. For and , so divides the product of any consecutive integers.
2. Putting in the binomial theorem gives -- so the number of subsets of an -set is . There are many proofs of this fact. An easy one is by induction on . Write for the total number of subsets of an -set. Then and for , . (Pick a point in the -set and observe that there are subsets not containing it and subsets containing it.
3. -- so in any finite set the number of subsets of even sizes equals the number of subsets of odd sizes.
It also gives us another proof of Fermat's Little Theorem: if is prime then for all .

Proof. It is done by induction on . It is obviously true when , so take and assume the theorem is true for . Then

 as unless or

Subsections

Next: Selections Up: Induction and Counting Previous: Recursive Definitions   Contents
root 2002-06-10