Foata’s Transformations On Permutations And Fibonacci Words

Foata’s first transformation and Foata’s second transformation are two classical transformations in combinatorics. Foata’s first transformation is the inverse of Lyndon factorization, and it transforms the excedance number to the descent number on words. Foata’s second transformation transformations the major index to the inversion num-ber on words, and has been widely generalized to other combinatorial objects, such as r-colored words, matchings, set partitions, standard Young tableaux and moon poly-ominoes.In this thesis, we study the properties of Foata’s first and second transformation on permutations and Fibonacci words. On one hand, we consider the invariance prop-erty of principal order ideals (with respect to the Bruhat order) under Foata’s second transformation on permutations. On the other hand, we study the Eulerian pairs on Fibonacci words by using Foata’s first transformation. Meanwhile, we study the invari-ance property of principal order ideals (with respect to the weak order) under Han’s Foata-style bijection on permutations.This thesis is organized as follows. In Chapter1, we introduce the background of Foata’s two transformations. We also present some basic definitions, including four common statistics, Fibonacci words, the weak order and the Bruhat order. Finally, we give a brief review of the contents of this thesis.In Chapter2, we consider the invariance property of principal order ideals (with respect to the Bruhat order) under Foata’s second transformation on permutations. Our main contribution is to give a characterization of the maximal element of an invariant principal order ideal with respect to the Bruhat order. The main framework is as fol-lows. First, for any principal order ideal, we partition the permutations in this principal order ideal into different sets according to the last element of each permutation and then derive the general form of the maximal element in each class. Second, we prove that the maximal permutation in an invariant principal order ideal must be132-avoiding. Finally, we derive the characterization of the maximal element by induction. We also show that a principal order ideal is invariant under Han’s Foata-style bijection if and only if it is invariant under Foata’s transformation.In Chapter3, we focus on the invariance property of principal order ideals (with respect to the weak order) under Han’s Foata-style bijection on permutations. We aim to give a characterization of the maximal element of each invariant principal order ideal. The main idea is as follows. We construct a specific subset Ln of permutations. We first give a characterization of a permutation beginning with n in Ln. Then we find the descriptions of permutations in Ln according to the number of the right-left maxima. Based on these results, we conclude that a principal order ideal is invariant under Han’s Foata-style bijection if and only if the maximal element is in Ln. We also give a sufficient condition of invariant intervals under Han’s Foata-style bijection.In Chapter4, we answer a question raised by Sagan and Savage, under the consid-eration of the Eulerian pairs on Fibonacci words based on Foata’s first transformation and an extension of Steingimsson’s bijection, which can be seen as a variant of the inverse of Foata’s first transformation. Although it is not a bijection on words, it al-so transforms the descent number to the excedance number and it can be viewed as a bijection on a special set. Applying a well-known correspondence between integer par-titions and binary words, we obtain the descriptions of images of three sets consisting of Fibonacci words under Foata’s first transformation and the extended map respec-tively. This allows us to derive three Eulerian pairs. Meanwhile, we find that when restricted to binary words, Foata’s first transformation coincides with Han’s fundamen-tal transformation. Finally, we point out that Foata’s first transformation is the inverse of Foata’s second transformation under some restrictions.