# Binomial Coefficient

**Binomial coefficients** are a family of positive integers that occur as coefficients in the binomial theorem. Binomial coefficients have been known for centuries, but they're best known from Blaise Pascal's work circa 1640. Below is a construction of the first 5 rows of Pascal's triangle.

\[1\\ 1\quad 1\\ 1\quad 2 \quad 1\\ 1\quad 3 \quad 3 \quad 1\\ 1\quad 4 \quad 6 \quad 4 \quad 1\\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1\\ \cdots\]

In mathematics, binomial coefficients are represented as \(\binom{a}{b}\), where \(a\) is the \((a+1)^{\text{th}}\) row, and \(b\) is the \((b+1)^{\text{th}}\) number in that row, counting from the left, acting as an index. That is under the pretense that first row is usually considered to be the \(0^{\text{th}}\) row, which is what we will be assuming as well. For example, the \(2^{\text{nd}}\) number in the \(4^{\text{th}}\) row is represented as \(\binom{3}{1} = 3\). Binomial coefficients, which are in the form \(\binom{a}{b}\), are equal to the number of ways there are to choose \(b\) objects from a set of \(a\) objects.

## Definition

The formula to calculate a binomial coefficient \(\binom{n}{k}\) is

\[\binom{n}{k}=\frac{n!}{k!(n-k)!}. \ _\square\]

## Calculate the value of \( \dbinom{7}{3} \).

We can use the formula \( \binom{n}{k}=\frac{n!}{k!(n-k)!}\) to calculate the value of \( \binom{7}{3} \):

\[ \dbinom{7}{3} = \frac{7! }{3! \times (7-3)!} = \frac{5040}{6 \times 24} = 35. \ _\square\]

## Calculate the value of \( \dbinom{8}{4} \).

We can use the formula \( \binom{n}{k}=\frac{n!}{k!(n-k)!}\) to calculate the value of \( \binom{8}{4} \):

\[ \dbinom{8}{4} = \frac{8! }{4! \times (8-4)!} = \frac{40320}{24 \times 24} = 70. \ _\square\]

Compute \(\dbinom{9}{2} + \dbinom{8}{3}\).

**Notation**: \( \binom MN \) denotes the binomial coefficient, \( \binom MN = \frac{M!}{N!(M-N)!} \).

Three numbers, \(x, y, z \in \mathbb{N}\) are chosen at random such that \(1\leq x, y, z \leq 10\). What is the probability that their product is divisible by 9?

What this question is really asking is "how many \(x, y,\) and \(z\) can be chosen so that, combined, \(xyz\) has a power of \(3\) which is \(\geq 2\)?" It seems our best bet is to factorize each number from \(1\) to \(10\).

\[1, ~2, ~3, ~2^2, ~5, ~2\cdot3, ~7, ~2^3, ~3^2, ~2\cdot5.\]

Our instincts tell us that it may be easier to count the numbers that are not divisible by 9, and then subtract that value from the total numbers we can make. Following this logic, we build two cases:

Case 1: the highest power of \(3\) that divides \(xyz\) is \(3^0 = 1\).

There are \(7\) numbers in the interval that are not divisible by \(3\), and we want to choose \(3\) of them. Thus, for this case, all we need to calculate is \(\binom{7}{3} = 35\).

Case 2: the highest power of \(3\) that divides \(xyz\) is \(3^1 =3\).

There are \(2\) numbers in the given interval which have a highest power of \(3\) with magnitude \(1\). We can choose only one of these for our variables. The other two variables must come from the set we considered in case \(1\). So, we have to calculate \(\binom{2}{1} \cdot \binom{7}{2} = 42\). Thus, we have a total of \(35+42=77\) numbers which are \(\textbf{not}\) divisible by \(9\).Now, we recognize that there are \(\binom{10}{3} = 120\) total combinations of \(3\) choices of numbers from \(1\) to \(10\). Thus \(120-42-35=43\) numbers formed in this manner divide \(9\). Hence, the probability is \(\dfrac{43}{120}\). \(_\square\)

How many 3-digit numbers can be formed by using 1,2,3,4,5 without repetition of digits?

