Enumération de permutations à motifs exclus

S. Dulucq, S. Gire, O. Guibert, J. West ^{∗}

LaBRI, Université Bordeaux I

E-mail : name@labri.u-bordeaux.fr

De nombreux auteurs se sont intéressés à l’énumération de permutations dont certains motifs (sous-mots) sont exclus. En particulier, D.E. Knuth [7], considérant l’ensemble des permutations triables par passage dans une pile, a montré qu’elles correspondaient à l’ensemble des permutations ne possédant pas de sous-suite de type 231, c’est à dire de sous-suite formée des éléments j, k, i tels que i < j < k (ensemble que l’on notera S_{n}(231)). Il montre que le nombre de permutations de S_{n}(231) est donné par le nième nombre de Catalan.

J. West [14] s’est intéressé au problème des permutations triables par deux passages consécutifs dans une pile en imposant une règle du jeu de type “tour de Hanoï” pour les empilements (c’est à dire qu’on ne peut empiler un élément j sur un élément i en sommet de pile lorsque i < j), problème différent de la généralisation considérée par D.E. Knuth [7] qui n’imposait aucun type de contrainte. J. West a caractérisé ces permutations en termes de permutations à motifs exclus; les motifs interdits sont 2341 et 3241, ce dernier motif étant autorisé dans le cas où il est lui même sous-suite du motif 35241 dans la permutation (ensemble noté S_{n}(2341, 3\overline{5}241)). Il a conjecturé que le nombre de ces permutations est 2(3n)!/((n + 1)!(2n + 1)!), conjecture démontrée par D. Zeilberger [15] de manière analytique (la preuve faisant intervenir une équation en trois variables de degrés respectifs 6, 8 et 9 résolue par l’utilisation de Maple). Dans un premier temps, D. Zeilberger avait cherché vainement une preuve combinatoire de ce résultat. En effet, il apparaît que ces nombres énumèrent une famille particulière de cartes, les cartes planaires pointées non séparables, selon le nombre d’arêtes (travaux de W.T. Tutte [12]).

∗Cet article est un résumé des travaux de Dulucq, Gire et West [6] et de Dulucq, Gire et Guibert [5].

Nous donnons une preuve combinatoire de cette conjecture en reliant la famille S_{n}(2341, 3\overline{5}241) des permutations triables par deux passages consécutifs dans une pile aux cartes planaires pointées non séparables ayant n + 1 arêtes (famille NS_{n+1}) par un chemin composé de 7 familles de permutations à motifs exclus.

Pour cela, nous utilisons la notion d’isomorphisme d’arbres de génération d’objets combinatoires. Il s’agit de construire un arbre infini dont les sommets sont les objets de la famille considérée, de telle manière qu’il contienne au niveau n tous les objets de taille n, chacun apparaissant une fois et une seule. Cet arbre est ensuite caractérisé comme étant “l’arbre de dérivation” d’un “système de réécriture”. La donnée d’un axiome (l’étiquette de la racine) et d’un jeu de règles de réécriture (qui fournit les étiquettes de tous les fils d’un sommet d’une étiquette donnée) permet de retrouver l’arbre de génération des objets considérés. Lorsque les arbres de génération de deux familles d’objets combinatoires correspondent au même système de réécriture, ils sont isomorphes. Ils induisent ainsi une bijection entre ces deux familles d’objets.

Pour chaque famille formant le chemin des cartes de NS_{n+1} aux permutations de S_{n}(2341, 3\overline{5}241), nous construisons son arbre de génération et donnons le système de réécriture qui le caractérise. Nous passons d’une famille à la suivante soit par isomorphisme d’arbre de génération, soit par des bijections classiques sur les permutations comme l’inverse, le miroir ou le complémentaire.

Nous déduisons de ces faits que les permutations sur [n] triables par deux passages consécutifs dans une pile sont énumérées par 2(3n)!/((n + 1)!(2n + 1)!). De plus, une analyse des systèmes de réécriture des arbres de dérivations de ces familles nous permet d’obtenir des formules d’énumération de ces permutations suivant divers paramètres (nombre d’élements saillants, nombre de descentes, nombre de descentes inverses). Ces formules sont déduites des formules donnant le nombre de cartes planaires pointées non séparables à n arêtes suivant le nombre de sommets (travaux de W.G. Brown et W.T. Tutte [2]), ou relativement au degré de la face pointée (travaux de W.G. Brown [1]).

