next up previous contents
Next: Selections Up: Induction and Counting Previous: Recursive Definitions   Contents

Selection and Binomial Coefficients

We define a set of polynomials for $ m \in \mathbb{N}_0$ as

$\displaystyle x^{\underline{m}} = x (x-1) (x-2) \dots (x-m+1),
$

which is pronounced ``$ x$ to the $ m$ falling''. We can do this recursively by $ x^{\underline{0}} = 1$ and $ x^{\underline{m}} = (x - m + 1)
x^{\underline{m-1}}$ for $ m > 0$. We also define ``$ x$ to the $ m$ rising'' by

$\displaystyle x^{\overline{m}} = x (x+1) (x+2) \dots (x+m-1).
$

We further define $ \binom{x}{m}$ (read ``$ x$ choose $ m$'') by

$\displaystyle \binom{x}{m} = \frac{x^{\underline{m}}}{m!}.$    

It is also convienient to extend this definition to negative $ m$ by $ \binom{x}{m} = 0$ if $ m < 0$, $ m \in \mathbb{Z}$. By fiddling a little, we can see that for $ n \in \mathbb{N}$, $ n \ge m$ we have:

$\displaystyle \binom{n}{m} = \frac{n!}{m! (n-m)!}.$    

Proposition 8.5.1   The number of $ k$-subsets of a given $ n$-set is $ \binom{n}{k}$.

Proof. We can choose the first element to be included in our $ k$-subset in $ n$ ways, then then next in $ n-1$ ways, down to the $ k^{\text{th}}$ which can be chosen in $ n-k + 1$ ways. However, ordering of the $ k$-subset is not important (at the moment), so divide $ \frac{n^{\underline{k}}}{k!}$ to get the answer. $ \qedsymbol$

Theorem 8.5.2 (The Binomial Theorem)   For $ a$ and $ b \in \mathbb{R}$, $ n \in \mathbb{N}_0$ then

$\displaystyle \left( a + b \right)^n = \sum_k \binom{n}{k} a^k b^{n-k}.$    

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

Proof. $ (a+b)^n = (a+b) (a+b) \dots (a+b)$, so the coefficient of $ a^k b^{n-k}$ is the number of $ k$-subsets of an $ n$-set -- so the coefficient is $ \binom{n}{k}$. $ \qedsymbol$

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

$\displaystyle \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$    

$ \qedsymbol$

There are a few conseqences of the binomial expansion.
  1. For $ m,n \in \mathbb{N}_0$ and $ n \ge m$, $ \binom{n}{m} \in \mathbb{N}_0$ so $ m!$ divides the product of any $ m$ consecutive integers.
  2. Putting $ a=b=1$ in the binomial theorem gives $ 2^n =
\sum_k \binom{n}{k}$ -- so the number of subsets of an $ n$-set is $ 2^n$. There are many proofs of this fact. An easy one is by induction on $ n$. Write $ S_n$ for the total number of subsets of an $ n$-set. Then $ S_0 = 1$ and for $ n > 0$, $ S_n = 2 S_{n-1}$. (Pick a point in the $ n$-set and observe that there are $ S_{n-1}$ subsets not containing it and $ S_{n-1}$ subsets containing it.
  3. $ (1-1)^n = 0 = \sum_k \binom{n}{k} (-1)^k$ -- 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 $ p$ is prime then $ a^p \equiv a \pmod{p}$ for all $ a \in \mathbb{N}_0$.

Proof. It is done by induction on $ a$. It is obviously true when $ a = 0$, so take $ a > 0$ and assume the theorem is true for $ a-1$. Then

$\displaystyle a^p$ $\displaystyle = \left( \left( a-1 \right) + 1 \right)^p$    
  $\displaystyle \equiv \left( a-1 \right)^p + 1 \mod{p}$   as $ \binom{p}{k} \equiv
 0 \pmod{p}$ unless $ k=0$ or $ k=p$    
  $\displaystyle \equiv a - 1 + 1 \mod{p}$    
  $\displaystyle \equiv a \mod{p}$    

$ \qedsymbol$



Subsections
next up previous contents
Next: Selections Up: Induction and Counting Previous: Recursive Definitions   Contents
root 2002-06-10