MATH 47A FALL 2008 INTRO TO MATH RESEARCH 315.3. Dyck paths to binary trees. Last time we constructed Dyckpaths out of binary trees. This can be described in set theoretic lan-guage as follows. We constructed a mappingf : {rooted binary trees with n nodes} → {Dyck paths of length 2n}Today we constructed the backwards mappingg : {Dyck paths of length 2n} → {rooted binary trees with n nodes}The inverse function g (if it is correct) satisfies the following two prop-erties:(1) f ◦ g = id on Dyck paths(2) g ◦ f = id on binary trees.The description of the function g was recursive. We took each Dyckpath and made it into one or two shorter paths. We used inductionon the number n to get the binary tree for these shorter paths, thenput them together to get the answer. The recursive algorithm “callsitself”, i.e., has a loop. But, since the length gets shorter, it do es notloop forever.We took two examples.(1) LRLRLLRR(2) LLRLRLRRIn the first example, we can break the Dyck path into two Dyckpaths:LR!!LRLLRR or LRLR!!LLRRIn the second example, there is no breaking point.5.3.1. Case 1. The Dyck path can be broken into two shorter Dyckpaths.In this case, we make two shorter Dyck paths. Each Dyck pathgives a binary tree. To put them together we attach the root of thefirst tree to the first leaf of the second tree. To make the algorithmdeterministic we take the first breaking point. In the example, first wedo: LR!!LLRR:!!!!root"""1st leaf!!!!!!!!!!""""""!to get:32 NOTES!!!!"""!!!!!!!!!!""""""!So, LR!!LRLLRR is given by putting the LR tree on the first leaf ofthis one. Drawing all leaves at the bottom, we get:!!!!!!!!"""""""""!!!!!!!""""""""""""!!!!5.3.2. Case 2. There is no breaking point.In this case we get a smaller Dyck path by removing the first andlast letter.Lemma 5.17. If we are in case 2, i.e., we have a Dyck path so that,whenever we break the path into two parts, there will be more L’s thanR’s in the first part, then we get a shorter Dyck path by removing thefirst and last letter.Proof. The first letter in any Dyck path must be L and the last lettermust be R. We want to prove that what is in the middle M is a Dyckpath. Since LMR has n L’s and n R’s, the middle part M has n − 1L’s and n − 1 R’s. We just need to prove that, whenever M is brokeninto two parts, say M = AB then the first part A has at least as manyL’s as R’s.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