| Doubly alternating Baxter permutations are Catalan (1998) | |||||||||||||||||
|
|||||||||||||||||
Abstract | |||||||||||||||||
| The Baxter permutations who are alternating and whose inverse is also alternating are shown to be enumerated by the Catalan numbers. A bijection to complete binary trees is also given. R'esum'e Nous montrons que les permutations de Baxter alternantes dont l'inverse est 'egalement une permutation de Baxter alternante sont 'enum'er'ees par les nombres de Catalan. De plus, nous donnons une bijection avec les arbres binaires complets. 1 Introduction Baxter [Ba] studied a particular class of permutations by studying fixed points of the composite of commuting functions. These permutations can be defined by forbidden subsequences [Gi, Gu, Kn, SS, We]. In fact, the Baxter permutations are exactly the permutations ß of length n which verify the two following conditions: for all 1 i ! j ! k ! l n, if ß i + 1 = ß l and ß j ? ß l then ß k ? ß l , if ß l + 1 = ß i and ß k ? ß i then ß j ? ß i . For example, 2413 and 3142 are the only permutations on four elements which are not Baxter permutat... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||