The binomial coefficient and nCr

We start with a definition:

Definition 1

Consider two natural numbers (including $0$ ) $n$ and $r$ , where $n\geq r$ . The binomial coefficient of $n$ and $r$ , denoted by

\left(\begin{array}{lll} n \\ r\end{array}\right)

is defined as

\left(\begin{array}{lll} n \\ r\end{array}\right)=\frac{n!}{r!\cdot(n-r)!}

(say "n choose r").

Another notation for the binomial coefficient is $nCr$ (say "n c r"). You can find this key on the calculator as well. In the last section we have seen the following:

Theorem 1

Consider $n$ objects arranged in a row, where $r$ objects are identical, and also the remaining $n-r$ objects are identical. The number of possible permutations of these objects that can be formed by rearranging the order of the objects in the row is

\left(\begin{array}{lll} n \\ r\end{array}\right)

Example 1

The number of words that can be formed by rearranging the letters of the word HHHTTHT is

\left(\begin{array}{lll} 7 \\ 4\end{array}\right)=\frac{7!}{4!\cdot (7-4)!}=\frac{7!}{4!\cdot 3!}=35

because the number of letters is $n=7$ and there are $k=4$ Hs. Of course we could also argue that there are $k=3$ Ts, and then we would get

\left(\begin{array}{lll} 7 \\ 3\end{array}\right)=\frac{7!}{3!\cdot (7-3)!}=\frac{7!}{3!\cdot 4!}=35

and indeed we get the same number of possibilities. Nothing else would make sense.

Here are some further properties of binomial coefficients:

Theorem 2

$\left(\begin{array}{lll} n \\ 0\end{array}\right)=1$
$\left(\begin{array}{lll} n \\ n\end{array}\right)=1$
$\left(\begin{array}{lll} n \\ 1\end{array}\right)=n$
$\left(\begin{array}{lll} n \\ n-1\end{array}\right)=n$
$\left(\begin{array}{lll} n \\ r\end{array}\right)=\left(\begin{array}{lll} n \\ n-r\end{array}\right)$

Exercise 1

Prove the statements above in two ways. First by using the definition of the binomial coefficient, and second by finding the corresponding number of permutations of a word with $n$ letters.

Solution

Using the definition of the binomial coefficient

$\left(\begin{array}{lll} n \\ 0\end{array}\right)=\frac{n!}{0!(n-0)!}=\frac{n!}{n!}=1$
$\left(\begin{array}{lll} n \\ n\end{array}\right)=\frac{n!}{n!(n-n)!}=\frac{n!}{n!}=1$
$\left(\begin{array}{lll} n \\ 1\end{array}\right)=\frac{n!}{1!(n-1)!}=\frac{n!}{(n-1)!}=n$
$\left(\begin{array}{lll} n \\ n-1\end{array}\right)=\frac{n!}{(n-1)!(n-(n-1))!}=\frac{n!}{(n-1)!}=n$
$\left(\begin{array}{lll} n \\ r\end{array}\right)=\frac{n!}{r!(n-r)!}\,$ and $\,\left(\begin{array}{lll} n \\ n-r\end{array}\right)=\frac{n!}{(n-r)!(n-(n-r))!}=\frac{n!}{(n-r)!\cdot r!}\,$ so the two expressions are the same!

Using number of permutations of a word with $n$ letters

For example, the word consists of the letters H and T, and let denote the number of H by $r$ .

$r=0$ , so no H, so all letters are the same, TTTTT. By rearranging the letters, we always get the same word. Thus, $\left(\begin{array}{lll} n \\ 0\end{array}\right)=1$
$r=n$ , so only Hs, so again all letters are the same, HHHHH. Thus, $\left(\begin{array}{lll} n \\ n\end{array}\right)=1$
$r=1$ , so one letter H, e.g. HTTTT. By rearranging the letters, we get $n$ possibilities (there are $n$ positions where we can place the $H$ : HTTTT, THTTT, TTHTT, ...). So $\left(\begin{array}{lll} n \\ 1\end{array}\right)=n$
$r=n-1$ , so $n-1$ letter H, e.g. HHHHT. Again, we get $\left(\begin{array}{lll} n \\ n-1\end{array}\right)=n$ .
$\left(\begin{array}{lll} n \\ r\end{array}\right)$ : number of words that can be formed if there are $r$ Hs in the word, and $n-r$ Ts.

$\left(\begin{array}{lll} n \\ n-r\end{array}\right)$ : number of words that can be formed if there are $n-r$ Hs in the word, and $r$ Ts.

These are different words (e.g. HHTTT and HHHTT), but clearly in both cases the number of possible permutations has to be the same (simply rename in the second case the letter H to T and the letter T to H).

There is a close relationship between the permutations of words consisting of two different letters and trees. Consider a word made of two letters, such as AABB. We already know that there are

\left(\begin{array}{lll} 4 \\ 2\end{array}\right)=6

permutations of the word. But what are these words? To find out, it is helpful to draw a tree as follows: As there are $4$ letters in the word, we draw $4$ generations of the tree, where on left the branch is always A and on the right branch is always B (or vice versa, it does not matter):

Every path from top to bottom traces out a word. If we follow all paths, we get all possible $4$ -letter words that can be formed with the letters A and B. There are $2^4=16$ such words (or paths).

Following the paths containing $2$ A and $2$ B, we can find out all the permutations of AABB (see figure above). There are

\left(\begin{array}{lll} 4 \\ 2\end{array}\right)=6

such words (or paths).

Or if we follow the paths containing $1$ A and $3$ B, we can find out all the permutations of ABBB. There are $\left(\begin{array}{lll} 4 \\ 1\end{array}\right)=4$ such words (or paths). And so on.