Symmetry Rule for Binomial Coefficients/Proof 2

Theorem

Let $n \in \Z_{>0}, k \in \Z$.

Then:

$\dbinom n k = \dbinom n {n - k}$

Proof

From the definition of Cardinality of Set of Subsets, $\dbinom n k$ is the number of subsets of cardinality $k$ of a set with cardinality $n$.

Let $S$ be a set with cardinality $n$.

Let $\powerset S$ denote the power set of $S$.

Let $\AA_k \subseteq \powerset S$ be the set of elements of $\powerset S$ which have cardinality $k$.

For every $T \in \AA_k$ there exists its relative complement:

$\relcomp S T \in \AA_{n - k}$

Define the mapping $f_k: \AA_k \to \AA_{n - k}$ as:

$\forall T \in \AA_k: \map f T = \relcomp S T$

From Relative Complement Mapping on Powerset is Bijection it follows that $f_k$ is a bijection.

By definition of set equivalence, that means:

$\card {A_k} = \card {A_{n - k} }$

That is, from the definition of Cardinality of Set of Subsets:

$\dbinom n k = \dbinom n {n - k}$

$\blacksquare$

Sources

• 1966: Richard A. Dean: Elements of Abstract Algebra ... (previous) ... (next): $\S 0.6$: Theorem $8: \ 3$