An Activity on Lattice Paths, the Binomial Theorem, and the Multinomial Theorem

Before considering the proof about the number of lattice paths from \((0,0)\) to \((n,n)\) that do not go above the diagonal \(y=x\) in , let's practice counting some lattice paths with some restrictions.

You will not be tested on the proof in , but you are expected to know that the number of lattice paths from \((0,0)\) to \((n,n)\) that do not go above the diagonal \(y=x\) is counted by the Catalan numbers \[\begin{aligned}\end{aligned}\]. We will see the Catalan numbers come up a number times through the remainder of our course, including quite likely on the very last day of the semester! There are a couple of important methods that come up in the proof that we will use often, and I do want to highlight those:

1. Sometimes it appears hard to directly count the objects of interest (the so-called good lattice paths), but it is still reasonable to count all the objects in a larger set (all lattice paths from \((0,0)\) to \((n,n)\)) and then subtract off those we don't want to count (the bad lattice paths).

2. Sometimes on the surface, it is difficult to count the objects of interest (the bad lattice paths) but we can transform them in an invertible way to a collection of objects that is easier to count.

I do think that it's worthwhile spending some time understanding how we define bad lattice path and the transformation in the text, here are a couple of questions on the subject:

Let's now turn to some questions involving use of the binomial and multinomial theorem.

One of the interesting things about understanding the is figuring out how many terms are even in the summation, since the notation involves a summation that you might not be familiar with. The notation \(\displaystyle \sum_{k_1+k_2+\cdots+k_r=n}\) means that we sum over all nonnegative (i.e., greater than or equal to 0) integers \(k_1,k_2,\dots,k_r\) so that the sum \(k_1+k_2 + \cdots + k_r\) is exactly \(n\).

To help you check yourself on the class prep assignment, the answer to the question that asked for the coefficient on \(x^{30}y^{80}z^{10}\) in \((2x^{3}+y-z^{2})^{100}\) must be \(0\) because such a term cannot arise. Such a term would need an exponent of 5 on \(-z^2\) and an exponent of 10 on \(2x^3\). The sum of the exponents would need to be 100, so this leaves 85 as the exponent on \(y\). However, the term inquired about has \(y^{80}\).