MATH 47A FALL 2008 INTRO TO MATH RESEARCH 33But the original Dyck path is LABR. So, LA is a beginning of theoriginal Dyck path. By assumption, this word has more L’s than R’s.So, if we remove one L we have at least as many L’s as R ’s. So, the firstpart A of the middle word has at least as many L’s as R’s. Thereforethe middle word is a Dyck path. !In case 2 the Dyck path is LMR where M is the middle part whichis a shorter Dyck path. The algorithm is: Construct the binary treefor this middle word, then put it on the right underneath the root:!!!!!!!!!!!!!!!!!!!!!!!""""""""""""inserttree for Mhere5.3.3. the can of gas. If forgot to mention the “can of gas” analogy. Inthis interpretation you have a car which has no gas to start with. Youhave to go n miles and on the road there are n cans of gasoline. Eachcan has enough gas to go one mile and they are located at milestones(at 0 miles, 1 mile, 2 miles, etc.)In order to get started you need a can of gas at the beginning. Aftergoing one mile you need to find another can of gas. In the Dyck path,the L’s are cans of gas and the R are miles. So, for example, in theDyck path LRLLRLRR you get one can of gas at the beginning, thenyou drive one mile and find two more cans of gas. You drive one moremile and you find the fourth can of gas which is enough to get you twomore miles to the finish.If you take LRLR RLLR you will run out of gas after 2 miles. Atany point in time you need enough gas to get to the next milestone.In other words, you need at least as many cans of gas (the L’s) as thenumber of miles (R ’s) that you travel.34 NOTES5.4. reflection principle. Today we used the reflection principle toprove that there number of Dyck paths is given by the Catalan number.Theorem 5.18. The number of Dyck paths of length 2n is equal toC(n) =1n + 1!2nn".Proof. A Dyck path is the same as a random walk which stays on orabove the y-axis and starts and ends at y = 0 in 2n steps. The totalnumber of random walks which start and end at y = 0 in 2n steps is!2nn".We want to calculate the number of “good” paths. But instead wecount the number of “bad” paths since:total # paths = #good paths + #bad paths!2nn"= C(n) + (??)The “bad” paths are those which, at some p oint go below the y-axis.So, they hit the horizontal line y = −1 at some point in time. Thereflection principle says: Take the first point where the path hits theline y = −1 and reflect the rest of the path vertically through that line:!!!!!"""!"""!!!!!"""!!!!!!!!!"""!yxy = −1"""!"!!!!"""!"""!!!!! y = −2What happens is that the reflected path ends at y = −2. Andconversely, any random walk which ends up at y = −2 starting aty = 0 must cross the line y = −1 at some point and we can reflect theblue path back up. This gives a bijection between the set of bad paths(paths which start and end at y = 0 and go to y = −1 at some point)and the set of all paths which start at y = 0 and end at y = −2 after2n steps.MATH 47A FALL 2008 INTRO TO MATH RESEARCH 35This second set has#2nn−1$elements since, out of 2n steps we need totake exactly n − 1 steps to the left and n + 1 steps to the right in orderto arrive at 2 steps to the right at the end. So the number of goodpaths is# Dyck paths = total # paths − # bad paths=!2nn"−!2nn − 1"Expand this out:=(2n)!n!n!−(2n)!(n − 1)!(n + 1)!Factor out common factors:=(2n)!(n − 1)!n!%1n−1n + 1&=(2n)!(n − 1)!n!%1n(n + 1)&Collect terms:=(2n)!(n + 1)!n!=1n + 1(2n)!n!n!=