HEIGHT RESTRICTED LATTICE PATHS, ELENAS, AND BIJECTIONS HELMUTPRODINGER 6 1 0 ABSTRACT. A bijection is constructed between two sets of height restricted lattice paths by 2 means of translating them in two tree classe, namely plane trees and Elena trees. An old n bijectionbetweenthemcanbeusednowforthatactualproblem. a J 2 ] O 1. INTRODUCTION C We consider lattice path, consisting of up-steps and down-steps of one unit each, starting . h at the origin. In other words, (0,s ),(1,s ),...,(n,s ), with s = 0, and |s − s | = 1. 0 1 n 0 i i+1 t a Furthermore, we assume that 0 ≤ s ≤ 3. Let A be the family of these path of length n, i n,i m ending at level i, for i =0,1,2,3. [ It is straightforward to prove that |A | = F , |A | = F , |A | = F , and 2n,0 2n−1 2n,2 2n 2n+1,1 2n+1 1 |A |= F , with Fibonacci numbers F . 2n+1,3 2n k v We also consider similar lattice paths, this time with −2 ≤ s ≤ 1 and starting again 0 i at the origin. Let Let B be the family of these path of length n, ending at level i, for 3 n,i 2 i = −2,−1,0,1. It is again straightforward to prove that |B | = F , |B | = F , 2n,0 2n+1 2n,−2 2n 0 |B |= F , and |B |= F . 0 2n+1,1 2n+1 2n+1,−1 2n+2 . Thus we have that 1 3 0 6 (cid:12)(cid:12)[An,i(cid:12)(cid:12)=|Bn,0|+|Bn,−1|. 1 (cid:12)i=0 (cid:12) : v Cigler [1] asked fora bijectionto explain thisfact. An answer was given by Prellberg[2]. i X In this note, I want to link these problems to a tree structure named Elena (trees), that I r introduced some fifteen years ago [3]. The bijection presented in this early paper can also a be used here to explain the equality. Ifwe want that the paths are incorrespondencewith trees, werequire an evennumber of steps. 2. PATHS IN A AND HEIGHT RESTRICTED PLANE TREES 2n,0 Thetranslationofsuchapathoflength2nintoaplanetreeofheight≤3(countingedges) is direct and sometimescalled glove bijection. The followingexample will be sufficient. 2010MathematicsSubjectClassification. 05A19;11B39. Keywordsandphrases. Fibonaccinumbers;planetrees;Elenatrees,bijections. TheauthorwassupportedbyanincentivegrantoftheNationalResearchFoundationofSouthAfrica. 1 2 HELMUTPRODINGER 3 • 2 • • • • 1 • • • • 0• • • • FIGURE 1. A path of length 20, and the corresponding height restricted plane tree with 11 nodes 3. PATHS IN B AND ELENA TREES 2n,0 Elenas were introduced in [3]; they consist of some nodes labelled a, and a sequence of paths of various lengths (possibly empty) emanating from all of them, except for the last one. An example describes this readily: a • a • • a • • • • • a • • • a • • • • • FIGURE 2. An Elena described by ap ap p p aap a 3 1 1 4 2 Typically, an Elena can be described by ap p ...ap p ...a...a. For the set (language) i i j j 1 2 1 2 of Elenas, we might write a symbolic expression ap∗ ∗a. (cid:0) (cid:1) It is perhaps surprising that the paths in B are suitable to describe Elenas: For each 2n,0 sequence of steps (2i,0) → (2i+1,1) → (2i+2,0), we write a symbol a. In Figure 3 such pairs of steps are depicted in boldface. Thus, a path can be decomposed as w aw a...aw , where each w is a walk from level 0 0 1 s tolevel 0that “lives”onlevels0,−1,−2. Nowweaddasymbolaboth,tothe leftandtothe right. What isstill leftishow such aw canbe interpretedasa sequence ofpaths: Each returnto the level 0 marks the end of a path, and the translation of the sojourns is as follows: corresponds to p , corresponds to p , corresponds to p , corre- 1 2 3 sponds to p , and so forth. 4 Note that in this way a path of length 2n is (bijectively) mapped to an Elena of size (= number of nodes) n+2; the Elena consisting only of one node will not be considered. 4. ELENAS AND HEIGHT RESTRICTED PLANE TREES WewillestablishabijectionbetweenB andA ∪A ;note,howeverthatthelatter 2n,0 2n,0 2n,2 set may be replaced by A , by distinguishing the two cases of the last two steps. 2n+2,0 LATTICE PATHS, ELENAS, AND BIJECTIONS 3 1 0• • −1 −2 FIGURE 3. A path of length 28, described by p ap p p aap 3 1 1 4 2 • • • • • • • • • • • • • • • • FIGURE 4. The Elena with 16 nodes correspondingto (a)p ap p p aap (a) 3 1 1 4 2 Sowewouldbedoneoncewewouldknowhowtomap(bijectively)anElenaofsize n+2 to a height restrictedplane tree of the same size. This was documented already in [3], but will be repeated here to make this note self contained. The set of operations will be described a sequence of pictures, which require no additional explanation. We start with our running example of an Elena of size 16 and gradually transform it: • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • FIGURE 5. Transforming an Elena into a height restrictedplane tree 4 HELMUTPRODINGER 5. PATHS WITH AN ODD NUMBER OF STEPS Let us consider B , enumerated by F . If we augment one up-step at the end, we 2n−1,−1 2n have Elenas, but with the special propertythat the last group of paths is non-empty. One the other hand, if we consider A ∪A , which is equivalent to A , then 2n−1,1 2n−1,3 2n,2 we augment it with 2 down-steps. The resulting height restricted tree has the property that the rightmost leaf is on a level ≥2. A short reflection convinces us that the bijection described earlier also works bijectively on the two respective subclasses. REFERENCES [1] J. Cigler, Is there a simple bijection between the following sets A and B which are counted by the n n Fibonaccinumbers? www.researchgate.net,2015. [2] T. Prellberg, Is there a simple bijection between the following sets A and B which are counted by the n n Fibonaccinumbers? (Answer)www.researchgate.net,2015. [3] H. Prodinger, Words, Dyck paths, Trees, and Bijections, in: Words, Semigroups, and Transductions, World Scientific,2001,369–379,2015. DEPARTMENT OFMATHEMATICS,UNIVERSITY OFSTELLENBOSCH7602,STELLENBOSCH,SOUTHAFRICA E-mailaddress: [email protected]