Symmetry Rule for Binomial Coefficients

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Then:

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

where $\dbinom n k$ is a binomial coefficient.


Complex Numbers

For all $z, w \in \C$ such that it is not the case that $z$ is a negative integer and $w$ an integer:

$\dbinom z w = \dbinom z {z - w}$


Proof 1

Follows directly from the definition of binomial coefficient, as follows.

If $k < 0$ then $n - k > n$.

Similarly, if $k > n$, then $n - k < 0$.

In both cases:

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


Let $0 \le k \le n$.

\(\displaystyle \binom n k\) \(=\) \(\displaystyle \frac {n!} {k! \paren {n - k}!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {n!} {\paren {n - k}! k!}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac {n!} {\paren {n - k}! \paren {n - \paren {n - k} } !}\)
\(\displaystyle \) \(=\) \(\displaystyle \binom n {n - k}\)

$\blacksquare$


Proof 2

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 $\mathcal A_k \subseteq \powerset S$ be the set of elements of $\powerset S$ which have cardinality $k$.

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

$\relcomp S T \in \mathcal A_{n - k}$

Define the mapping $f_k: \mathcal A_k \to \mathcal A_{n - k}$ as:

$\forall T \in \mathcal A_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