Correspondances entre les différents types de bijections entre le groupe symétrique et les chemins de Motzkin valués

par

Arthur RANDRIANARIVONY^{1}

Résumé. – Le but de cette note est de trouver les liens entre les différents types de bijections entre le groupe symétrique et les chemins de Motzkin valués.

1. – Introduction. Depuis quelques années, les devéloppements en fractions continues des fonctions génératrices font l’objet d’un regain d’attention par certains combinatoristes. La théorie combinatoire des fractions continues de Flajolet [3] et l’existence des bijections entre les chemins de Motzkin valués et le groupe symétrique ([1], [4], [5], [6]) permettent de devélopper la fonction génératrice de certains polynômes générateurs du groupe symétrique en fraction continue de type Jacobi ou de type Stieltjes. En 1979, Françon et Viennot [5] ont construit une bijection entre le groupe symétrique et un ensemble de chemins de Motzkin valués appélés histoires de Laguerre. Dix ans plus tard, Foata et Zeilberger [4] ont construit eux-aussi une autre bijection entre ces deux ensembles. Récemment, Clarke, Steingrímsson et Zeng [2] ont trouvé une correspondance entre ces deux bijections, dont nous rappelons la construction dans le paragraphe suivant. Dans cette note, nous essayons de trouver les liens entre les autres bijections. Rappelons qu’un chemin de Motzkin de longueur n est un mot de l’alphabet

{ , , [figure] , [figure] }

tel que si l’on note

h_{i}(c) = #{j ≤ i/ c_{j} = [figure] } − #{j ≤ i/ c_{j} = [figure] },

alors h_{i}(c) ≥ 0 pour tout i et h_{n}(c) = 0 (avec la convention h_{0}(c) = 0). h_{i−1}(c) est appélé niveau du i-ème pas c_{i} du chemin. Le chemin c = [figure] [figure] [figure] [figure] [figure] [figure] [figure] peut être représenté par la figure 1. Si un chemin de Motzkin ne possède pas de pas horizontal, on dit que c’est un chemin de Dyck.

1Département de Mathématiques, Université Louis-Pasteur, 7, rue René Descartes, 67084 Strasbourg Cedex, France

[figure: 1; 2; 3; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; •; •; •; •; •; •; •; •; •; •]

fig. 1

Un chemin de Motzkin valué de longueur n est un couple (c, p) où c = c_{1}c_{2} ⋯ c_{n} est un chemin de Motzkin de longueur n et p = p_{1}p_{2} ⋯ p_{n} une suite d’entiers ≥ 0. Si p vérifie la condition 0 ≤ p_{i} ≤ h_{i−1}(c) si c_{i} = [figure] ou , et 0 ≤ p_{i} ≤ h_{i−1}(c) − 1 si c_{i} = [figure] ou , on dit que (c, p) est une histoire de Laguerre.

Si c est un chemin de Dyck et p_{i} = 0 pour c_{i} = [figure] , et, 0 ≤ p_{i} ≤ ⌈\frac{h_{i−1}(c)}{2}⌉ − 1 pour

c_{i} = [figure] où ⌈x⌉ est le plus petit entier ≥ x, on dit que (c, p) est une histoire de Laguerre subdivisée.

Un chemin de Motzkin bivalué de longueur n est un couple (c, ξ) où c = c_{1}c_{2} ⋯ c_{n} est un chemin de Motzkin de longueur n et ξ = (ξ_{1}, …, ξ_{n}) une suite de couples d’entiers ≥ 0 telle que, si ξ_{i} = (ξ_{i}^{−}, ξ_{i}^{+}) (1 ≤ i ≤ n), alors ξ_{i}^{−} = ξ_{i}^{+} = 0 si c_{i} = [figure] ; 0 ≤ ξ_{i}^{−} ≤ h_{i−1}(c) − 1, 0 ≤ ξ_{i}^{+} ≤ h_{i−1}(c) − 1 si c_{i} = [figure] ; 0 ≤ ξ_{i}^{−} ≤ h_{i−1}(c) − 1, ξ_{i}^{+} = 0 si c_{i} = ; ξ_{i}^{−} = 0, 0 ≤ ξ_{i}^{+} ≤ h_{i−1}(c) si c_{i} = .