Here making a 3-digit number is equivalent to filling 3 places with the five numbers.

Places= _ _ _. And there are five numbers.So, Number of ways of filling all the three places = \(\binom{5}{3} = \frac{5!}{(5-3)! 3!} = 60.\)

Hence, the total possible 3-digit numbers from 5 numbers is 60.

\[ \large \dfrac{2^{903}}{ \displaystyle \sum_{n=0}^{451} \binom{903}n } = \, ? \]

**Notation**: \( \binom MN \) denotes the binomial coefficient, \( \binom MN = \frac{M!}{N!(M-N)!} \).

## Properties of Binomial Coefficients

Extracted from mathematician Blaise Pascal's famous triangle, binomial coefficients have several elegant properties. Sure, they're useful, often necessary, in combinatorial analysis, but they're much more than that. Some properties make use of symmetry, some deal with expansion, but they all can be proved rather intuitively. We start by looking at binomial coefficients in their most raw form: in Pascal's triangle.

\[1\] \[1\quad 1\] \[1\quad 2 \quad 1\] \[1\quad 3 \quad 3 \quad 1\] \[1\quad 4 \quad 6 \quad 4 \quad 1\] \[1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1\] \[...\]

From the above diagram, we can see that the basic rule of construction is

\[\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1} .\]

\[\displaystyle \begin{eqnarray} \binom{n}{k} + \binom{n}{k+1} & = & \frac{n!}{k!((n-k)!)} + \frac{n!}{(k+1)!(n-(k+1))!} \\ & = & \frac{(k+1)n!+(n-k)n!}{(k+1)!(n-k)!} \\ & = & \frac{(n+1)!}{(k+1)!(n-k)!} \\ & = & \binom{n+1}{k+1} \end{eqnarray}\]

Or, in other terms, the sum of two adjacent binomial coefficients is equal to the one "below" it, assuming Pascal's triangle is produced in the equilateral-triangle-like shape shown above. Another important identity is

\[\binom{n}{k} = \binom{n}{n-k},\]

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

which is the statement that each row of Pascal's triangle is symmetric in either one of two ways. It is either palindromic and centrally oriented (for even \(n\)), or palindromic and "mirrored," where all the numbers on one side of the triangle are replicated on the other side (for odd \(n\)).

The sum of binomial coefficients across a fixed row \(n\) is equal to a power of two. Indeed,

\[\sum_{k=0}^{n} \binom{n}{k} = 2^n,\]

which can easily be shown by

\[2^n = (1+1)^n = \binom{n}{0}(1)^n(1)^0 + \binom{n}{1}(1)^{n-1}(1)^1 + \cdots + \binom{n}{n}(1)^0(1)^{n} = \sum_{k=0}^{n} \binom{n}{k}.\]

Along similar lines, I'll demonstrate a more general fascinating property concerning a weighted sum of binomial coefficients with respect to their indices:

\[\sum_{k=0}^{n} k\binom{n}{k} = n2^{n-1}.\]

First, we take note of what this sum looks like:

\[0\binom{n}{0} + 1\binom{n}{1} + 2\binom{n}{2} + 3\binom{n}{3} + \cdots + n\binom{n}{n}.\]

The first term is zero, so let's rewrite our sum as

\[\sum_{k=1}^{n} k\binom{n}{k} = n2^{n-1}.\]

Falling back on the formula to calculate a binomial coefficient, we obtain

\[\begin{align} k\binom{n}{k} &= k\left(\frac{n!}{k!(n-k)!}\right)\\ &=k\left(\frac{(n)(n-1)(n-2)\cdots (n-k+1)}{(k)(k-1)(k-2)\cdots (2)(1)}\right)\\ &= n\left(\frac{(n-1)(n-2)\cdots (n-k+1)}{(k-1)(k-2)\cdots (2)(1)}\right)\\ &=n\left(\frac{(n-1)(n-2)\cdots ((n-1)-(k-1)+1)}{(k-1)(k-2)\cdots (2)(1)}\right), \end{align}\]

which is quite advantageous for us, considering we have a fixed \(n\). We can finally say that

