Definition 2.2.
A lattice path is a sequence of ordered pairs of integers
\begin{equation*}
(m_{1},n_{1}), (m_{2},n_{2}), (m_{3},n_{3}),\dots,(m_{t},n_{t})
\end{equation*}
so that for all \(i=1,2,\dots,t-1\text{,}\) either
Print preview
Handout 2.3 Lattice Paths, Binomial Theorem, Multinomial Theorem
A grid of dots. There are 13 columns of dots and 8 rows of dots. The dot in the lower left corner is labeled \((0,0)\text{.}\) The dot in the upper right corner is labeled \((13,8)\text{.}\) There is a path marked on the grid between these dots. The path moves only to the right and up. It consists of three moves to the right, two moves up, one move right, one move up, one move right, three moves up, five moves right, one move up, one move right, one move up, and two moves right.
Activity 2.3.1.
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.
(a)
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?
(b)
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?
(c)
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?
Question 2.3.
How many lattice paths are there from \((0,0)\) to \((n,n)\) that do not cross the line \(y=x\text{?}\) (Lattice paths are allowed to touch the line.)
Peer instruction question 1
Activity 2.3.2.
Find a \(1\)-\(1\) correspondence between the set of good lattice paths and each of the following sets:
(a)
Sequences of \(n\) \(1\)’s and \(n\) \(-1\)’s in which the sum of the first \(i\) terms is non-negative for all \(i\text{.}\)
(b)
Full-parenthesizations of a product of \(n+1\) factors as if the “multiplication” operation were not associative. Examples:
-
\(4\) factors: \((a_{1}(a_{2}(a_{3}a_{4})))\text{,}\) \((a_{1}((a_{2}a_{3})a_{4}))\text{,}\) \(((a_{1}a_{2})(a_{3}a_{4}))\text{,}\) \(((a_{1}(a_{2}a_{3}))a_{4})\text{,}\) and \((((a_{1}a_{2})a_{3})a_{4})\)
Theorem 2.4. Binomial Theorem.
Let \(x\) and \(y\) be real numbers to that \(x\text{,}\) \(y\text{,}\) and \(x+y\) are all nonzero. For every nonnegative integer \(n\text{,}\)
\begin{equation*}
\phantom{(x+y)^n = \sum_{k=0}^n x^{n-k}y^k}
\end{equation*}
Peer instruction question 3.
Activity 2.3.3.
How many rearrangements of the string
\begin{equation*}
\text{APPLIEDCOMBINATORICSISTHEMOSTINTERESTINGBOOKEVER}
\end{equation*}
are there if all letters must be used?
Hint 2.
| A | P | L | I | E | D | C | O | M | B | N | T | R | S | H | G | V | K |
| 2 | 2 | 1 | 6 | 6 | 1 | 2 | 5 | 2 | 2 | 3 | 5 | 3 | 4 | 1 | 1 | 1 | 1 |
Theorem 2.5. Multinomial Theorem.
Let \(x_{1},x_{2},\dots,x_{r}\) be nonzero real numbers with \(x_{1} + x_{2} + \cdots + x_{r} \neq 0\text{.}\) Then for every nonnegative integer \(n\text{,}\)
\begin{equation*}
(x_{1}+x_{2} + \cdots + x_{r})^{n} = \sum_{k_1+k_2 + \cdots + k_r=n}\binom{n}{k_1,k_2,\dots,k_r}x_{1}^{k_1}x_{2}^{k_2}\cdots x_{r}^{k_r}.
\end{equation*}
Activity 2.3.4.
How many terms are there in the summation from the multinomial theorem for \((x+y+z+w)^{17}\text{?}\)
Let’s take another look at a class prep question. What is the coefficient on \(x^{30}y^{80}z^{10}\) in \((2x^3+y-z^2)^{100}\text{?}\)
Peer instruction question 4
Activity 2.3.5.
Consider the expansion of \((3+x^{5}+y+xy^{3})^{50}\text{.}\) Find the coefficient on each of the following terms.
(a)
\(x^{30}y^{4}\)
(b)
\(x^{3}y^{3}\)
(c)
\(x^{30}y^{15}\)