On note respectivement HL(n), HLS(2n) et CB(n) l’ensemble des histoires de Laguerre de longueur n, des histoires de Laguerre subdivisées de longueur 2n et l’ensemble des chemins de Motzkin bivalués de longueur n.

2. – Correspondance entre la bijection de Françon - Viennot et la bijection de Foata-Zeilberger.

Étant donnée une permutation σ de [n], on dit que σ(i) (1 ≤ i ≤ n) est:

– un pic de σ si σ(i − 1) < σ(i) > σ(i + 1);

– un creux de σ si σ(i − 1) > σ(i) < σ(i + 1);

– une double montée de σ si σ(i − 1) < σ(i) < σ(i + 1);

– une double descente de σ si σ(i − 1) > σ(i) > σ(i + 1); avec la convention σ(0) = σ(n + 1) = 0.

Si σ^{−1}(i) < i > σ(i) (resp. σ^{−1}(i) > i < σ(i), σ^{−1}(i) < i < σ(i), σ^{−1}(i) ≥ i ≥ σ(i)), on dit que i est un pic (resp. un creux, une double montée, une double descente) de cycle de σ.

Théorème 1 [Françon-Viennot [5]]. – Il existe une bijection Ψ_{F V} : S_{n+1} ⟶ Γ_{n}, σ ↦ Ψ_{F V} (σ) = (c, p) telle que, pour 1 ≤ i ≤ n,

\begin{matrix}i est un pic de σ si et seulement si c_{i} = [figure] ; \\ i est un creux de σ si et seulement si c_{i} = [figure] ; \\ i est une double montée de σ si et seulement si c_{i} = ; \\ i est une double descente de σ si et seulement si c_{i} = . \end{matrix} (1)

où Γ_{n} désigne l’ensemble des chemins de Motzkin valués (c, p) de longueur n vérifiant 0 ≤ p_{i} ≤ h_{i−1}(c) pour tout i.

Construction. Soient σ ∈ S_{n+1} et i ∈ [n]. On décompose σ en une suite de mots m_{0}M_{0} ⋯ m_{k}M_{k}m_{k+1}, appelée i-décomposition de σ, telle que M_{0}, …, M_{k} soient des sous-mots non vides de σ ne contenant que des lettres ≥ i, et m_{0}, …, m_{k+1} des sousmots non vides, sauf éventuellement m_{0} et m_{k+1}, et ne contenant que des lettres < i. De la relation (1), on a:

h_{i−1}(c) = ∑_{j=0}^{k+1}(nb de creux dans m_{j} − nb de pics dans m_{j}).

Or,

nb de creux dans m_{0} (resp. m_{k+1}) = nb de pics dans m_{0} (resp. m_{k+1})

et,

nb de creux dans m_{j} = 1 + nb de pics dans m_{j} (1 ≤ j ≤ k).

Par conséquent, h_{i−1}(c) = k et on pose p_{i} = l si i ∈ M_{l}. On a bien 0 ≤ p_{i} ≤ h_{i−1}(c).

Si σ(n + 1) = n + 1, la i-décomposition de σ est m_{0}M_{0} ⋯ m_{k}M_{k}. Dans ce cas, si i est un pic ou une double descente de σ, nécessairement i ∉ M_{k}. Ce qui implique que k ≠ 0. Par conséquent, si c_{i} = \ ou , 0 ≤ p_{i} ≤ h_{i−1}(c) − 1.

Comme toute permutation σ de [n + 1] telle que σ(n + 1) = n + 1 peut être identifiée à une permutation de [n], alors on a le théorème suivant équivalent au précédent.

Théorème 2 [Françon-Viennot]. – Il existe une bijection Ψ′_{F V} : S_{n} ⟶ HL(n), σ ↦ (c, p) telle que, pour 1 ≤ i ≤ n,

\begin{matrix}i est un pic de σ si et seulement si c_{i} = [figure] ; \\ i est un creux de σ si et seulement si c_{i} = [figure] ; \\ i est une double montée de σ si et seulement si c_{i} = ; \\ i est une double descente de σ si et seulement si c_{i} = . \end{matrix} (2)

avec la convention σ(0) = 0 et σ(n + 1) = n + 1.

