Permutations de Baxter

S. Dulucq et O. Guibert ^{∗}

LaBRI, Université Bordeaux I (France) E-mail : nom@labri.u-bordeaux.fr

Abstract

F.R.K. Chung, R.L. Graham, V.E. Hoggatt and M. Kleiman [2] have shown the number of Baxter’s permutations on [n] is

∑_{m=0}^{n−1} \frac{\binom{n+1}{m}.\binom{n+1}{m+1}.\binom{n+1}{m+2}}{\binom{n+1}{1}.\binom{n+1}{2}}. X. Viennot [12] has then given a combinatorial proof of this formula, showing this sum corresponds to the distribution of these permutations according to their number of rises.

R. Cori, S. Dulucq and X. Viennot [3], by making a correspondence between two families of planar maps, have shown the number of alternating Baxter’s permutations on [2n + δ] is c_{n+δ}.c_{n} where c_{n} = \frac{(2n)!}{(n+1)!n!} is the n^{th} Catalan number.

We establish a new one-to-one correspondence between Baxter’s permutations and three nonintersecting paths, which unifies [12] and [3]. Moreover, we obtain more precise results for the enumeration of (alternating or not) Baxter’s permutations according to various parameters. So, we give a combinatorial interpretation of C.L. Mallows’s formula [10].

Introduction

G. Baxter [1] a mis en évidence une classe particulière de permutations en étudiant les points fixes de fonctions continues commutant par composition. Ces permutations, dites depuis permutations de Baxter, peuvent être définies en termes de motifs exclus. Plus précisément, elles vérifient les deux conditions suivantes : pour tout 1 ≤ i < j < k < l ≤ n, si π_{i} + 1 = π_{l} et π_{j} > π_{l} alors π_{k} > π_{l}, et, si π_{l} + 1 = π_{i} et π_{k} > π_{i} alors

π_{j} > π_{i}.

Ainsi, sur quatre éléments, seules les permutations 2413 et 3142 ne sont pas des permutations de Baxter.

∗Avec les soutiens PRC-Maths/Info et EC grant CHRX-CT93-0400

F.R.K. Chung, R.L. Graham, V.E. Hoggatt et M. Kleiman [2] ont montré, de manière analytique, que le nombre de permutations de Baxter sur [n] est

donné par la formule ∑_{m=0}^{n−1} \frac{\binom{n+1}{m}.\binom{n+1}{m+1}.\binom{n+1}{m+2}}{\binom{n+1}{1}.\binom{n+1}{2}}.

Plus tard, C.L. Mallows [10] a donné une interprétation plus fine de ce résultat en montrant que cette sommation correspondait à la distribution des permutations de Baxter suivant leur nombre de montées (indices i tels que π_{i} < π_{i+1}). De plus, il donne une nouvelle formule pour ces permutations où seul le paramètre m possède une interprétation (nombre de montées) : ∑_{m=0}^{n−1} ∑_{s=1}^{n} ∑_{i=1}^{n} \binom{n+1}{m+1} \frac{s.i}{n.(n+1)} [\binom{n−s−1}{n−m−2}\binom{n−i−1}{m−1} − \binom{n−s−1}{n−m−1}\binom{n−i−1}{m}].

X. Viennot [12] a donné une preuve combinatoire de la formule obtenue par F.R.K. Chung, R.L. Graham, V.E. Hoggatt et M. Kleiman en établissant une correspondance entre les permutations de Baxter et certains tableaux semistandards pour lesquels on connait une formule d’énumération. Cette correspondance repose sur un certain nombre de bijections classiques telles qu’entre permutations et histoires de Laguerre, entre mots de Motzkin 2-colorés et polyominos parallélogrammes [4], et finalement entre chemins deux à deux disjoints et tableaux semi-standards [7].

D’autre part, R. Cori, S. Dulucq et X. Viennot [3], lors de la résolution d’un problème posé par R.C. Mullin [11] sur l’énumération de certaines familles de cartes planaires, ont établi une correspondance entre le langage produit de mélange (ou shuffle) de deux systèmes de parenthèses (ou mots de Dyck) et les couples d’arbres binaires. Parmi les divers objets mis en oeuvre dans cette correspondance, apparaissent naturellement les permutations de Baxter alternantes (tour à tour montée et descente). Ils en déduisent que le nombre de telles permutations est c_{n}.c_{n} et c_{n+1}.c_{n} où c_{n} = \frac{(2n)!}{(n+1)!n!} est le n^{ème} nombre de Catalan.

