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:

$$\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:

   $$\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:

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

   $$\quad = \frac {(n-1)!}{p! \; (n-p-1)!} + \frac {(n-1)!}{(p-1)! \; (n-p)!}$$

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

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

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

   $$\quad = \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.

The colored arrows show three different examples, namely:

$$\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:

$$(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:

$$(x+y)^2 = x^2+2xy+y^2$$

$$(x+y)^3 = 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$.

• For $n=0$, the equality is trivial.
• Assume that for some natural number $n$, the equality holds. Then we have:

  $$(x+y)^{n+1} = (x+y)(x+y)^n$$

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

  $$\quad = \overset{n}{\underset{k=0}{\sum}} \begin{pmatrix}n \\ k \end{pm... ...et{n}{\underset{k=0}{\sum}} \begin{pmatrix}n \\ k \end{pmatrix}\; x^k y^{n-k+1}$$

  $$\quad = \binom{n}{n} x^{n+1} + \overset{n-1}{\underset{k=0}{\sum}} \beg... ...derset{k=1}{\sum}} \begin{pmatrix}n \\ k \end{pmatrix}\; x^k y^{n-k+1} +y^{n+1}$$

  $$\quad =x^{n+1} + \overset{n}{\underset{k=1}{\sum}} \begin{pmatrix}n \\ ... ...derset{k=1}{\sum}} \begin{pmatrix}n \\ k \end{pmatrix}\; x^k y^{n-k+1} +y^{n+1}$$

  $$\quad = x^{n+1} + \overset{n}{\underset{k=1}{\sum}} \left[ \begin{pmat... ...nd{pmatrix} + \begin{pmatrix}n \\ k \end{pmatrix} \right] x^ky^{n+1-k} +y^{n+1}$$

  $$\quad = \binom{n+1}{0}x^{n+1} +\overset{n}{\underset{k=1}{\sum}} \binom{n+1}{k} x^ky^{n+1-k} +\binom{n+1}{n+1}y^{n+1}$$

  $$\quad = \overset{n+1}{\underset{k=0}{\sum}} \begin{pmatrix}n \\ k \end{pmatrix}\; x^k y^{n-k}.$$

  
  

$\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:

$$\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$