next up previous contents
Next: Countable sets Up: Elementary combinatorics Previous: Surjections   Contents

Combinations

Proposition 7.2.10   Let $ E$ be a finite set such that $ \vert E\vert=n$. If $ 0 \leq p \leq n$, the number of subsets $ A$ of $ E$ such that $ \vert A\vert=p$ is equal to the number $ \binom{n}{p}$ defined by:

$\displaystyle \binom{n}{p}=\frac {n!}{p! \; (n-p)!}$    

In particular, we have:
(i)
$ \binom{n}{0}=1$; there exists only one possibility to choose 0 element from a set (you don't choose anything!).
(ii)
$ \binom{n}{1}=n$; you have $ n$ different choices for a single element.

Proposition 7.2.11   Let $ n$ and $ p$ be two natural numbers such that $ 0 \leq p \leq n$. Then we have:
  1. $ \binom{n}{p}=\binom{n}{n-p}=$;
  2. $ \binom{n}{p}=\binom{n-1}{p}+\binom{n-1}{p-1}$.

Proof.     
  1. We replace into the definition:

    $\displaystyle \binom{n}{n-p}= \frac {n!}{(n-p)! \; [n-(n-p)]!} = \frac {n!}{p! \; (n-p)!}=\binom{n}{p}.$    

  2. We begin from the right-hand side:

    $\displaystyle \binom{n-1}{p}+\binom{n-1}{p-1}$ $\displaystyle = \frac {(n-1)!}{p! \; (n-1-p)!} + \frac {(n-1)!}{(p-1)! \; [(n-1)-(p-1)]!}$    
    $\displaystyle \quad$ $\displaystyle = \frac {(n-1)!}{p! \; (n-p-1)!} + \frac {(n-1)!}{(p-1)! \; (n-p)!}$    
    $\displaystyle \quad$ $\displaystyle = \frac {(n-p)[(n-1)!]}{p! \; (n-p)[(n-p-1)!]} + \frac {p[(n-1)!]}{p[(p-1)!] \; (n-p)!}$    
    $\displaystyle \quad$ $\displaystyle = \frac {(n-p+p)[(n-1)!]}{p! \; (n-p)!}$    
    $\displaystyle \quad$ $\displaystyle = \frac {n!}{p! \; (n-p)!}$    
    $\displaystyle \quad$ $\displaystyle = \binom{n}{n-p}.$    

$ \qedsymbol$

This last property has a nice presentation, called Pascal's triangle (note that it can be extended infinitely):

Figure 3: Pascal's triangle.
\begin{figure}
\centering
\mbox{\epsfig{file=PascalTriangle.eps, height=6cm}}
\end{figure}

The colored arrows show three different examples, namely:

$\displaystyle \begin{matrix}
 \text{in red} & \binom{3}{1}+\binom{3}{2}=\binom{...
...}\\  
 \text{in purple} & \binom{4}{2}+\binom{4}{3}=\binom{5}{3}.
 \end{matrix}$    

Theorem 7.2.12 (Newton's Binomial Formula)   For any $ x,y \in \mathbb{Z}$ and $ n \in \mathbb{N}$, the following holds:

$\displaystyle (x+y)^n = \overset{n}{\underset{k=0}{\sum}} \begin{pmatrix}n \\  ...
...et{n}{\underset{k=0}{\sum}} \begin{pmatrix}n \\  k \end{pmatrix}\; x^{n-k} y^k.$    

This is te generalization of well known formulas:

$\displaystyle (x+y)^2$ $\displaystyle = x^2+2xy+y^2$    
$\displaystyle (x+y)^3$ $\displaystyle = x^3+3x^2y+3xy^2+y^3$    

and so on. Compare the coefficients of these developments (together with the coeeficients in $ (x+y)^0$ and $ (x+y)^1$) with the rows of Pascal's triangle).

Proof. By induction on $ n$. $ \qedsymbol$

Corollary 7.2.13   Let $ A$ be a finite set such that $ \vert A\vert=n$. Then $ \vert\mathcal{P}(A)\vert=2^n$.

Proof. We have:

$\displaystyle \vert\mathcal{P}(A)\vert=\underbrace{\binom{n}{0}}_{\begin{matrix...
... the}\\  \text{subsets with} \\  \text{$n$\ elements}\end{matrix}}=(1+1)^n=2^n.$    

$ \qedsymbol$


next up previous contents
Next: Countable sets Up: Elementary combinatorics Previous: Surjections   Contents
root 2002-06-10