L’objet de ce travail est de fournir une preuve combinatoire unifiant les résultats de X. Viennot sur les permutations de Baxter [12] et ceux de R. Cori, S. Dulucq et X. Viennot sur les permutations de Baxter alternantes [3], tout en donnant une interprétation combinatoire de la formule de C.L. Mallows [10].

Récemment, S. Dulucq et O. Guibert [5] ont résolu deux conjectures de S. Gire [8] portant sur l’énumération de certains mots de piles (liés au problème de permutations triables par passages consécutifs dans une pile [13]), objets en correspondance avec certains tableaux de Young standards rectangulaires de hauteur 3. Lors de la résolution de l’un de ces deux problèmes, ils mettent en correspondance permutations de Baxter et arbres jumeaux. Ces derniers sont obtenus en prenant les deux arbres binaires, croissant et décroissant, associés à une permutation (on oublie l’étiquetage de ces arbres). Cette application surjective est bijective lorsque les permutations considérées sont les permutations de Baxter. Par exemple, les permutations 2413 et 3412 donnent le même couple d’arbres binaires croissant et décroissant, mais seule la permutation 3412 est une permutation de Baxter.

Partant de cette caractérisation des permutations de Baxter en termes d’arbres binaires jumeaux [5], nous mettons en correspondance permutations de Baxter et triplets de chemins deux à deux disjoints dans un huitième de plan (ces triplets de chemins correspondent à des polyominos parallélogrammes jumeaux) et retrouvons ainsi les chemins obtenus par X. Viennot [12], ce qui nous permet de conclure. Cependant, dans les différentes bijections considérées ici, un certain nombre de paramètres sont transportés.

Ainsi, nous déduisons des travaux de I. Gessel et X. Viennot [7] un déterminant 3 × 3 donnant le nombre de permutations de Baxter sur [n] distribuées suivant plusieurs paramètres. Nous retrouvons les formules de F.R.K. Chung, R.L. Graham, V.E. Hoggatt et M. Kleiman [2] et de C.L. Mallows [10] pour laquelle nous montrons que les paramètres m, i et s correspondent aux nombres de montées, de minima et maxima à gauche des permutations de Baxter.

De plus, dans la bijection que nous donnons entre permutations de Baxter et triplets de chemins deux à deux disjoints, le caractère alternant des permutations correspond au fait que le second chemin est en escalier. Ainsi apparait naturellement un couple de chemins de Dyck. Nous en déduisons que le nombre de permutations de Baxter alternantes sur [2n + δ] (δ = 0 ou 1) est c_{n+δ}.c_{n} où c_{n} = \frac{(2n)!}{(n+1)!n!} est le n^{ème} nombre de Catalan, et affinons ensuite ce résultat.

1 Les résultats principaux

Rappelons tout d’abord la définition des paramètres suivants sur les permutations de S_{n} :

pour i ∈ [n − 1], l’indice i est appelé une montée de π si et seulement si π(i) < π(i + 1), pour i ∈ [n], l’élément π(i) est dit

minimum à gauche si et seulement si π(i) < π(j) pour tout 1 ≤ j < i, maximum à gauche si et seulement si π(i) > π(j) pour tout 1 ≤ j < i.

De plus, une permutation π de S_{n} est alternante si et seulement si pour tout i ∈ [⌊\frac{n}{2}⌋] , π(2i − 1) < π(2i) > π(2i + 1).

Définition 1 Une permutation π de S_{n} est une permutation de Baxter si et seulement si, pour tout entier p ∈ [n − 1], π se factorise de manière unique sous la forme

π = π′.p. π^{<} . π^{>} .p+1.π′′ ou π = π′.p+1. π^{>} . π^{<} .p.π′′

où toutes les lettres de π^{<} sont inférieures à p et toutes celles de π^{>} sont supérieures à p + 1. On note Baxter_{n} l’ensemble des permutations de Baxter sur [n] = {1, 2, …, n}.

