Binomial Coefficients

Section 2.3 Binomial Coefficients

Objectives

Prove the Binomial Theorem and apply it to find coefficients of terms in expansions.
Describe and prove simple identities involving binomial coefficients possibly in relation to Pascal's Triangle.

In this section we discuss the quantity

(\binom{n}{k})

in more detail and explore some nice related identities and applications. First, we give a name to the quantity; the reason for the name will be made clear in the main theorem of this section.

🔗

Definition 2.3.1. Binomial Coefficient.

For $k \leq n,$ the quantities

(\binom{n}{k})

are called binomial coefficients.

🔗

Exploration 2.3.1. The Meru Prastaara (The Holy Mountain).

The Meru Prastaara. Numbers in boxes arranged in a triangular shape.

The Indian mathematician and writer Piṅgala (200 BC) in his text the Chandaḥśāstra studied variations in poetic metres when using only either long (g, for guru) and short (l, for laghu) syllables.

He explained that monosyllabic (or one-syllable) metres have two variations—either g or l—while disyllabic metres have four different kinds:

gg, gl, lg, or ll.

Or, one with no l's, two with one l, and one with two l's.

Piṅgala also observed that each two-syllable variant could be obtained from the one-syllable variants using the following scheme, appending on the right:

monosyllabic	(g	l)	(g	l)
append	g		l
disyllabic	gg	lg	gl	ll

The same can be done going from two to three syllables.

disyllabic	(gg	lg	gl	ll)	(gg	lg	gl	ll)
append	g				l
trisyllabic	ggg	lgg	glg	llg	ggl	lgl	gll	lll

🔗

(a)

Of the three trisyllabic variants with two l's (llg, lgl, and gll), one comes from the first group (ending with g), and two from the second (ending with l). Explain how this demonstrates that

(\binom{3}{2}) = (\binom{2}{2}) + (\binom{2}{1}) .

🔗

(b)

Construct the table for the four-syllable forms in a similar way: appending g's to all trisyllabic forms, then appending l's. You should get a total of 16. In the same manner as (a), find an identity involving

(\binom{4}{2})

by looking at the two possible endings of the four-syllable forms.

Hint

There are six strings involving g's and l's that have exactly two l's. How many of them end with g? How many with l?

🔗

(c)

Generalize the arguments above to a formula involving

(\binom{n}{k}) .

Hint 1

Separate into two cases depending on the last syllable (g or l).

Hint 2

How many of the $(n-1)$-syllable variants already have $k$ l's? How many have $(k-1)$ $l$'s and need one more?

Answer

Right-hand side is $\displaystyle\binom{n-1}{k} + \binom{n-1}{k-1}\text{.}$

🔗

In Exploration 2.3.1 we saw how the binomial coefficient

(\binom{n}{k})

can be expressed as the sum of two binomial coefficients involving

(n - 1) :

(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .

🔗

This rule is known as Pascal's Formula, after mathematician Blaise Pascal, who formalized many of the results and identities about the binomial coefficients.

🔗

Theorem 2.3.2. Pascal's Formula.

If $n \geq 1,$ then

(\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) .

🔗

Theorem 2.3.2 generates an intuitive visualization of the binomial coefficients that you may have seen before, widely known as Pascal's Triangle.

🔗

We start by placing a 1 in the 0th row, and two 1's in the 1st row. Then each new row starts and ends with a 1, while each value in between is obtained by adding the numbers to its upper left and upper right.

The first five rows of Pascal's triangle. — 🔗
Figure 2.3.3. The first five rows of Pascal's Triangle, for $n = 0$ to $4 .$

🔗

The

k

th entry in the

n

th row of this triangle (starting with

n = 0

) is exactly

(\binom{n}{k}),

while Theorem 2.3.2 shows how to recursively generate its rows.

🔗

Checkpoint 2.3.4. Continue the Triangle.

Complete Pascal's Triangle up to the 9th row and use it to determine the value of $\displaystyle\binom{9}{3}\text{.}$

Answer

$84.$

🔗

The reason for the term binomial coefficient is clarified in the next theorem.

🔗

Video: The Binomial Theorem

🔗

Theorem 2.3.5. Binomial Theorem.

For $k \leq n,$ the quantity $(\binom{n}{k})$ is equal to the coefficient of $x^{n - k} y^{k}$ in the expansion of $(x + y)^{n} .$ That is,

(x + y)^{n} = \underset{n times}{\underset{⏟}{(x + y) (x + y) \dots (x + y)}} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .

🔗

Proof.

Each factor in the product $(x+y)^n = (x+y)(x+y)\cdots(x+y)$ contributes either an $x$ or a $y$ in the resulting expansion. We can express each term in the answer as a sequence of $n$ symbols, each either an $x$ or a $y\text{;}$ for example, picking $x$ from each $(x+y)$ term gives $\underbrace{xx\cdots x}_\text{$n$ times}=x^n\text{.}$

Hence the number of times $x^{n-k}y^k$ appears in the final expansion is precisely the number of rearrangements of the word

\begin{equation*} \underbrace{x\ x\cdots x}_\text{$n-k$ times}\underbrace{y\ y\cdots y}_\text{$k$ times}, \end{equation*}

which is exactly equal to $\frac{n!}{(n-k)!k!} = \binom{n}{k}$ by Proposition 2.2.10.

🔗

Observe that the proof of Theorem 2.3.5 simply counts the number of

n

-letter strings of

x

's and

y

's that contain

n - k

number of

x

's. This is the same thing as counting

n

-syllable forms in Exploration 2.3.1, and in fact, Theorem 2.3.5 can also be proven using the same recursive argument in Exploration 2.3.1 part (c).

🔗

Checkpoint 2.3.6. Coefficient of $x^{4} y^{7}$ in $(x + y)^{11}$ .

Determine the coefficient of $x^4y^7$ in the product $(x+y)^{11}\text{.}$

Hint

This is a direct application of Theorem 2.3.5.

Answer

$\displaystyle\binom{11}{4}$ or $\displaystyle\binom{11}{7}\text{.}$

🔗

Checkpoint 2.3.7. Coefficient of $a^{2} b^{3}$ .

Determine the coefficient of $a^2b^3$ in each product:

$\displaystyle (a+b)^5$
$\displaystyle (a-b)^5$
$\displaystyle (3a+2b)^5$

Hint

b. and c. What are $x$ and $y$ in the statement of Theorem 2.3.5?

🔗

Checkpoint 2.3.8. Prove that $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$ .

Prove that $\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n$ for $n \geq 0\text{.}$

Hint

Stare at Theorem 2.3.5 until you see it.

🔗

We end this section with a nice application where binomial coefficients appear.

🔗

Example 2.3.9. Lattice Paths.

On the $xy$-plane, a lattice path is a path that moves from integer point to integer point by taking only steps of length one to the right or upwards. For instance, the following are three different paths to the point $(4,2)\text{,}$ starting at the origin $(0,0)\text{:}$

Each path above can be represented as a sequence of 4 R's and 2 U's:

RRUURR

UURRRR

RRRURU

so the total number of lattice paths from $(0,0)$ to $(4,2)$ is the same as the number of such sequences, which is

\begin{equation*} \binom{6}{4} = \frac{6!}{2! \ 4!}\text{.} \end{equation*}

🔗

Example 2.3.9 illustrates a useful technique in counting problems: by representing what is being counted (lattice paths) in a different way (sequences of R's and U's), we can uncover the combinatorial structure of these objects, making them easier to count.

🔗