\[\sum_{k=1}^{n} k\binom{n}{k} = \sum_{k=1}^{n} n\binom{n-1}{k-1} = n\sum_{k=1}^{n} \binom{n-1}{k-1}\]

Then it follows from our earlier definition for the sum of binomial coefficients that

\[n\sum_{k=1}^{n} \binom{n-1}{k-1} =n\sum_{k=0}^{n-1} \binom{n-1}{k}= n2^{n-1}.\]

Now comes something interesting. The alternating sum of binomial coefficients across a fixed row \(n\) equals \(0\). More formally,

\[\binom{n}{0} -\binom{n}{1} +\binom{n}{2} - \binom{n}{3} +\cdots +(-1)^n\binom{n}{n} = \sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0.\]

It follows that

\[0=(1-1)^n=\binom{n}{0}(1)^n(-1)^0+\binom{n}{1}(1)^{n-1}(-1)^1+\cdots +\binom{n}{n}(1)^0(-1)^{n}.\]

Let \(\alpha_e\) equal the sum of all the even-index terms in row \(n\), and let \(\alpha_o\) equal the sum of all odd-index terms in row \(n\). Our previous equation now can be shown as

\[\alpha_e - \alpha_o = 0 \quad \Rightarrow \quad \alpha_e = \alpha_o.\]

Since the sum of all the even-index terms in row \(n\) and the sum of all the odd-index terms in row \(n\) are equal, they contribute the same amount to the total sum of the row, \(2^n\). Thus, if we omit either the even-index or the odd-index terms, we will have precisely half of our original total. Thus, we can say

\[\sum_{k=0}^{n} \binom{n}{2k} = \sum_{k=0}^{n} \binom{n}{2k+1} = \frac{2^n}{2} = 2^{n-1}.\]

One may also notice a familiar sequence hidden in Pascal's triangle. \(\binom{n}{2}\) represents the \((n-1)^{\text{th}}\) triangular number \(T_n = \dfrac{(n+1)(n)}{2}\). If you're unfamiliar with this sequence, here is a link to get you started! This proof makes use of the facts that

\[\binom{n}{1} = n, \quad \binom{2}{2} = 1 = T_{1},\]

and making the assumption that for all \(n\geq 2\),

\[\begin{align} \binom{n}{2} = T_{n-1} &= \dfrac{(n)(n-1)}{2}\\ \binom{n+1}{2} = T_{n} &= \dfrac{(n+1)(n)}{2}, \end{align}\]

which holds under induction. We can verify this visually by looking at Pascal''s triangle and using our guideline for construction:

\[\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.\]

Actually, if you know your stuff about triangular numbers, you can even say that

\[\binom{n}{2}^2 = \sum_{j=1}^{n-1} \binom{j}{1}^3.\]

It is left to the reader to prove this for themselves, but if you get stuck, here's a link to the proof.

One of the more visually striking properties is the Sierpiński sieve, which is obtained by taking every binomial coefficient mod 2. Essentially, this process separates each binomial coefficient by its parity. If every odd number is replaced with a black triangle, a Sierpinski triangle begins to form. Try it out for yourself! This also plays into the Lucas correspondence theorem, which is far too complex for the sake of this wiki page.

## Proof

Suppose we have a sequence of length \(n\), and we want the number of ways to choose \(k\) elements. Obviously, there are \(n\) choices for the first element. There are \(n-1\) ways to choose the second element, \(n-2\) ways to choose the third element, etc. This continues down to choosing the \(k^{\text{th}}\) element, for which there are \(n-k+1\) choices. Thus the number of all possible permutations of these "choosings" is

\[(n)(n-1)(n-2)\cdots (n-k+1) = \dfrac{n!}{(n-k)!}.\]

Now, for all these selections, there are only some unique ones. In other words, some selections are permutations. It's easy to see that there are \(k!\) permutations of each primitive selections. Thus, to get the number of primitive sequences, we use

\[\dfrac{\dfrac{n!}{(n-k)!}}{k!}=\frac{n!}{k!(n-k)!}. \ _\square\]

Prove that nC1+...+nCn = 2 nCn

**Cite as:**Binomial Coefficient.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/binomial-coefficient/