MAT202: Introduction to Discrete Mathematics

Section 2.3 Binomial Coefficients

In this section we discuss the quantity \(\displaystyle\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.

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

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

\begin{equation*} \binom{3}{2} = \binom{2}{2} + \binom{2}{1}\text{.} \end{equation*}

(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

\begin{equation*} \displaystyle\binom{4}{2} \end{equation*}

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

\begin{equation*} \binom{n}{k}\text{.} \end{equation*}

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 \(\displaystyle\binom{n}{k}\) can be expressed as the sum of two binomial coefficients involving \((n-1)\text{:}\)

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 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 \(k\)th entry in the \(n\)th row of this triangle (starting with \(n=0\)) is exactly \(\displaystyle\binom{n}{k}\text{,}\) while Theorem 2.3.2 shows how to recursively generate its rows.

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

Video: The Binomial Theorem

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).

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

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.