1 Définitions et notations

1.1 Permutations à motifs exclus.

Soit S_{n} l’ensemble des n! permutations sur [n]= {1, 2, …, n}.

Définition 1 Une permutation π de S_{n} contient une sous-suite de type τ ∈ S_{k} si et seulement si il existe 1 ≤ i_{τ(1)} < i_{τ(2)} < … < i_{τ(k)} ≤ n telle que π(i_{1}) < π(i_{2}) < … < π(i_{k}) . On note S_{n}(τ) l’ensemble des permutations de S_{n} qui ne contiennent pas de sous-suite de type τ.

Exemple. La permutation π = 614753 appartient à S_{7}(2413) mais pas à S_{7}(3142) car la sous-suite (π(1), π(2), π(4), π(6)) = 6173 est de type 3142.

Définition 2 Une permutation barrée τ̄ sur [k] est une permutation de S_{k} dont on distingue un élément. Une permutation π de S_{n} contient une sous-suite de type τ̄ de S_{k} si et seulement si π contient une sous-suite de type τ̂ qui n’est pas elle même sous-suite d’une suite de type τ, où τ est la permutation sur [k] identique à τ̄ mais sans distinguer l’élément, et τ̂ la permutation sur [k − 1] constituée des k − 1 éléments non distingués de τ̄ ramenés à une permutation.

Exemple. τ̄ = 41\overline{3}52. π = 614753 ∈ S_{7}(τ̄) car la sous-suite (π(1), π(2), π(4), π(6)) = 6173 qui est de type τ̂ = 3142 est sous-suite de (π(1), π(2), π(3), π(4), π(6)) = 61473 qui est de type τ = 41352.

Définition 3 Pour toutes permutations τ_{1}, …, τ_{p}, barrées ou non, sur, respectivement [k_{1}], …, [k_{p}], on note S_{n}(τ_{1}, …, τ_{p}) = S_{n}(τ_{1}) ∩ … ∩ S_{n}(τ_{p}).

Définition 4 Pour toute permutation π de S_{n}, on considère saillsg(π) le nombre d’éléments saillants supérieurs gauches de π, c’est à dire

saillsg(π)=|{π(i) pour i ∈ [1, n], tel que π(i) > π(j) ∀j ∈ [1, i[}|

saillsd(π) le nombre d’éléments saillants supérieurs droits de π, c’est à dire

saillsd(π)=|{π(i) pour i ∈ [1, n], tel que π(i) > π(j) ∀j ∈]i, n]}|

saillig(π) le nombre d’éléments saillants inférieurs gauches de π, c’est à dire

saillig(π)=|{π(i) pour i ∈ [1, n], tel que π(i) < π(j) ∀j ∈ [1, i[}|

saillid(π) le nombre d’éléments saillants droits de π, c’est à dire

saillid(π)=|{π(i) pour i ∈ [1, n], tel que π(i) < π(j) ∀j ∈]i, n]}|

desc(π) le nombre de descentes de π, c’est à dire