\underline{Exemple}. La permutation 4236571 appartient à Baxter_{7}. Par exemple,

pour p = 4, π^{<}= 23 et π^{>}= 6.

Dans ce travail, nous donnons une preuve combinatoire de la formule suivante due à C.L. Mallows [10], lequel ne donne pas d’interprétation simple (dans le sens de paramètres classiques sur les permutations) de i et s.

Théorème 1 Le nombre de permutations de Baxter sur [n] ayant m montées, i minima à gauche et s maxima à gauche est

\binom{n + 1}{m + 1}\frac{s.i}{n.(n + 1)} [\binom{n − s − 1}{n − m − 2}\binom{n − i − 1}{m − 1} − \binom{n − s − 1}{n − m − 1}\binom{n − i − 1}{m}]

De plus, la preuve du théorème 1 nous permet d’affiner un résultat dû à R. Cori, S. Dulucq et X. Viennot [3], obtenu lors de la résolution d’un problème de R.C. Mullin [11] sur l’énumération de certaines familles de cartes planaires.

Théorème 2 Le nombre de permutations de Baxter alternantes sur [2n + δ] où δ ∈ {0, 1} ayant i minima à gauche et s maxima à gauche est

\frac{i}{n + δ − i}\binom{2(n + δ) − i − 1}{n + δ}.\frac{s − 1}{n − s + 1}\binom{2n − s}{n}

2 La correspondance entre les permutations de Baxter et les triplets de chemins deux à deux disjoints

Cette correspondance entre permutations de Baxter et triplets de chemins deux à deux disjoints est la composition de deux bijections, la première reliant les permutations de Baxter et les arbres jumeaux [5], la seconde reliant les arbres jumeaux et les triplets de chemins deux à deux disjoints.

2.1 La bijection entre les permutations de Baxter et les arbres jumeaux

Nous rappelons ici brièvement une bijection entre les permutations de Baxter et les arbres jumeaux établie par S. Dulucq et O. Guibert [5].

Soit A_{n} l’ensemble des arbres binaires ayant n sommets. Ainsi, |A_{n}| = c_{n} = \frac{(2n)!}{(n+1)!n!}.

Définition 2 L’ensemble des arbres jumeaux J_{n} ⊆ A_{n} × A_{n} est l’ensemble

J_{n} = {(a_{1}, a_{2}) : a_{1}, a_{2} ∈ A_{n} et Θ(code(a_{1})) = Θ^{c}(code(a_{2}))} où Θ consiste en l’étiquetage des feuilles gauches [resp. droites] d’un arbre

binaire (une fois complété) par la lettre 0 [resp. 1] excepté les deux feuilles extrêmes et Θ^{c} est identique à Θ modulo l’échange des lettres 0 et 1.

Figure 1: Deux arbres jumeaux de J_{7}.

Figure 2: Une permutation de Baxter, ses arbres binaires croissant et décroissant, et les arbres jumeaux lui correspondant.

Théorème 3 [5] Il existe une bijection (cf. figure 2) entre les permutations de Baxter sur [n] et les arbres jumeaux de J_{n}. De plus, à une permutation de Baxter ayant m montées, i minima à gauche et s maxima à gauche correspond des arbres jumeaux tels que le premier arbre binaire a m arêtes droites et i sommets sur sa branche gauche tandis que le second arbre binaire a s sommets sur sa branche gauche.

2.2 La bijection entre les arbres jumeaux et les triplets de chemins deux à deux disjoints

Cette bijection entre les arbres jumeaux et les triplets de chemins deux à deux disjoints consiste pour l’essentiel à concrétiser le caractère jumeau sur les deux polyominos parallélogrammes obtenus à partir des deux arbres binaires par la bijection de M. Delest et X. Viennot [4].

Figure 3: Un triplet de chemins deux à deux disjoints de T_{7}.

Définition 3 T_{n} est l’ensemble des triplets de chemins deux à deux disjoints allant respectivement des 3 points de coordonnées (0, n−1), (1, n), (2, n+1) aux 3 points de coordonnées (m, m), (m + 1, m + 1), (m + 2, m + 2) en empruntant seulement des pas Est et Nord, où m parcourt l’intervalle [0, n − 1].

