MATH 47A FALL 2008 INTRO TO MATH RESEARCH 275.2. Dyck paths. First we discussed random walks. This is a “sto-chastic process” which you learn about in Math 56a. Then we convertedthis into a Dyck paths. Then I showed the bijection from binary trees toDyck paths. I asked the class to come up with the inverse construction(Dyck paths ⇒ binary tree).5.2.1. random walk. By a (fair) random walk we mean a sequence ofintegers X0, X1, X2, · · · so that, given Xt, Xt+1= Xt+1 or Xt−1 withequal probability. If you flip a coin and get 1$ for each head and lose1$ for each tail then Xtrepresents the amount of money you have aftert tosses of the coin.Question 5.12. Suppose X0= 0. Then what is the probability thatX2n= 0 ? In terms of equations this is:P(X2n= 0 | X0= 0) =?The formula for probability, given that each outcome has equal prob-ability, isP(A) =#ways that A can occurtotal # of possibilities(If the coin were not fair, the equation is more complicated.)Since we take 2n steps going either left or right with equal prob-ability, there are 22ntotal number of possibilities. This goes in thedenominator. To end up where we started we need the same numberof left steps and right steps. This number is 2n choose n. So, studentsfigured out that the answer is:P(X2n= 0 | X0= 0) =!2nn"22nQuestion 5.13. Suppose that X0= 0. Then what is the probabilitythat, not only is X2n= 0 but Xk≥ 0 for k = 0, 1, 2, · · · , 2n?This is something that we did in Math 23b. The answer is:P(X2n= 0, Xk≥ 0, 0 ≤ k ≤ 2n | X0= 0) =1n+1!2nn"22n=C(n)22nThe difference between these two equations is the factor of 1/(n + 1).This factor represents the conditional probability:P(Xk≥ 0, 0 ≤ k ≤ 2n | X0= 0, X2n= 0) =1n + 1I drew the following picture.28 NOTES!!!!!!!!!"""!!!!!"""!"""!!!!!"""!ytL L L LR R R RAlthough we didn’t prove it yet (It’s torture!) this formula says thatthe number of paths Xtwhich go up and down the same number oftimes and always stay above the y axis. Imagining that you are walkingleft and sometimes stepping left and sometimes right, every step in thepositive y direction is a left step and every step in the negative directionis a right step. So the random walk is represented by a sequence of L’sand R ’s.5.2.2. definition of Dyck path.Definition 5.14. A Dyck path is a word with 2n letters: n L’s and nR’s with the property that, if the word is broken into two parts, thefirst part (the one on the left) has at least as many L’s as R’s.As I explained in class, this definition has the advantage of beingcompletely rigorous and not relying on a picture.Theorem 5.15. The number of Dyck paths is at most!2nn".Proof. This binomial is the total number of words made out of n L’sand n R’s. !5.2.3. bijection with set of binary trees.Theorem 5.16. There is a bijection between the set of rooted binarytrees with n nodes and the set of Dyck paths with 2n letters.In order to prove this we need to show how every binary tree givesa Dyck path and, conversely, how every Dyck path gives a binarytree. This will give a bijection. This bijection should also preservethe “rank.” I described the first mapping and challenged the class tofind an algorithm for the inverse, i.e., which binary tree gives the givenDyck path?In words, the mapping from binary trees to Dyck paths goes as fol-lows. As Liz pointed out, for each binary tree with 2n nodes, thereare n edges going to the left and n edges going to the right. However,MATH 47A FALL 2008 INTRO TO MATH RESEARCH 29these edges are not in a row. Some of them are hanging in the air. Webring these letters down to the level of the leaves by sliding them tothe right.!!!!!!!!!!!!!!!!!!""""""""""""""""""""""""L L R L R RL RLLRBut, what is the inverse construction? What is the formula for thebinary tree.5.2.4. rank. I also pointed out that the bijection should preserve “rank.”The equation:Catal an# = sum of Narayana#!s :C(n) =n#k=1N(n, k)is usually interpreted in the following way. C(n) is the number ofobjects that we are considering. They might be Dyck paths of length2n or binary trees with n nodes. Each object has a “rank” k between1 and n. The number of items in our set with rank k is N(n, k). Thisexplains why the Narayana numbers add up to the Catalan number.For Dyck paths the rank is the number of peaks in the graph of thepath. So, k = 3 in our example. For binary trees it is the number ofrows that the nodes come in.(1) Find the unique binary tree with rank 1.(2) How can you tell from a Dyck path where the peaks