desc(π)=|{i ∈ [1, n[, tel que π(i) > π(i + 1)}|

mont(π) le nombre de montées de π, c’est à dire

mont(π)=|{i ∈ [1, n[, tel que π(i) < π(i + 1)}|

descinv(π) le nombre de descentes inverses de π, c’est à dire le nombre de descentes de π^{−1} montinv(π) le nombre de montées inverses de π, c’est à dire le nombre de montées de π^{−1}

1.2 Cartes planaires pointées non séparables.

Les cartes et en particulier les cartes planaires sont des objets combinatoires sur lesquels de nombreux travaux ont été réalisés depuis ceux de Tutte dans les années 60. Ainsi, Cori [3] en a donné une représentation par un couple de permutations (σ, α), où α est une involution dans le cas des cartes et de nombreux travaux ont porté sur l’énumération de familles de cartes : Tutte [12, 13], Brown [1, 2], Mullin [11], Lehman et Walsh [9, 10], Cori et Vauquelin [4], …

Notre propos portera ici sur les cartes planaires pointées non séparables, c’est à dire les cartes planaires pour lesquelles un brin est distingué, et qui ne possèdent pas de point d’articulation c’est à dire qui ne peuvent être séparées en deux parties connexes en “coupant” en deux un sommet. Pour plus de détails, le lecteur pourra se référer à l’exposé sur les cartes de Cori [3] ou aux travaux de Tutte [12] sur les cartes non séparables.

Nous notons NS_{n} l’ensemble des cartes planaires pointées non séparables à n arêtes. L’énumération de ces cartes a été obtenue par Tutte [12] qui a montré que |NS_{n+1}| =

\frac{2}{(n + 1)(2n + 1)}\binom{3n}{n}.

Etant donnée une carte c de NS_{n}, le sommet distingué de c est le sommet contenant le brin distingué (sommet dont est issue l’arête pointée) et la face distinguée est la face située “à gauche” de l’arête pointée (cycle ασ contenant le brin distingué dans la représentation de la carte par un couple de permutations (α, σ) [3]).

Définition 5 Pour une carte c de NS_{n}, on définit ds(c) le degré du sommet distingué, df(c) le degré de la face distinguée, s(c) le nombre de sommets de la carte c, et f(c) le nombre de faces de la carte c.

2 Enumération des permutations de S_{n}(2341, 3\overline{5}241)

Théorème 6 L’ensemble des permutations triables par deux passages consécutifs dans une pile (famille S_{n}(2341, 3\overline{5}241)) est en bijection avec l’ensemble des cartes planaires pointées non séparables à n + 1 arêtes. Ainsi,

|S_{n}(2341, 3\overline{5}241)| = \frac{2}{(n + 1)(2n + 1)}\binom{3n}{n}

De plus, |S_{n}(2413, 45\overline{3}12)| = |S_{n}(2413, 5\overline{1}324)| = |S_{n}(2314, \overline{4}2513)| = |S_{n}(2341, 3\overline{5}241)|

= \frac{2}{(n + 1)(2n + 1)}\binom{3n}{n}

Pour démontrer ce théorème, nous exhibons dans un premier temps un arbre de génération des cartes planaires pointées non séparables, arbre qui contiendra au niveau n l’ensemble complet des cartes de NS_{n+1}. Nous considérons ensuite une suite de sept familles de permutations à motifs exclus qui permettent de relier combinatoirement les cartes planaires pointées non séparables à la famille S_{n}(2341, 3\overline{5}241) des permutations triables par deux passages dans une pile. Ces familles sont en bijection, soit parce qu’elles possèdent des arbres de génération isomorphes, soit parce qu’elles sont reliées par des bijections classiques sur les permutations. Le chemin conduisant à cette preuve est composé de quatre arbres de génération différents (voir figure 1).

Une analyse plus fine des systèmes de réécriture de ces arbres nous permet d’obtenir les distributions suivantes sur les familles de permutations à motifs exclus considérées.

Corollaire 7 Le nombre de permutations sur [n] triables par deux passages consécutifs dans une pile et ayant k descentes est

|\{π ∈ S_{n}(2341, 3\overline{5}241) : desc(π) = k\}| = \{ \begin{matrix}1 & si k = 0 \\ \binom{k + 1}{2}^{−1}\binom{2n − k − 1}{k − 1}\binom{n + k}{2k + 1} & sinon. \end{matrix}

De plus, |\{π ∈ S_{n}(2413, 45\overline{3}12) : descinv(π) = k\}| = |\{π ∈ S_{n}(2413, 5\overline{1}324) : mont(π) = k\}| = |\{π ∈ S_{n}(2314, \overline{4}2513) : descinv(π) = k\}|

= \{ \begin{matrix}1 & si k = 0 \\ \binom{k + 1}{2}^{−1}\binom{2n − k − 1}{k − 1}\binom{n + k}{2k + 1} & sinon. \end{matrix}

Corollaire 8 Le nombre de permutations sur [n] triables par deux passages consécutifs dans une pile et ayant k éléments saillants supérieurs droits est |\{π ∈ S_{n}(2341, 3\overline{5}241) : saillsd(π) = k\}|

= \frac{k + 1}{(2n − k + 1)!} ∑_{j=k+1}^{min(n+1,2k+2)} \frac{(3k − 2j + 2)(2j − k − 1)(j − 2)!(3n − j − k + 1)!}{(n − j + 1)!(j − k − 1)!(j − k)!(2k − j + 2)!}

De plus, |\{π ∈ S_{n}(2314, \overline{4}2513) : saillig(π)=k\}| = |\{π ∈ S_{n}(2413, 5\overline{1}324) : saillsd(π)=k\}| = |\{π ∈ S_{n}(2413, 5\overline{1}324) : saillid(π)=k\}| = |\{π ∈ S_{n}(2413, 45\overline{3}12) : saillsd(π)=k\}| = |\{π ∈ S_{n}(2413, 45\overline{3}12) : saillsg(π)=k\}|

= \frac{k + 1}{(2n − k + 1)!} ∑_{j=k+1}^{min(n+1,2k+2)} \frac{(3k − 2j + 2)(2j − k − 1)(j − 2)!(3n − j − k + 1)!}{(n − j + 1)!(j − k − 1)!(j − k)!(2k − j + 2)!}

Corollaire 9 Le nombre de permutations sur [n] triables par deux passages consécutifs dans une pile et ayant k descentes et k + 1 éléments saillants supérieurs droits est

|\{π ∈ S_{n}(2341, 3\overline{5}241) : saillsd(π) = k + 1, desc(π) = k\}| = \frac{1}{k + 1}\binom{n}{k}\binom{n − 1}{k}

De plus, |\{π ∈ S_{n}(2314, \overline{4}2513) : saillig(π) = k + 1, descinv(π) = k\}| Cartes planaires pointées non séparables NS_{n+1}

↑

arbres de génération isomorphes

↓

S_{n}(2413, 45\overline{3}12)

↑ −1 ∘ ∗

↓

S_{n}(2413, 21\overline{3}54)

↑

arbres de génération isomorphes

↓

S_{n}(2413, 5\overline{1}324)

↑ −1 ∘ ∗

↓

S_{n}(2413, \overline{4}2315)

↑

arbres de génération isomorphes

↓

S_{n}(2314, \overline{4}2513)

↑ c ↓

S_{n}(3241, \overline{2}4153)

↑

arbres de génération isomorphes

↓

S_{n}(3214, \overline{2}4135)

↑ −1 ∘ ∗

↓

permutations triables par deux passages dans une pile : S_{n}(2341, 3\overline{5}241) Figure 1: Le chemin menant des cartes planaires pointées non séparables aux permutations triables par deux passages dans une pile.

= |\{π ∈ S_{n}(2413, 5\overline{1}324) : saillsd(π) = k + 1, desc(π) = k\}| = |\{π ∈ S_{n}(2413, 5\overline{1}324) : saillid(π) = k + 1, mont(π) = k\}| = |\{π ∈ S_{n}(2413, 45\overline{3}12) : saillsd(π) = k + 1, descinv(π) = k\}| = |\{π ∈ S_{n}(2413, 45\overline{3}12) : saillsg(π) = k + 1, montinv(π) = k\}|

= \frac{1}{k + 1}\binom{n}{k}\binom{n − 1}{k}

2.1 Arbre de génération des cartes planaires pointées non séparables

Etant donnée une carte c de NS_{n}, on considère les deux opérations suivantes permettant de construire un certain nombre de cartes de NS_{n+1} par ajout d’une arête à c. Opération F. Cette opération consiste en la division en deux faces de la face distinguée de c, de df(c) − 1 façons différentes, par ajout d’une nouvelle arête issue du sommet distingué de c, cette arête ajoutée devenant l’arête distinguée de la carte construite. On note F_{i}(c), la ième carte ainsi obtenue, c’est à dire celle dont l’extrémité finale de l’arête distinguée est le ième sommet de la face distinguée de c. Opération S. Cette opération consiste en la division du sommet distingué de c en deux sommets de degrés i et ds(c) − i + 2 (2 ≤ i ≤ ds(c)) par ajout d’une arête qui devient l’arête distinguée de la nouvelle carte obtenue. Une telle carte est dite valide si et seulement si elle possède un point d’articulation lorsqu’on lui supprime son arête distinguée. On note S_{i}(c) la carte ainsi obtenue de sommet distingué de degré i (i ∈ [2, ds(c)]).

Remarques. Toute carte obtenue par l’application de S ou F à une carte de NS_{n} est une carte planaire pointée non séparable de NS_{n+1}. Les cartes S_{i}(c) non valides sont les cartes planaires pointées non séparables pouvant être obtenues par une opération F sur une carte c′.

Définition 10 On considère l’arbre infini A, dit arbre de génération des cartes planaires pointées non séparables construit de la manière suivante.

racine(A) := la carte planaire pointée non séparable à 2 arêtes, pour tout sommet s de A correspondant à une carte c,

fils(s) := {S_{i_{1}}(c), …, S_{i_{p}}(c), F_{1}(c), …, F_{df(c)−1}(c) : 2 ≤ i_{k} ≤ ds(c)et S_{i_{k}}(c)valide}.

La figure 2 donne l’arbre de génération A jusqu’au niveau 4 et indique la répartition des 91 cartes au niveau 5.

Proposition 11 A l’ensemble des sommets de A au niveau n correspond l’ensemble des cartes planaires pointées non séparables à n + 1 arêtes, chacune apparaissant une fois et une seule.

Afin de caractériser l’arbre A, nous associons à chaque carte non séparable une étiquette formelle et définissons un système de réécriture basé sur ces étiquettes et permettant de construire récursivement cet arbre.

Définition 12 Etant donnée une carte c de A, nous définissons son étiquette par label(c)= (x|df, ds, s, f; D_{1}, D_{2}, …, D_{df−1}) où x est le nombre de fils de c dans A, df = df(c), ds = ds(c), s = s(c), f = f(c) et où D_{i} = {d_{1}, …, d_{p}} contient les degrés d_{j} des sommets distingués des cartes S_{d_{j}}(F_{i}(c)) non valides.

Figure 2: Arbre de génération des cartes planaires pointées non séparables.

Figure 3: Arbre obtenu par dérivations formelles.

Proposition 13 L’arbre A de génération des cartes planaires pointées non séparables est isomorphe à l’arbre ayant pour racine l’étiquette (2|2, 2, 2, 2; ∅) et obtenu par application récursive des règles de dérivation suivantes (x|df, ds, s, f; D_{1}, …, D_{df−1}) ⟶ (df+i|df+1, ds_{i}, s+1, f; D_{1}^{i}, D_{1}^{i}, D_{2}^{i}, …, D_{df−1}^{i})

pour tout i ∈ [1, x − df + 1]

où \{ \begin{matrix}ds_{1} = 2 \\ ds_{i} = min\{k : k > ds_{i−1} et k ∉ D_{1}\} pour i > 1 \end{matrix}

et D_{j}^{i} = D_{j} ∩ {k : k ≤ ds_{i}} ⟶ (x + 2 − i − (|D_{i}| − |D_{1}|)|df − i + 1, ds + 1, s, f + 1; D_{i},

D_{i+1} ∪ {ds + 1}, …, D_{df−1} ∪ {ds + 1}) , pour i ∈ [1, df − 1]

La figure 3 donne l’arbre obtenu à partir de ces règles de dérivation jusqu’au niveau 4. La preuve des propositions 11 et 13 est donnée dans [6].

2.2 Arbres de génération des permutations à motifs exclus

Lemme 14 L’ensemble des permutations à motifs exclus S_{n}(3214, \overline{2}4135) est en bijection avec l’ensemble des permutations à motifs exclus S_{n}(3241, \overline{2}4153). De plus,

|\{π ∈ S_{n}(3214, \overline{2}4135) : saillsg(π) = i, montinv(π) = j\}|

= |\{π ∈ S_{n}(3241, \overline{2}4153) : saillsg(π) = i, montinv(π) = j\}|

Lemme 15 L’ensemble des permutations à motifs exclus S_{n}(2314, \overline{4}2513) est en bijection avec l’ensemble des permutations à motifs exclus S_{n}(2413, \overline{4}2315). De plus,

|\{π ∈ S_{n}(2314, \overline{4}2513) : saillig(π) = i, descinv(π) = j\}|

= |\{π ∈ S_{n}(2413, \overline{4}2315) : saillig(π) = i, descinv(π) = j\}|

Lemme 16 L’ensemble des permutations à motifs exclus S_{n}(2413, 5\overline{1}324) est en bijection avec l’ensemble des permutations à motifs exclus S_{n}(2413, 21\overline{3}54). De plus,

Figure 4: Arbre de génération de S_{n}(3214, \overline{2}4135).
|\{π ∈ S_{n}(2413, 5\overline{1}324) : saillid(π) = i, mont(π) = j\}|
= |\{π ∈ S_{n}(2413, 21\overline{3}54) : saillid(π) = i, mont(π) = j\}|

Lemme 17 L’ensemble des permutations à motifs exclus S_{n}(2413, 45\overline{3}12) est en bijection avec l’ensemble NS_{n+1} des cartes planaires pointées non séparables ayant n + 1 arêtes. De plus,

|\{π ∈ S_{n}(2413, 45\overline{3}12) : saillsd(π) = i, descinv(π) = j\}|

= |{c ∈ NS_{n+1} : df(c) = i + 1, s(c) = j + 2}|

Afin de montrer ces lemmes, nous construisons un arbre de génération pour chaque famille apparaissant dans la figure 1 et le caractérisons pas un sytème de réécriture faisant intervenir divers paramètres sur ces permutations (nombre de descentes, d’éléments saillants, …). Nous montrons que les systèmes correspondants aux familles S_{n}(3214, \overline{2}4135) et S_{n}(3241, \overline{2}4153) sont identiques, ainsi que ceux des familles S_{n}(2314, \overline{4}2513) et S_{n}(2413, \overline{4}2315) et des familles S_{n}(2413, 5\overline{1}324) et S_{n}(2413, 21\overline{3}54). Enfin, nous montrons que le système de réécriture caractérisant l’arbre de génération de la famille S_{n}(2413, 45\overline{3}12) est identique à celui des cartes planaires pointées non séparables donné dans la proposition 13.

Tous ces résultats sont détaillés dans [5, 6]. A titre d’exemple, nous donnons ici l’arbre de génération de la famille S_{n}(3214, \overline{2}4135).

Définition 18 On considère l’arbre infini T construit de la manière suivante.

racine(T ) := la permutation 1 de S_{1}(3214, \overline{2}4135). pour tout sommet s de T correspondant à une permutation σ de S_{n}(3214, \overline{2}4135),

fils(s) := \{π : π est dans S_{n+1}(3214, \overline{2}4135) et π donne σ par suppression de l’entier n + 1}.

Proposition 19 A l’ensemble des sommets de T au niveau n correspond l’ensemble des permutations à motifs exclus de S_{n}(3214, \overline{2}4135), chacune apparaissant une fois et une seule.

La figure 4 donne l’arbre de génération T jusqu’au niveau 4 et indique la répartition des 91 permutations au niveau 5.

Afin de caractériser l’arbre T , nous associons à chaque permutation une étiquette et définissons un système de réécriture basé sur ces étiquettes qui permet de construire récursivement cet arbre.

Définition 20 Etant donné un sommet s de T correspondant à une permutation π de S_{n}(3214, \overline{2}4135), nous définissons son étiquette par label(s)= (x|mi; p_{1}, …, p_{s}) où x est le nombre de fils de π dans T , mi=montinv(π) et p_{1}, …, p_{s} sont les positions des s éléments saillants supérieurs gauches de π.

Le système de réécriture de T est donné par la proposition suivante.

Proposition 21 L’arbre T est isomorphe à l’arbre ayant pour racine l’étiquette (2|0; 1) et obtenu par application récursive des règles de dérivation suivantes (x|mi; p_{1}, …, p_{s}) ⟶ (2 + p_{1}|mi; p_{1})

⟶ (2 + p_{2}|mi; p_{1}, p_{1} + i) pour i ∈ [1, p_{2} − p_{1}]

⟶ (2 + p_{3}|mi; p_{1}, p_{2}, p_{2} + i) pour i ∈ [1, p_{3} − p_{2}]
⋮
⟶ (2 + p_{s}|mi; p_{1}, …, p_{s−1} + i) pour i ∈ [1, p_{s} − p_{s−1}]
⟶ (x + 1|mi + 1; p_{1}, …, p_{s}, p_{s} + i) pour i ∈ [1, x − p_{s}]

La preuve de cette proposition est donnée dans [5].

2.3 Preuve des formules d’énumération

Le théorème 6 est une conséquence immédiate des lemmes 14, 15, 16 et 17, du fait que (S_{n}(2413, 45\overline{3}12)^{∗})^{−1} = S_{n}(2413, 21\overline{3}54), (S_{n}(2413, 5\overline{1}324)^{∗})^{−1} = S_{n}(2413, \overline{4}2315), S_{n}(2314, \overline{4}2513)^{c} = S_{n}(3241, \overline{2}4153) et (S_{n}(3214, \overline{2}4135)^{∗})^{−1} = S_{n}(2341, 3\overline{5}241) et des résultats de Tutte [12] sur l’énumération des cartes planaires pointées non séparables.

Des travaux de Brown et Tutte [2] donnant le nombre de cartes planaires pointées non séparables suivant le nombre de sommets et de ceux de Brown [1] relativement au degré de la face pointée, on déduit alors les corollaires 7 et 8.

Enfin, énumérer les cartes planaires pointées non séparables de NS_{n+1} qui ont k+2 sommets et dont la face distinguée est de degré k + 2 revient à énumérer les polygones à k + 2 sommets et possédant (n+1)−(k +2) arêtes intérieures ne se coupant pas. Ces objets sont en bijection avec les arbres planaires à n arêtes (n + 1 sommets) ayant k + 1 feuilles, donnant ainsi la distribution β sur les nombres de Catalan [8], soit \frac{1}{k+1} \binom{n}{k}\binom{n−1}{k}. Ce qui prouve le corollaire 9. □

References

[1] W.G. Brown. Enumeration of non separable planar maps, Can. J. Math. 15(1963), 526-545.

[2] W.G. Brown, W.T. Tutte. On the enumeration of rooted non separable planar maps, Can. J. Math. 16(1964), 572-577.

[3] R. Cori. Un code pour les graphes planaires et ses applications, Astérisque 27, Soc. Math. de France, 1975.

[4] R. Cori, B. Vauquelin. Planar maps are well labeled trees, Can. J. Math. 33(1981), 1023-1042.

[5] S. Dulucq, S. Gire, O. Guibert. Une preuve combinatoire de la conjecture de J. West, en préparation.

[6] S. Dulucq, S. Gire, J. West. Permutations à motifs exclus et cartes planaires pointées non séparables, Actes du colloque “Séries formelles et combinatoire algébrique”, Florence, Juin 1993.

[7] D.E. Knuth. The art of computer programming, vol 1, Addison-Wesley, Reading, 1973, 238-239.

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

[9] A.B. Lehman, T.S. Walsh. Counting rooted maps by genus I and II, J. Comb. Theory 13B(1972), 192-218 and 122-141.

[10] A.B. Lehman, T.S. Walsh. Counting rooted maps by genus III : nonseparable maps, J. Comb. Theory 18B(1975), 222-259.

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

[12] W.T. Tutte. A census of planar maps, Can. J. Math. 15(1963), 249-271.

[13] W.T. Tutte. On the enumeration of planar maps, Bull. Amer. Math. Soc. 74(1968), 249-271.

[14] J. West. Permutations with restricted subsequences and stack-sortable permutations, Ph.D. thesis, M.I.T. (1990)

[15] D. Zeilberger. A proof of Julian West’s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!/((n + 1)!(2n + 1)!), submitted to Disc. Math.