Remarque. Si B_{0}B_{1} ⋯ B_{r} est la décomposition de σ en une suite de blocs telle que B_{j} soit un sous-mot décroissant et maximal de σ pour tout j (voir [2]), et m_{0}M_{0} ⋯ m_{k}M_{k} la i-décomposition de σ, on note B_{i_{j}} le bloc contenant la dernière lettre de M_{j} (1 ≤ j ≤ k − 1). Soit M_{l} le sous-mot contenant i. Si M_{l} ≠ i, B_{i_{0}}, B_{i_{1}},…, B_{i_{k−1}} sont les seuls blocs qui embrassent i, c’est-à-dire les blocs B_{j} tels que O(B_{j}) < i < F (B_{j}) où O(B_{j}) et F (B_{j}) sont respectivement la plus petite et la plus grande lettre de B_{j} respectivement appelées ouvrant et fermant de B_{j}. Si M_{l} = i, il y a exactement k − 1 blocs qui embrassent i. On en déduit que

h_{i−1}(c) = \{ \begin{matrix}#\{blocs de σ qui embrassent i\} & si i n’est pas un pic; \\ #\{blocs de σ qui embrassent i\} + 1 & si i est un pic. \end{matrix}

et p_{i} est égal au nombre de blocs embrassant i et situés à gauche du bloc qui le contient.

Exemple 1. Soit σ = 8 2 3 1 10 9 4 6 7 5. Sa décomposition en blocs de descentes est 8 2 − 3 1 − 10 9 4 − 6 − 7 5. Si (c, p) = Ψ′_{F V} (σ), le chemin c est représenté par la figure 2 et p = 0 0 1 1 2 2 2 0 0 0.

[figure: 1; 2; 3; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; •; •; •; •; •; •; •; •; •]

fig. 2

Théorème 3 [Foata-Zeilberger [4]]. – Il existe une bijection Ψ_{F Z} : S_{n} ⟶ HL(n), σ ↦ (c, p) telle que, pour 1 ≤ i ≤ n,

\begin{matrix}i est un pic de cycle de σ si et seulement si c_{i} = [figure] ; \\ i est un creux de cycle de σ si et seulement si c_{i} = [figure] ; \\ i est une double montée de cycle de σ si et seulement si c_{i} = ; \\ i est une double descente de cycle de σ si et seulement si c_{i} = . \end{matrix} (3)

Soient σ(i_{1}), σ(i_{2}), …, σ(i_{k}) (resp. σ(j_{1}), σ(j_{2}), …, σ(j_{n−k})) les excédances (resp. les non-excédances) de σ, c’est-à-dire σ(i_{l}) > i_{l} (resp. σ(j_{l}) ≤ j_{l}) pour tout l. On note:

σ_{exc} = ( \begin{matrix}i_{1} & i_{2} & ⋯ & i_{k} \\ σ(i_{1}) & σ(i_{2}) & ⋯ & σ(i_{k}) \end{matrix} ) et σ_{nex} = ( \begin{matrix}j_{1} & j_{2} & ⋯ & j_{n−k} \\ σ(j_{1}) & σ(j_{2}) & ⋯ & σ(j_{n−k}) \end{matrix} )

Par construction, p_{σ(i_{1})}p_{σ(i_{2})} ⋯ p_{σ(i_{k})} est la table d’inversion à gauche de σ_{exc}; p_{σ(j_{1})}p_{σ(j_{2})} ⋯ p_{σ(j_{n−k})} est la table d’inversion à droite de σ_{nex}. Par suite, on obtient:

p_{i} = \{ \begin{matrix}#\{j < σ^{−1}(i); σ(j) > i\} & si σ^{−1}(i) < i; \\ #\{j > σ^{−1}(i); σ(j) < i\} & si σ^{−1}(i) ≥ i. \end{matrix}  (4)

D’autre part, on a:

h_{i−1}(c) = #{j < i; σ(j) ≥ i} = #{j < i; σ^{−1}(j) ≥ i}  (5)

En effet, la relation (3) entraîne que

h_{i}(c) = #{j ≤ i; j < σ^{−1}(j); j < σ(j)} − #{j ≤ i; j > σ^{−1}(j); j > σ(j)}
= #{j ≤ i; j < σ(j)} − #{j ≤ i; j ≥ σ^{−1}(j); j < σ(j)}
−#{j ≤ i; j > σ^{−1}(j); j > σ(j)}
= #{j ≤ i; j < σ(j)} − #{j ≤ i; j > σ^{−1}(j)}

Or, #{j ≤ i; j < σ(j)} = #{j ≤ i; σ(j) > i} + #{j ≤ i; j < σ(j) ≤ i} et, #{j ≤ i; j < σ(j) ≤ i} = #{j ≤ i; j > σ^{−1}(j)}.

Exemple 2. Soient σ = 8 3 1 9 7 5 6 4 10 2 et (c, p) = ψ_{F Z}(σ). La décomposition en cycles de σ est (1 8 4 9 10 2 3)(5 7 6). Donc c est déterminé par la figure 2. D’autre part, on a:

σ_{exc} = ( \begin{matrix}1 & 2 & 4 & 5 & 9 \\ 8 & 3 & 9 & 7 & 10 \end{matrix} ) et σ_{nex} = ( \begin{matrix}3 & 6 & 7 & 8 & 10 \\ 1 & 5 & 6 & 4 & 2 \end{matrix} )

Par suite p = 0 0 1 1 2 2 2 0 0 0.

Récemment, Clarke, Steingrímsson et Zeng [2] ont prouvé le théorème suivant.

Théorème 4. – Il existe une bijection Φ de S_{n} sur S_{n} telle que Ψ′_{F V} = Ψ_{F Z} ∘ Φ.

Construction de Φ. Soit π ∈ S_{n}, π = B_{0}B_{1} ⋯ B_{r} sa décomposition en blocs de descentes. Pour tout i ∈ [n], on note e_{i} le nombre de blocs embrassant i et situés à sa gauche. On pose d’autre part F = {i ∈ [n]; i est un creux ou une double descente de π} = {i_{1}, i_{2}, …, i_{k}}; F′ = {i ∈ [n]; i est un pic ou une double descente de π}; G = {i ∈ [n]; i est un pic ou une double montée de π} = {j_{1}, j_{2}, …, j_{n−k}}; G′ = {i ∈ [n]; i est un creux ou une double montée de π}.

On définit Φ(π) = σ de la façon suivante:

(i) σ(F) = F′ tel que e_{σ(i_{1})}e_{σ(i_{2})} ⋯ e_{σ(i_{k})} soit la table d’inversion à gauche de σ(i_{1})σ(i_{2}) ⋯ σ(i_{k}); (ii) σ(G) = G′ tel que e_{σ(j_{1})}e_{σ(j_{2})} ⋯ e_{σ(j_{n−k})} soit la table d’inversion à droite de σ(j_{1})σ(j_{2}) ⋯ σ(j_{n−k}).

Exemple 3. Soit π = 8 2 3 1 10 9 4 6 7 5. Sa décomposition en blocs de descentes est 8 2 − 3 1 − 10 9 4 − 6 − 7 5. On a e = e_{1}e_{2} ⋯ e_{10} = 0 0 1 1 2 2 2 0 0 0. D’autre part, F = {1, 2, 4, 5, 9}, F′ = {3, 7, 8, 9, 10}, G = {3, 6, 7, 8, 10} et G′ = {1, 2, 4, 5, 6}. On a donc

σ_{exc} = ( \begin{matrix}1 & 2 & 4 & 5 & 9 \\ 8 & 3 & 9 & 7 & 10 \end{matrix} ) et σ_{nex} = ( \begin{matrix}3 & 6 & 7 & 8 & 10 \\ 1 & 5 & 6 & 4 & 2 \end{matrix} )

Par conséquent, Φ(π) = σ = 8 3 1 9 7 5 6 4 10 2. D’après les exemples 1 et 2, on a bien Ψ′_{F V} (π) = Ψ_{F Z}(σ)

3. – Correspondance entre la bijection de Foata-Zeilberger et la bijection de Biane. Dans son article [1], Biane a démontré le théorème suivant. Théorème 5. – Il existe une bijection Ψ_{B} de S_{n} sur CB(n) telle que, si Ψ_{B}(σ) = (c, ξ), alors, pour 1 ≤ i ≤ n,

\begin{matrix}i est un pic de cycle de σ si et seulement si c_{i} = [figure] ; \\ i est un creux de cycle de σ si et seulement si c_{i} = [figure] ; \\ i est une double montée de cycle de σ si et seulement si c_{i} = ; \\ i est une double descente de cycle de σ si et seulement si c_{i} = . \end{matrix} (6)

Par construction de Ψ_{B}, on a:

ξ_{i}^{−} = \{ \begin{matrix}= 0 & si σ^{−1}(i) ≥ i; \\ #\{j < σ^{−1}(i); σ(j) > i\} & si σ^{−1}(i) < i; \end{matrix}

ξ_{i}^{+} = \{ \begin{matrix}= 0 & si σ(i) > i; \\ #\{j < σ(i); σ^{−1}(j) > i\} & si σ(i) ≤ i. \end{matrix} .

(7)

Exemple 4. Soit σ = 5 3 1 8 7 2 6 4 11 10 9. Elle est représentée par le diagramme suivant:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]

Si (c, ξ) = ψ_{B}(σ), alors le chemin c est représenté par la figure 3 et ξ = (0, 0)(0, 0)(1, 0)(0, 0)(0, 0)(0, 0)(1, 1)(0, 0)(0, 0)(0, 1)(0, 0)

[figure: 1; 2; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; •; •; •; •; •; •; •; •; •; •]

fig. 3

Théorème 6. – Il existe une bijection θ de CB(n) sur HL(n) telle que Ψ_{F Z} = θ∘Ψ_{B}.

Démonstration. Soient σ ∈ S_{n} et (c, ξ) = Ψ_{B}(σ). Notons A = {j; c_{j} = [figure] ou } = {i_{1}, …, i_{k}} et B = {j; c_{j} = [figure] ou } = {j_{1}, …, j_{k}}. On a nécessairement i_{1} = 1, j_{k} = n et i_{l} ≤ j_{l} pour tout l. Remarquons d’autre part que, pour 1 ≤ l ≤ k, ξ_{j_{l}}^{+} ≤ h_{i−1}(c) − 1 ≤ k − (l − 1) − 1 = k − l si c_{j_{l}} = [figure] ; ξ_{j_{l}}^{+} ≤ h_{i−1}(c) ≤ (k − 1) − (l − 1) = k − l si c_{j_{l}} = . Soit donc α la bijection de A sur B telle que ξ_{α(i_{1})}^{+}ξ_{α(i_{2})}^{+} ⋯ ξ_{α(i_{k})}^{+} soit la table d’inversion à gauche de α(i_{1})α(i_{2}) ⋯ α(i_{k}). Soit p = p_{1}p_{2} ⋯ p_{n} la suite définie par:

p_{i} = ξ_{i}^{−} si c_{i} = [figure] ou  et p_{i} = ξ_{α(i)}^{+} si c_{i} = [figure] ou .  (8)

Montrons que θ : (c, ξ) ↦ (c, p) applique bijectivement CB(n) sur HL(n) et que (c, p) = Ψ_{F Z}(σ). Pour cela, montrons que α(i) ≥ i pour tout i ∈ A. Par construction, α^{−1}(j_{1}) est le m_{1}-ème élément de A où m_{1} = ξ_{j_{1}}^{+} +1: α^{−1}(j_{1}) = i_{m_{1}}. Si c_{j_{1}} = [figure] , m_{1} ≤ h_{j_{1}−1} = #{j < j_{1}; c_{j} = [figure] } − #{j < j_{1}; c_{j} = [figure] } = #{j < j_{1}; c_{j} = [figure] }. On a dans ce cas i_{1} < j_{1}, i_{2} < j_{1}, …, i_{m_{1}} < j_{1}. Si c_{j_{1}} = , j_{1} ∈ A et m_{1} − 1 ≤ h_{j_{1}−1} = #{j < j_{1}; c_{j} = [figure] }. Par conséquent, i_{1} < j_{1}, i_{2} < j_{1}, …, i_{m_{1}−1} < j_{1} et par suite i_{m_{1}} ≤ j_{1}. Dans les deux cas, on a toujours α^{−1}(j_{1}) ≤ j_{1}. Soit maintenant α_{1} la restriction de α à A_{1} = A\{i_{m_{1}}}. ξ_{α(i_{1})}^{+} ⋯ ξ_{α(i_{m_{1}−1})}^{+}ξ_{α(i_{m_{1}+1})}^{+} ⋯ ξ_{α(i_{k})}^{+} étant la table d’inversion à gauche de α_{1}(i_{1})α_{1}(i_{m_{1}−1})α_{1}(i_{m_{1}+1}) ⋯ α_{1}(i_{k}), on peut appliquer le résultat précédent à α_{1}: i_{m_{2}} = α_{1}^{−1}(j_{2}) ≤ j_{2}, c’est-à-dire α^{−1}(j_{2}) ≤ j_{2}. Par itération, on obtient α^{−1}(j_{l}) ≤ j_{l} pour tout l. Ainsi, pour tout i ∈ [n],

\begin{aligned}h_{i−1}(c) & = #\{j < i; j ∈ A\} − #\{j < i; j ∈ B\} \\ & = #\{j < i; j ∈ A\} − #\{j < i; j ∈ A, α(j) < i\} \\ & = #\{j < i; j ∈ A, α(j) ≥ i\}. \end{aligned}  (9)

Il en résulte que, si c_{i} = [figure] ou , p_{i} = ξ_{i}^{−} ≤ h_{i−1}(c) − 1; si c_{i} = [figure] ou , p_{i} = ξ_{α(i)}^{+} = #{k < i; α(k) > α(i)} ≤ #{k < i; α(k) > i} ≤ h_{i−1}(c).

Ce qui prouve que (c, p) ∈ HL(n). Par ailleurs, puisque α est bijective, θ est clairement bijective. Enfin, les relations (3) et (6) entraînent que les chemins de Motzkin associés à σ respectivement par Ψ_{B} et Ψ_{F Z} sont identiques. De plus, on déduit des relations (5) et (9) que α est la restriction de σ^{−1} à A. Compte tenu des relations (4), (7) et (8), on a enfin Ψ_{F Z}(σ) = (c, p).

Exemple 5. Prenons le chemin bivalué (c, ξ) défini dans l’exemple 4. Si (c, p) = θ(c, ξ), on a:

α = ( \begin{matrix}1 & 2 & 4 & 6 & 9 & 10 \\ 3 & 6 & 8 & 7 & 11 & 10 \end{matrix} ) et p = 0 0 1 0 0 1 1 0 0 1 0

Or, si σ = ψ_{F Z}^{−1}(c, p), on a

σ_{exc} = ( \begin{matrix}1 & 2 & 4 & 5 & 9 \\ 5 & 3 & 9 & 7 & 11 \end{matrix} ) et σ_{nex} = ( \begin{matrix}3 & 6 & 7 & 8 & 10 & 11 \\ 1 & 2 & 6 & 4 & 10 & 9 \end{matrix} )

Donc σ = 5 3 1 8 7 2 6 4 11 10 9. D’après l’exemple 4, on a alors Ψ_{F Z}(σ) = θ ∘ Ψ_{B}(σ).

4. – Correspondance entre la bijection de Biane et la bijection de Médicis-Viennot. de Médicis et Viennot [6] ont construit en trois étapes une bijection entre le groupe symétrique et les histoires de Laguerre subdivisées, qui peut être traduite par le théorème suivant. Théorème 7. – L’application Ψ_{MV} : σ ↦ (γ, p) définie par

\begin{matrix}(i) & \{ \begin{matrix}γ_{2i−1} & = [figure] & si et seulement si σ^{−1}(i) < i; \\ γ_{2i} & = [figure] & si et seulement si σ(i) ≤ i; \end{matrix} \\ (ii) & \{ \begin{matrix}p_{i} & = 0 & si γ_{i} = [figure] ; \\ p_{2i−1} & = #\{j < σ^{−1}(i); σ(j) > i\} & si γ_{2i−1} = [figure] ; \\ p_{2i} & = #\{j < σ(i); σ^{−1}(j) > i\} & si γ_{2i} = [figure] . \end{matrix} \end{matrix} (10)

est une bijection de S_{n} sur HLS(2n).

[figure: •; •; •; •; j; σ^{−1}(i); i; σ(j); (a); σ^{−1}(i); i; •; •; (b); i; σ(i); •; •; (c); •; •; •; •; i; σ^{−1}(j); j; σ(i); (d)]

(a) : γ_{2i−1} = [figure] , p_{2i−1} = #{j < σ^{−1}(i); σ(j) > i}

(b) : γ_{2i−1} = [figure] , p_{2i−1} = 0

(c) : γ_{2i} = [figure] , p_{2i} = 0

(d) : γ_{2i} = [figure] , p_{2i} = #{j < σ(i); σ^{−1}(j) > i}

Soit σ ∈ S_{n}, (γ, p) = Ψ_{MV} (σ). On a:

h_{2i}(γ) = #{j ≤ 2i; γ_{j} = [figure] } − #{j ≤ 2i; γ_{j} = [figure] }
= #{j ≤ i; σ(j) > j} + #{j ≤ i; σ^{−1}(j) ≥ j}
−#{j ≤ i; σ(j) ≤ j} − #{j ≤ i; σ^{−1}(j) < j}

\begin{aligned}Or, #\{j ≤ i; σ(j) > j\} & = #\{j ≤ i; σ(j) > i\} + #\{j ≤ i; j < σ(j) ≤ i\} \\ & = #\{j ≤ i; σ(j) > i\} + #\{k ≤ i; σ^{−1}(k) < k\} \end{aligned}

\begin{aligned}et #\{j ≤ i; σ^{−1}(j) ≥ j\} & = #\{j ≤ i; σ^{−1}(j) > i\} + #\{j ≤ i; j ≤ σ^{−1}(j) ≤ i\} \\ & = #\{j ≤ i; σ^{−1}(j) > i\} + #\{k ≤ i; σ(k) ≤ k\}. \end{aligned}

Donc

h_{2i}(γ) = #{j ≤ i; σ(j) > i} + #{j ≤ i; σ^{−1}(j) > i}
= #{j ≤ i; σ(j) > i} + i − #{j ≤ i; σ^{−1}(j) ≤ i}
= #{j ≤ i; σ(j) > i} + i − #{k ≤ i; σ(k) ≤ i}.

D’où

h_{2i}(γ) = 2#{j ≤ i; σ(j) > i} = 2#{j ≤ i; σ^{−1}(j) > i}.

On démontre de même que

h_{2i−1}(γ) = 2#{j < i; σ(j) > i} + 1 = 2#{j ≤ i; σ^{−1}(j) ≥ i} − 1.

Exemple 6. Soit σ = 5 3 1 8 7 2 6 4 11 10 9, (γ, p) = ψ_{MV} (σ). σ est représentée par le diagramme suivant:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]

Alors γ est représenté par la figure 4 suivante et p = 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0.

[figure: 1; 2; 3; 4; 5; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •]

fig. 4

Théorème 8. – Il existe une bijection φ de CB(n) sur HLS(2n) telle que Ψ_{MV} = φ ∘ Ψ_{B}.

Démonstration. Soient σ ∈ S_{n}, (c, ξ) = Ψ_{B}(σ) et (γ, p) = Ψ_{MV} (σ). Les relations (6) et (10)(i) montrent que γ est le décontracté de c, c’est-à-dire γ et c vérifient la relation suivante:

\{ \begin{matrix}γ_{2i−1} = [figure] , γ_{2i} = [figure] & ⟺ & c_{i} = [figure] \\ γ_{2i−1} = [figure] , γ_{2i} = [figure] & ⟺ & c_{i} = [figure] \\ γ_{2i−1} = [figure] , γ_{2i} = [figure] & ⟺ & c_{i} = \\ γ_{2i−1} = [figure] , γ_{2i} = [figure] & ⟺ & c_{i} = \end{matrix}  (11)

Les relations (7) et (10)(ii) impliquent, d’autre part, que p = p_{1}p_{2} ⋯ p_{2n} et ξ = ξ_{1}ξ_{2} ⋯ ξ_{n} sont liés par la relation:

Pour tout i ∈ [n], p_{2i−1} = ξ_{i}^{−}et p_{2i} = ξ_{i}^{+}.  (12)

Considérons alors l’application φ : (c, ξ) ↦ (γ, p), où (c, ξ) ∈ CB_{n} et (γ, p) le chemin marqué défini par les relations (11) et (12). On a:

h_{2j}(γ) = h_{2j−2}(γ) + 2χ(c_{j} = [figure] ) − 2χ(c_{j} = [figure] ) pour tout j ∈ [n].

Ce qui entraîne que

h_{2i}(γ) = 2h_{i}(c) pour tout i ∈ [n].

Soit donc k ∈ [2n].

a) k impair : k = 2i − 1

– si γ_{k} = [figure] , c_{i} = [figure] ou et par suite ξ_{i}^{−} = 0. Donc p_{k} = 0.

– si γ_{k} = [figure] , c_{i} = [figure] ou et par suite 0 ≤ ξ_{i}^{−} ≤ h_{i−1}(c) − 1. Donc 0 ≤ p_{k} ≤

\frac{h_{k−1}}{2} (γ) − 1.

b) k pair : k = 2i

– si γ_{k} = [figure] , c_{i} = [figure] ou et par suite ξ_{i}^{+} = 0. Donc p_{k} = 0.

– si γ_{k} = [figure] , c_{i} = [figure] ou :

Si c_{i} = [figure] , γ_{2i−1} = [figure] , et 0 ≤ ξ_{i}^{+} ≤ h_{i−1}(c) − 1 = \frac{h_{2i−2}(γ)}{2} − 1 = \frac{h_{2i−1}(γ) + 1}{2} − 1.

Par suite, 0 ≤ p_{k} ≤ \frac{h_{k−1}(γ) + 1}{2} − 1.

Si c_{i} = , γ_{2i−1} = [figure] , et 0 ≤ ξ_{i}^{+} ≤ h_{i−1}(c) = \frac{h_{2i−2}(γ)}{2} = \frac{h_{2i−1}(γ) − 1}{2}.

Par suite, 0 ≤ p_{k} ≤ \frac{h_{k−1}(γ) − 1}{2} = \frac{h_{k−1}(γ) + 1}{2} − 1.

On en déduit que φ est bien une application de CB_{n} vers HLS(2n). D’autre part, d’après ce qui précède, on a les équivalences:

\begin{aligned}0 ≤ p_{2i−1} ≤ \frac{h_{2i−2}}{2} − 1 & ⟺ & 0 ≤ ξ_{i}^{−} ≤ h_{i−1} − 1; \\ 0 ≤ p_{2i} ≤ \frac{h_{2i−1} + 1}{2} − 1 & ⟺ & \{ \begin{matrix}0 ≤ ξ_{i}^{+} ≤ h_{i−1} − 1 et c_{i} = [figure] ; \\ ou \\ 0 ≤ ξ_{i}^{+} ≤ h_{i−1} et c_{i} = . \end{matrix} \end{aligned}

Ce qui montre que φ est bijective et Ψ_{MV} = φ ∘ Ψ_{B}.

Exemple 7. Soit σ = 5 3 1 8 7 2 6 4 11 10 9. Le chemin de Motzkin bivalué (c, ξ) associé par ψ_{B} est défini dans l’exemple 5. Soit (γ, p) = φ(c, ξ). Alors γ est représenté par la figure 4 et p = 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0. Les exemples 5 et 6 montrent que Ψ_{MV} (σ) = φ ∘ Ψ_{B}(σ).

BIBLIOGRAPHIE

[1] BIANE (P.). — Permutations suivant le type d’excédance et le nombre d’inversions, et interprétation combinatoire d’une fraction continue de Heine, Europ. J. Combinatorics, 14 (1993), 277 − 284.

[2] CLARKE (R.J.), STEINGR^{}ÍMSSON (E.) et ZENG (J.). — New Euler-Mahonian statistics on permutations, Preprint 1996.

[3] FLAJOLET (P.). — Combinatorial aspects of continued fractions, Disc. Math., 32 (1980), 125 − 161.

[4] FOATA (D.) et ZEILBERGER (D.). — Denert’s Permutation Statistic is indeed Euler-Mahonian, Studies in Appl. Math., 83 (1990), 31 − 59.

[5] FRANÇON (J.) et VIENNOT (X.G.). — Permutations selon les pics, creux, doubles montées, doubles descentes, nombres d’Euler, nombres de genocchi, Disc. Math., 28 (1979), 21 − 35.

[6] de M^{}ÉDICIS (A.) et VIENNOT (X.G.). — Moments des q−polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. Applied Math., 15 (1994), 262 − 304.