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$.

\(\ds \binom n k\) \(=\) \(\ds \frac {n!} {k! \paren {n - k}!}\)
\(\ds \) \(=\) \(\ds \frac {n!} {\paren {n - k}! k!}\)
\(\ds \) \(=\) \(\ds \frac {n!} {\paren {n - k}! \paren {n - \paren {n - k} } !}\)
\(\ds \) \(=\) \(\ds \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 $\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$


Informal Proof

If we choose $k$ objects from $n$, then we leave $n - k$ objects.

Hence for every choice of $k$, we are also making the same choice of $n - k$.

Hence the number of choices of $k$ objects is the same as the number of choices of $n - k$ objects.

Hence the result.

$\blacksquare$


Examples

$11$ choose $8$

Consider the binomial coefficient $\dbinom {11} 8$.

This can be calculated as:

$\dbinom {11} 8 = \dfrac {11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4} {8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}$

which is unwieldy.

Or we can use the Symmetry Rule for Binomial Coefficients, and say:

$\dbinom {11} 8 = \dbinom {11} {11 - 8} = \dbinom {11} 3$

and calculate it as:

$\dbinom {11} 3 = \dfrac {11 \times 10 \times 9} {3 \times 2 \times 1} = \dfrac {990} 6 = 165$

which is far less trouble.


$8$ choose $6$

Let $N$ be the number of ways a team of $6$ people may be selected from a pool of $8$.

Then:

$N = 28$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Symmetry_Rule_for_Binomial_Coefficients&oldid=626767"