Théorème 4 Il existe une bijection (cf. figure 4) entre arbres jumeaux de J_{n} et triplets de chemins deux à deux disjoints de T_{n}. De plus, à un couple d’arbres jumeaux tel que le premier arbre binaire a m arêtes droites et i sommets sur sa branche gauche tandis que le second arbre binaire a s sommets sur sa branche gauche correspond un triplet de chemins deux à deux disjoints allant des 3 points de coordonnées (1, n − i), (1, n), (s + 1, n) respectivement aux 3 points de coordonnées (m, m), (m + 1, m + 1), (m + 2, m + 2) en empruntant des pas Est et Nord.

Lemme 1 [4] Il existe une bijection entre arbres binaires ayant n sommets, m arêtes droites et dont la branche gauche contient l sommets et couples de chemins disjoints (ou deux polyominos parallélogrammes) allant respectivement des 2 points de coordonnées (0, n − 1), (1, n) aux 2 points de coordonnées (m, m), (m+1, m+1) en empruntant des pas Est et Nord, le chemin supérieur débutant par exactement l − 1 pas Nord.

\underline{Preuve} du théorème 4. Après avoir appliqué la bijection du lemme 1 aux deux arbres jumeaux, les deux couples de chemins disjoints correspondants ont leurs seconds chemins complémentaires. Une symétrie par rapport à la diagonale du second couple permet de coller ces deux couples, donnant ainsi un triplet de chemins deux à deux disjoints.

2.3 Enumération des permutations de Baxter

\underline{Preuve} du théorème 1. Par une preuve en tout point identique (même involution) à celle décrite dans l’article de I.M. Gessel et X. Viennot [7], on montre que le nombre de triplets de chemins deux à deux disjoints allant des 3 points de coordonnées (1, n − i), (1, n), (s + 1, n) aux 3 points de coordonnées (m, m), (m + 1, m + 1), (m + 2, m + 2) est donné par un déterminant 3 × 3 équivalent à la formule de C.L. Mallows.

Permutations de Baxter 7

Figure 4: Des arbres jumeaux aux triplets de chemins deux à deux disjoints.

Notre correspondance nous permet de retrouver le résultat dû à F.R.K. Chung, R.L. Graham, V.E. Hoggatt et M. Kleiman [2], démontré ensuite combinatoirement par X. Viennot [12]. De plus, nous retrouvons un résultat dû à R. Cori, S. Dulucq et X. Viennot [3].

References

[1] G. Baxter, On fixed points of the composite of commuting functions, Proc. of AMS 15 (1964), 851-855.

[2] F.R.K. Chung, R.L. Graham, V.E. Hoggatt et M. Kleiman, The number of Baxter permutations, JCT (Series A) 24 (1978), 382-394.

[3] R. Cori, S. Dulucq et G. Viennot, Shuffle of parenthesis systems and Baxter permutations, JCT (Series A) 43 (1986), 1-22.

[4] M. Delest et X. Viennot, Algebraic languages and polyominoes enumeration, TCS 34 (1984), 169-206.

[5] S. Dulucq et O. Guibert, Mots de piles, tableaux standards et permutations de Baxter, 6^{ème} conférence FPSAC, Dimacs (1994), soumis à Disc. Math.

[6] F. Françon et X. Viennot, Permutations selon les pics, creux, doublesmontées, doubles-descentes, nombres d’Euler et de Genocchi, Disc. Math. 28 (1979), 21-35.

[7] I.M. Gessel et G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300-321.

[8] S. Gire, Arbres, permutations à motifs exclus et cartes planaires : quelques problèmes algorithmiques et combinatoires, Thèse de l’Université Bordeaux I (1993).

[9] G. Kreweras, Sur les éventails de segments, Cahiers du BURO 15 (1970), 1-41.

[10] C.L. Mallows, Baxter permutations rise again, JCT (Series A) 27 (1979), 394-396.

[11] R.C. Mullin, The enumeration of hamiltonian polygons in triangular maps, Pacific J. of Math. 16 (1966), 139-145.

[12] G. Viennot, A bijective proof for the number of Baxter permutations, Séminaire Lotharingien de Combinatoire, Le Klebach (1981).

[13] J. West, Sorting twice through a stack, 3^{ème} conférence FPSAC, Bordeaux, TCS 117 (1993), 303-313.