Section2.10An 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 Example 2.28, let’s practice counting some lattice paths with some restrictions.
The town of Mascotville is laid out as a grid. There are seven parallel streets (\(1^{\text{st}}\) through \(7^{\text{th}}\)) that run north-south and five parallel avenues (\(1^{\text{st}}\) through \(5^{\text{th}}\)) that run east-west.
Buzz starts at the intersection of \(1^{\text{st}}\) Street and \(1^{\text{st}}\) Avenue and wants to get to Bucky’s burrow at the intersection of \(7^{\text{th}}\) Street and \(5^{\text{th}}\) Avenue traveling only on streets/avenues, and always moving toward Bucky’s burrow. How many ways can he do this?
The Varsity is at the intersection of \(3^{\text{rd}}\) Street and \(3^{\text{rd}}\) Avenue. How many ways can Buzz get to Bucky’s burrow if he insists on stopping at The Varsity?
Suppose Buzz is put on a diet and prohibited from eating at The Varsity. He knows if he goes by it, he’ll stop and eat, so he must avoid it completely. How many ways are there for him to get to Bucky’s burrow that avoid The Varsity?
Correct! We can solve this by counting all the lattice paths and then subtracting those that involve the forbidden temptation of stopping at The Varstiy.
You will not be tested on the proof in Example 2.28, 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
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:
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).
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:
The bad lattice path \(HHVVHVVHHVVH\) from \((0,0)\) to \((6,6)\) is transformed to which of the following lattice paths from \((0,0)\) to \((5,7)\text{?}\)
How many rearrangements of the string APPLIEDCOMBINATORICSISTHEMOSTINTERESTINGBOOKEVER are there if all letters must be used? (Note that there are a couple of hints outside the blue box on Runestone!)
One of the interesting things about understanding the Multinomial Theorem 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\text{.}\)
Yes! This is really just folder distribution in disguise. Here we must distribute \(17\) folders (what the exponents must sum to) to four recipients (the number of terms). However, we need an artificial folder for each exponent to allow exponents to be zero. Therefore, we’re talking about 21 folders with 20 gaps and we need 3 dividers.
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\text{.}\) The sum of the exponents would need to be 100, so this leaves 85 as the exponent on \(y\text{.}\) However, the term inquired about has \(y^{80}\text{.}\)
