# Cardinality of Set of Subsets/Proof 2

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

- 1964: A.M. Yaglom and I.M. Yaglom:
*Challenging Mathematical Problems With Elementary Solutions: Volume $\text { I }$*... (previous) ... (next): Problems - 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\text {3-1}$ Permutations and Combinations: Theorem $\text {3-2}$ - 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients