Binomial coefficient

Elementary combinatorics: Factorial and binomial coefficient

Binomial coefficient

The binomial coefficient $\boldsymbol{n}$ over $\boldsymbol{k}$ , denoted $\binom{n}{k}$ , of two natural numbers $n$ and $k$ with $k\le n$ is defined as $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$

You never calculate a binomial coefficient by calculating the three factorials in the definition separately. The factorial properties allow you to strike out the larger of the two factorials in the denominator against the beginning of $n!$ . An example: $\begin{aligned}\binom{8}{3}&=\frac{8!}{3!\cdot 5!}\\[0.25cm] &=\frac{8\times 7\times 6\times \cancel{5}\times \cancel{4}\times \cancel{3}\times \cancel{2}\times \cancel{1}}{(3\times 2\times 1)\times(\cancel{5}\times \cancel{4}\times \cancel{3}\times \cancel{2}\times \cancel{1})}\\[0.25cm] &= \frac{8\times 7\times 6}{3\times 2\times 1}\\[0.25cm] &=8\times 7\\[0.25cm] &=56\end{aligned}$ In general: $\binom{n}{k}=\frac{n (n-1)\cdots (n-k+1)}{k!}$

As a generalisation of $\binom{n}{k}=\frac{n!}{k!\cdot (n-k)!}=\frac{n(n-1)\cdots (n-k+1)}{k!}$ one defines for numbers $x$ and $k\in\mathbb{N}$ $\binom{x}{k}=\frac{x (x-1)\cdots (x-k+1)}{k!}$ Then we have, for example, (do the math!): $\binom{-1}{k}=(-1)^k\qquad\text{and}\qquad \binom{k-1}{k}=0$ for all $k\in\mathbb{N}$ .

The number of ways in which one can choose $k$ things from a collection $n$ different objects without repetition (i.e., not putting back the chosen object in the original collection after each choice) and without taking care of the order of choice is equal to the binomial coefficient $\binom{n}{k}$ . Such a possible choice is called a combination. In short, we say that the number of combinations of $\boldsymbol{k}$ out of $\boldsymbol{n}$ is equal to $\binom{n}{k}$ . This jargon also explains the alternate notations $C^n_k$ and ${}^{n}C_{k}$ , as well as the name of the calculator button/function nCr to calculate the number of combinations of $r$ out of $n$ .

The number of ways in which one can choose $k$ things from a collection of $n$ different objects without repetition but taking care of the order of choice is equal to $\binom{n}{k}\cdot k! = \dfrac{n!}{(n-k)!}= n(n-1)\cdots (n-k+1)\text.$ We also call this the number of variations of $\boldsymbol{k}$ out of $\boldsymbol{n}$ .

The number of ways in which one can choose $k$ things from a collection of $n$ different objects where after each choice the chosen object is put back in the original collection and the order of selection does not play a role is equal to $\binom{n+k-1}{k}$ . We also call this the number of repeated combinations of $\boldsymbol{k}$ out of $\boldsymbol{n}$ .

For the sake of completeness we mention that the number of ways in which one can choose $k$ from a collection of $n$ different objects where after each after each choice the chosen object is put back in the original collection and the order of selection does plays a role is equal to $n^k$ . We also call this the number of repeated variations of $\boldsymbol{k}$ out of $\boldsymbol{n}$ .