Cardinality of Set of Subsets/Proof 4
Jump to navigation
Jump to search
Theorem
Let $S$ be a set such that $\card S = n$.
Let $m \le n$.
Then the number of subsets $T$ of $S$ such that $\card T = m$ is:
- $\dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$
Proof
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
- $\dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$
Basis for the Induction
$\map P 1$ is the case:
\(\ds \dbinom 1 m\) | \(=\) | \(\ds \dfrac {1!} {1! \paren {m - 1}!}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \begin {cases} 1 & : m = 0 \text { or } m = 1 \\ 0 & : \text {otherwise} \end {cases}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {1!} {0! \paren {1 - 0}!}\) | for $m = 0$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {1!} {1! \paren {1 - 1}!}\) | for $m = 1$ |
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
- $\dbinom k m = \dfrac {k!} {m! \paren {k - m}!}$
from which it is to be shown that:
- $\dbinom {k + 1} m = \dfrac {\paren {k + 1}!} {m! \paren {k + 1 - m}!}$
Induction Step
This is the induction step:
The number of ways to choose $m$ elements from $k + 1$ elements is:
- the number of ways to choose $m$ elements elements from $k$ elements (deciding not to select the $k + 1$th element)
added to:
- the number of ways to choose $m - 1$ elements elements from $k$ elements (after having selected the $k + 1$th element for the $n$th selection)
\(\ds \dbinom {k + 1} m\) | \(=\) | \(\ds \binom k m + \binom k {m - 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {k!} {m! \paren {k - m}!} + \dfrac {k!} {\paren {m - 1}! \paren {k - m + 1}!}\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac {\paren {k + 1}!} {m! \paren {k - m + 1}!}\) | after algebra | |||||||||||
\(\ds \) | \(=\) | \(\ds \binom {k + 1} m\) |
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall n \in \Z_{>0}: \dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-1}$ Permutations and Combinations: Exercise $4$