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 11 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\\ 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1\\ 1 \quad 7 \quad 21 \quad 35 \quad 35 \quad 21 \quad 7 \quad 1\\ 1 \quad 8 \quad 28 \quad 56 \quad 70 \quad 56 \quad 28 \quad 8 \quad 1\\ 1 \quad 9 \quad 36 \quad 84 \quad 126 \quad 126\quad 84 \quad 36 \quad 9 \quad 1\\ 1 \quad 10 \quad 45 \quad 120 \quad 210 \quad 252 \quad 210 \quad 120 \quad 45 \quad 10 \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 the 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.

Binomial coefficients are the ones that appear as the coefficient of powers of \(x\) in the expansion of \( (1+x)^n:\)

\[ (1+x)^n = n_{c_{0}} + n_{c_{1}} x + n_{c_{2}} x^2 + \cdots + n_{c_{n}} x^n,\]

where \( n_{c_{k}}=\frac{n!}{k!(n-k)!}.\) The terms from \( n_{c_{0}} \) to \( n_{c_{n}} \) are called as the binomial cofficients. Hereafter the term \( n_{c_{k}}\) will be written as \( \dbinom{n}{k}. \)

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\]

In how many ways can you select 2 balls from a box containing 9 balls?

---

The number of ways to choose 2 elements out of a set of 9 is

\[ \dbinom{9}{2} = \frac{9!}{2! 7!} = \frac{9\cdot 8 }{ 2\cdot 1} = \frac{72}{2} = 36. \ _\square\]

In how many ways could you choose a three-topping pizza based on the following menu?

---

The number of ways to choose 3 elements out of a set of 10 is

\[ \dbinom{10}{3} = \frac{10!}{7! 3!} = \frac{10\cdot 9 \cdot 8}{3\cdot 2\cdot 1} = \frac{720}{6} = 120. \ _\square\]

Three distinct 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\times 3, ~~7, ~~2^3, ~~3^2, ~~2\times5.\]

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 5 numbers.
So, the number of ways of filling all the three places is \(\binom{5}{3} = \frac{5!}{(5-3)! 3!} = 10.\)
But note that the order of these 3 distinct digits matter! So we need to multiply it back by \(3!\).
Hence, the total possible 3-digit numbers from the above 5 numbers is \(10\times3!=60\). \(_\square\)

As the name implies, the binomial theorem can be used to expand binomials. You may do so with the equation below.

When given a binomial, \((x + y)^a\), you may expand the binomial using the following equation:

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

This is a simplified definition of binomial expansion using binomial coefficients.

This equation may seem overwhelming at first glance. However, an easy way to think about it is that you apply each coefficient to its appropriate term, and the power of the first binomial term counts down from \(a\) to 0, while the power of the second binomial term counts up from 0 to \(a.\)

Expand \(\big(c^2 + 2\big)^3\).

---

Using the equation given above, we know that \(x = c^2, y = 2,\) and \(a = 3\). Therefore we can expand the binomial to

\[\binom{3}{0}\big(c^{2}\big)^{3}2^{0} + \binom{3}{1}\big(c^{2}\big)^{2}2^{1} + \binom{3}{2}\big(c^{2}\big)^{1}2^{2} + \binom{3}{3}\big(c^{2}\big)^{0}2^{3}=c^{6} + 6c^{4} + 12c^{2} + 8.\ _\square\]

Find the coefficient of \({ x }^{ 7 }\) in the expansion of \({ (x+3) }^{ 10 }\).

---

Recall that the binomial theorem is

\[(x + y)^a = \binom{a}{0}x^{a}y^{0} + \binom{a}{1}x^{(a-1)}y^{1} + \cdots + \binom{a}{a-1}x^{1}y^{(a-1)} + \binom{a}{a}x^{0}y^{a},\]

which in summation form is

\[{ (x+y) }^{ a }=\sum _{ i=0 }^{ a }{ a \choose i } { x }^{ a-i }{ y }^{ i }.\]

In order to get the coefficient of \({ x }^{ 7 }\), we need to have \(a - i = 7.\) Sinces \(a = 10\), \(i = 3\).

Thus, the answer is \(\displaystyle { y }^{ 3 }{ a \choose 3 } = { 3 }^{ 3 }{ 10 \choose 3 } = 3240.\ _\square\)

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} .\]

We have

\[\displaystyle \begin{eqnarray} \binom{n}{k} + \binom{n}{k+1} & = & \frac{n!}{k!\big((n-k)!\big)} + \frac{n!}{(k+1)!\big(n-(k+1)\big)!} \\\\ & = & \frac{(k+1)n!+(n-k)n!}{(k+1)!(n-k)!} \\\\ & = & \frac{(n+1)!}{(k+1)!(n-k)!} \\\\ & = & \binom{n+1}{k+1}.\ _\square \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}.\]

We have

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

This 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 \big((n-1)-(k-1)+1\big)}{(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 \implies \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 = \frac{(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}.\]

Now, if you know your stuff about triangular numbers, you can 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 mod 2 of every binomial coefficient. 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 left for the reader to discover for further learning.

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 \(\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n} = 2^n.\)

---

Intuition: The above sum is equal to the number of ways we can choose \(1\) object from \(n\) objects plus \(2\) objects all the way up to choosing \(n\) objects. Intuitively, this is all possible "choosings" for \(n\) objects. Now, if we are to calculate the total possible "choosings" for \(n\) objects, since each object can be either chosen or not chosen, this is equal to \(\underbrace{2\times 2\times 2\times \cdots \times 2}_{\text{n times}}=2^n.\)