# Binomial Coefficients

In Combinations, we introduced binomial coefficients $$\binom{n}{k}$$ as the number of ways to choose $$k$$ objects from a set of size $$n$$. Binomial coefficients also arise naturally when considering powers of binomial expressions, as shown in the following theorem.

### Binomial Theorem: If $$a, b$$ are variables and $$n$$ is a positive integer, then

$\displaystyle (a+b)^n = \sum_{i = 0}^{n}\binom{n}{i}a^{i}b^{n-i} .$

The two different ideas mentioned above are actually very closely related to each other. When we expand $$(a + b)^{n}$$, each term in the expansion comes from choosing either $$a$$ or $$b$$ from each of the $$n$$ binomials in the product. This is why the terms in our expression are of the form $$a^{i}b^{n-i}$$. To get the term $$a^{i}b^{n-i}$$, we have to multiply $$i$$ copies of $$a$$ and $$n-i$$ copies of $$b$$. If we choose $$i$$ of the $$n$$ binomials from which to use the term $$a$$, then we are left with $$n-i$$ of the binomials from which to use the term $$b$$. The total number of ways to choose $$i$$ of the $$n$$ binomials is $$\binom{n}{i}$$, which is why this is the coefficient of the term $$a^{i}b^{n-i}$$.

The binomial coefficients can be arranged into a chart called Pascal’s Triangle that uses the relation $$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$$. The $$i$$th row of Pascal’s triangle has the binomial coefficients $$\binom{i}{0}, \binom{i}{1}, \ldots, \binom{i}{i}$$. The first row is considered row 0 and contains the coefficient $$\binom{0}{0}$$.

$\begin{array}{ccccccccccccc} & & & & & &\binom{0}{0} & & & & & & \\ & & & & &\binom{1}{0} & &\binom{1}{1} & & & & & \\ & & & &\binom{2}{0} & &\binom{2}{1} & &\binom{2}{2} & & & & \\ & & &\binom{3}{0} & &\binom{3}{1} & &\binom{3}{2} & &\binom{3}{3} & & & \\ & &\binom{4}{0} & &\binom{4}{1} & &\binom{4}{2} & &\binom{4}{3} & &\binom{4}{4} & & \\ &\binom{5}{0} & &\binom{5}{1} & &\binom{5}{2} & &\binom{5}{3} & &\binom{5}{4} & &\binom{5}{5} & \\ \binom{6}{0} & &\binom{6}{1} & &\binom{6}{2} & &\binom{6}{3} & &\binom{6}{4} & &\binom{6}{5} & &\binom{6}{6} \\ \end{array}$

By plugging in the values of the binomial coefficients, we obtain Pascal's Triangle:

$\begin{array}{ccccccccccccc} & & & & & & 1 & & & & & & \\ & & & & & 1 & & 1 & & & & & \\ & & & & 1 & & 2 & & 1 & & & & \\ & & & 1 & & 3 & & 3 & & 1 & & & \\ & & 1 & & 4 & & 6 & & 4 & & 1 & & \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1 & \\ 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1 \\ \end{array}$

When working with binomial coefficients, we can generally approach problems in two different ways, either algebraically (by manipulating the expressions), or combinatorially (by interpreting the expressions).

## Worked Examples

### 1. Show algebraically that $$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$$.

Solution: We expand the expression on the left hand side in terms of factorials:

\begin{aligned} \binom{n}{k} + \binom{n}{k+1} = & \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!}\\ = & \frac{n!(k+1)}{(k+1)!(n-k)!} + \frac{n!(n-k)}{(k+1)!(n-k)!}\\ = & \frac{n!(n+1)}{(k+1)!(n-k)!}\\ = & \frac{(n+1)!}{(k+1)!(n-k)!}\\ = & \binom{n+1}{k+1}\\ \end{aligned}

### 2. Show combinatorially that $$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$$.

Solution: The right hand side counts the number of ways to choose $$k+1$$ people from $$n+1$$ people. If we consider one of the $$n+1$$ people, then either they are chosen in the set of $$k+1$$ people or they are not. The number of ways to choose $$k+1$$ people which includes this person is $$\binom{n}{k}$$ (we need to choose $$k$$ of the $$n$$ other people). The number of ways to choose $$k+1$$ people which do not include this person is $$\binom{n}{k+1}$$ (we need to choose $$k+1$$ of the $$n$$ other people).

### 3. Show that $$\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^{n}$$.

Algebraic solution: From the Binomial Theorem, we have

$(a + b)^{n} = \sum_{i = 0}^{n}\binom{n}{i}a^{i}b^{n-i} .$

If we let $$a = b = 1$$, this expression becomes

$2^n = \sum_{i=0}^{n}\binom{n}{i} = \binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} .$

Combinatorics solution: We use the technique of Double Counting. Consider the number of ways to choose a team out of $$n$$ players. From Combinations, there are $${ n \choose i}$$ ways to choose a team of exactly $$i$$ players; therefore, the left hand side represents the number of ways to choose a team according to the number of players. On the other hand, we can choose a team by deciding if a specified player is in the team or not. By the Rule of Product, there are $$2^n$$ ways to do this which is the right hand side. Hence, the two sides are equal.

Note by Arron Kau
4 years, 3 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$