# Cardinality of Set of Subsets

## Contents

## 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 1

For each $X \subseteq \N_n$ and $Y \subseteq S$, let $B \left({X, Y}\right)$ be the set of all bijections from $X$ onto $Y$.

Let $\Bbb S$ be the set of all subsets of $S$ with $m$ elements.

By Cardinality of Power Set of Finite Set and Cardinality of Subset of Finite Set, $\Bbb S$ is finite, so let $s = \left|{\Bbb S}\right|$.

Let $\beta: B \left({\N_n, S}\right) \to \Bbb S$ be the mapping defined as $\forall f \in B \left({\N_n, S}\right): \beta \left({f}\right) = f \left({\N_m}\right)$.

For each $Y \in \Bbb S$, the mapping:

- $\Phi_Y: \beta^{-1} \left({Y}\right) \to B \left({\N_m, Y}\right) \times B \left({\N_n - \N_m, S - Y}\right)$

defined as:

- $\Phi_Y \left({f}\right) = \left({f_{\N_m}, f_{\N_n - \N_m}}\right)$

is also (clearly) a bijection.

By Cardinality of Set of Bijections:

- $\left|{B \left({\N_m, Y}\right)}\right| = m!$

and:

- $\left|{B \left({\N_n - \N_m, S - Y}\right)}\right| = \left({n - m}\right)!$

So by Cardinality of Cartesian Product:

- $\left|{\beta^{-1} \left({Y}\right)}\right| = m! \left({n - m}\right)!$

It is clear that $\left\{{\beta^{-1} \left({Y}\right): Y \in \Bbb S}\right\}$ is a partition of $B \left({\N_n, S}\right)$.

Therefore by Number of Elements in Partition:

- $\left|{B \left({\N_n, S}\right)}\right| = m! \left({n - m}\right)! s$

Consequently, as $\left|{B \left({\N_n, S}\right)}\right| = n!$ by Cardinality of Set of Bijections, it follows that:

- $m! \left({n - m}\right)! s = n!$

and the result follows.

$\blacksquare$

## Proof 2

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$

## Proof 3

Let $\N_n$ denote the set $\set {1, 2, \ldots, n}$.

Let $\struct {S_n, \circ}$ denote the symmetric group on $\N_n$.

Let $r \in \N: 0 < r \le n$.

Let $B_r$ denote the set of all subsets of $\N_n$ of cardinality $r$:

- $B_r := \set {S \subseteq \N_n: \card S = r}$

Let $*$ be the mapping $*: S_n \times B_r \to B_r$ defined as:

- $\forall \pi \in S_n, \forall S \in B_r: \pi * B_r = \pi \sqbrk S$

where $\pi \sqbrk S$ denotes the image of $S$ under $\pi$.

From Group Action of Symmetric Group on Subset it is established that $*$ is a group action.

The stabilizer of any $U \in B_r$ is the set of permutations on $\N_n$ that fix $U$.

Let $U = \set {1, 2, \ldots, r}$.

So:

- $\tuple {a_1, a_2, \ldots, a_r}$ can be any one of the $r!$ permutations of $1, 2, \ldots, r$
- $\tuple {a_{r + 1}, a_{r + 2}, \ldots, _n}$ can be any one of the $\paren {n - r}!$ permutations of $r + 1, r + 2, \ldots, n$.

Thus:

- $\order {\Stab U} = r! \paren {n - r}!$

From Group Action of Symmetric Group on Subset is Transitive:

- $B_r = \Orb U$

and so:

- $\card {B_r} = \card {\Orb U}$

From the Orbit-Stabilizer Theorem:

- $\card {\Orb U} = \dfrac {\order {S_n} } {\order {\Stab U} } = \dfrac {n!} {r! \paren {n - r}!}$

But $\card {B_r}$ is the number of subsets of $\N_n$ of cardinality $r$.

Hence the result.

$\blacksquare$

## Proof 4

The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

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

### Basis for the Induction

$\map P 1$ is the case:

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

\(\displaystyle {}^m C_1\) | \(=\) | \(\displaystyle \begin {cases} 1 & : m = 0 \text { or } m = 1 \\ 0 & : \text {otherwise} \end {cases}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \dfrac {1!} {0! \paren {1 - 0}!}\) | for $m = 0$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \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:

- ${}^m C_k = \dfrac {k!} {m! \paren {k - m}!}$

from which it is to be shown that:

- ${}^m C_{k + 1} = \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)

\(\displaystyle {}^m C_{k + 1}\) | \(=\) | \(\displaystyle {}^m C_k + {}^{m - 1} C_k\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \binom k m + \binom k {m - 1}\) | Induction Hypothesis | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \binom {k + 1} m\) | Pascal's Rule |

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}: {}^m C_n = \dfrac {n!} {m! \paren {n - m}!}$

## Also see

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: I. Basic Concepts*... (previous) ... (next): Introduction $\S 1$: Operations on Sets - 1964: A.M. Yaglom and I.M. Yaglom:
*Challenging Mathematical Problems With Elementary Solutions: Volume I*... (previous) ... (next): Problems - 1965: J.A. Green:
*Sets and Groups*... (previous) ... (next): $\S 2.3$. Partitions: Example $35$ - 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Exercise $5.4$ - 1966: Richard A. Dean:
*Elements of Abstract Algebra*... (previous) ... (next): $\S 0.6$: Theorem $8: \ 3$ - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.2$: Sets: Exercise $4$ - 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $35$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $35$