Cardinality of Set of Subsets/Proof 2

From ProofWiki
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:

${}^m C_n = \dfrac {n!} {m! \paren {n - m}!}$


Proof

Let ${}^m C_n$ be the number of subsets of $m$ elements of $S$.

From Number of Permutations, the number of $m$-permutations of $S$ is:

${}^m P_n = \dfrac {n!} {\paren {n - m}!}$

Consider the way ${}^m P_n$ can be calculated.

First one makes the selection of which $m$ elements of $S$ are to be arranged.

This number is ${}^m C_n$.

Then for each selection, the number of different arrangements of these is $m!$, from Number of Permutations.

So:

\(\displaystyle m! \cdot {}^m C_n\) \(=\) \(\displaystyle {}^m P_n\) Product Rule for Counting
\(\displaystyle \) \(=\) \(\displaystyle \frac {n!} {\paren {n - m}!}\) Number of Permutations
\(\displaystyle \leadsto \ \ \) \(\displaystyle {}^m C_n\) \(=\) \(\displaystyle \frac {n!} {m! \paren {n - m}!}\) Product Rule for Counting

$\blacksquare$


Sources