Ordres bipartitionnaires et statistiques sur les mots

Guo-Niu HAN (^{∗})

Dédié à Dominique Foata à l’occasion de son soixantième anniversaire

Submitted : February 9, 1995 ; Accepted : March 28, 1995

R^{}ÉSUM^{}É. — Soit U un ensemble de couples de lettres. Foata et Zeilberger [FZ] ont introduit les Ustatistiques pour les mots quelconques. Dans cette note, on établit une condition nécessaire et suffisante pour que les deux définitions “maj_{U} ” et “maj2_{U} ”, qu’on rencontre dans le cas classique [H], sont équivalentes. Il est remarquable que cette condition est exactement la même que celle qui a été trouvée pour l’équidistribution des deux statistiques “maj_{U} ” et “inv_{U} ”.

1. Introduction. — Soient X un alphabet et X^{∗} le monoïde libre engendré par X. Si w = x_{1}x_{2} ⋯ x_{m} ∈ X^{∗} est un mot de longueur m, on appelle réarrangement de w tout mot u = x_{σ_{1}}x_{σ_{2}} ⋯ x_{σ_{m}}, où σ est une permutation appartenant à 𝔖_{m}. On note R(w) la classe de tous les réarrangements du mot w.

On représente les sous-ensembles U ⊂ X × X comme suit : pour tout x, y ∈ X, on écrit x ≻ y si (x, y) ∈ U et x ⊁ y si (x, y) ∉ U. Un sous-ensemble U est appelé ordre bipartitionnaire, (^{∗∗}) si les deux conditions suivantes sont remplies :

z ≻ y et y ≻ x ⟹ z ≻ x;  (1)
z ≻ y et x ⊁ y ⟹ z ≻ x.  (2)

Pour une relation U ⊂ X × X quelconque, on généralise les statistiques classiques “inv” (nombre d’inversions) et “maj” (indice majeur) pour les mots quelconques de la façon suivante. Soit w = x_{1}x_{2} ⋯ x_{m} ∈ X^{∗} un mot, on définit :

inv_{U} w = Card{(i, j) | 1 ≤ i < j ≤ m, x_{i} ≻ x_{j}},
maj_{U} w = ∑{i | 1 ≤ i ≤ n − 1, x_{i} ≻ x_{i+1}}.

Lorsque X est totalement ordonné, l’ordre sous-jacent “>” vérifie bien les deux conditions (1) et (2), et est donc bipartitionnaire. Lorsque le sous-ensemble U est cet ordre, c’est-à-dire, x ≻ y si et seulement si x > y, on a alors inv_{U} = inv et maj_{U} = maj. De plus, on peut vérifier que les deux statistiques précédentes généralisent les statistiques inv_{k} et maj_{k} introduites dans [CF2]. Un autre exemple d’ordre bipartitionnaire se trouve dans

(^{∗}) Avec le concours du programme des Communautés Européennes en Combinatoire Algébrique, 1994-95.

(^{∗∗}) Cette définition est différente de celle qui a été donnée dans [FZ]. Le théorème 5 dans la dernière section montre que ces deux définitions sont équivalentes. la section 3. Le nombre des ordres bipartitionnaires B_{r} sur un alphabet de cardinal r est donné par la fonction génératrice suivante [FZ] :

\begin{aligned}∑_{r≥0} B_{r} \frac{u^{r}}{r!} & = \frac{1}{3 − 2e^{u}} \\ & = 1 + 2u + 10\frac{u^{2}}{2!} + 74\frac{u^{3}}{3!} + 730\frac{u^{4}}{4!} + 9002\frac{u^{5}}{5!} + ⋯ \end{aligned}

Foata et Zeilberger ont établi le résultat suivant [FZ] :

TH^{}ÉOR^{}ÈME 1 (FOATA et ZEILBERGER). — Les deux statistiques maj_{U} et inv_{U} sont équidistribuées, si et seulement si le sous-ensemble U est un ordre bipartitionnaire.

Depuis [H], on sait qu’il existe une autre définition “maj2_{U}” qui est équivalente à “maj” dans le cas classique. Cette statistique peut être aussi généralisée pour un sous-ensemble U ∈ X × X quelconque. La définition de “maj2_{U}” se trouve dans la section 2. Dans cette note, on démontre le théorème suivant :

TH^{}ÉOR^{}ÈME 2. — Les deux statistiques maj_{U} et maj2_{U} sont équivalentes, si et seulement si le sous-ensemble U est un ordre bipartitionnaire.

D’après les deux théorèmes précédents, on peut dire que les ordres bipartitionnaires sont des objets combinatoires “naturels”.

2. Intervalles cycliques. — Pour x, y ∈ X, l’intervalle cyclique (généralisé), noté ]]x, y]]_{U}, est défini par

]]x, y]]_{U} = \{ \begin{matrix}\{z ∈ X | z ≻ x et z ⊁ y\}, & si x ⊁ y; \\ \{z ∈ X | z ≻ x ou z ⊁ y\}, & si x ≻ y. \end{matrix}

Parfois, on a besoin d’ajouter l’élément “∞” dans notre alphabet pour former l’ensemble [r] ∪ {∞}, et on suppose alors x ⊁ ∞ et ∞ ≻ x pour tout x. Dans ce cas, on a z ∈ ]]x, ∞]]_{U} si et seulement si z ≻ x. Deux exemples d’ intervalle cyclique se trouvent dans la section 3.

Soient w = x_{1}x_{2} ⋯ x_{m} ∈ X^{∗} un mot et S ⊂ X, on note

⟨w , S⟩ = #{i | 1 ≤ i ≤ m, x_{i} ∈ S}.

Soient w = x_{1}x_{2} ⋯ x_{m}, u ∈ X^{∗} deux mots et S, T ∈ X deux sous-ensembles. On a les propriétés suivantes :

⟨w , ∅⟩ = 0 , ⟨w , X⟩ = m,
⟨wu , S⟩ = ⟨w , S⟩ + ⟨u , S⟩,
⟨w , S⟩ + ⟨w , T ⟩ = ⟨w , S ∪ T ⟩ + ⟨w , S ∩ T ⟩.

D^{}ÉFINITION. — Soient w = x_{1}x_{2} ⋯ x_{m} un mot. Avec la convention x_{n+1} = ∞, on définit :

maj2_{U} w = ∑_{j=1}^{m}⟨x_{1}x_{2} ⋯ x_{j−1} , ]]x_{j}, x_{j+1}]]_{U}⟩ .

La suite (s_{j})_{1≤j≤m} où s_{j} = ⟨x_{1}x_{2} ⋯ x_{j−1} , ]]x_{j}, x_{j+1}]]_{U}⟩ est appelée maj-codage du mot w.

3. Exemple. — Considérons l’alphabet X = {0, 1, 2, ⋯, 6}. On vérifie que l’ensemble

U = \{ \begin{matrix}0 ≻ 0, & 0 ≻ 1, \\ 1 ≻ 0, & 1 ≻ 1, \\ 2 ≻ 0, & 2 ≻ 1, & 2 ≻ 2, \\ 3 ≻ 0, & 3 ≻ 1, & 3 ≻ 2, \\ 4 ≻ 0, & 4 ≻ 1, & 4 ≻ 2, \\ 5 ≻ 0, & 5 ≻ 1, & 5 ≻ 2, \\ 6 ≻ 0, & 6 ≻ 1, & 6 ≻ 2, & 6 ≻ 3, & 6 ≻ 4, & 6 ≻ 5 \end{matrix} \}

est bien un ordre bipartitionnaire. On a par exemple les intevalles cycliques ]]6, 2]]_{U} = {0, 1} et ]]2, 3]]_{U} = ]]2, 4]]_{U} = ]]2, 5]]_{U} = {2, 3, 4, 5}. Pour le mot w = 315016406254320, on a maj_{U} w = 1+3+4+6+7+9+13+14 = 57 et maj2_{U} w = 1+3+4+5+1+6+5+3+6+9+14 = 57. Les calculs complets sont consignés dans le tableau suivant :

i  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x_{i}  3 1 5 0 1 6 4 0 6 2 5 4 3 2 0
descente − − − − − − − −
s_{i}  0 1 0 3 4 5 1 7 4 3 0 0 6 9 14

4. Propriétés des intervalles cycliques. — Soit U ∈ X × X un sous-ensemble. Pour abréger les écritures, notons A = ]]y, ∞]]_{U}, B = ]]x, y]]_{U}, C = ]]x, ∞]]_{U} pour deux lettres x, y ∈ X. On a le résultat suivant :

LEMME 3. — Le sous-ensemble U est un ordre bipartitionnaire, si et seulement si, pour tout x, y ∈ X, les relations entre A, B et C suivants sont remplies :

(i) si x ⊁ y, alors A ∩ B = ∅, A ∪ B = C; (ii) si x ≻ y, alors A ∩ B = C, A ∪ B = X.

Démonstration. — La partie “si”. — D’après la condition (i), pour tout x, y, si x ⊁ y et z ∈ A, alors z ∈ C. Ceci démontre la relation (1) de la section 1. D’après la condition (ii), pour tout x, y, si x ≻ y et z ∈ C, alors z ∈ A. Ceci démontre la relation (2) de la section 1.

La partie “seulement si”. — Dans le premier cas, i.e., x ⊁ y, on vérifie :

• Si z ∈ C, alors z ≻ x. Dans ce cas, on a ou bien z ≻ y, z ∈ A et z ∉ B; ou bien z ⊁ y, z ∈ B et z ∉ A; • Si z ∈ A, alors z ≻ y. D’après la relation (1), on a z ≻ x, z ∈ C;

• Si z ∈ B, alors z ≻ x et z ⊁ y. On a z ∈ C. Dans le second cas, i.e., x ≻ y, on vérifie :

• Si z ∈ C, alors z ≻ x, z ∈ B. D’autre part, d’après (2), on a z ≻ y et z ∈ A.

• Si z ∉ C, i.e., z ⊁ x. Dans ce cas, si z ≻ y, alors z ∈ A et z ∉ B; si z ⊁ y, alors z ∉ A et z ∈ B.

5. Démonstration du théorème 2. — Posons w′ = x_{1}x_{2} ⋯ x_{m−1}. On note (s_{j})_{1≤j<m} et (s′_{j})_{1≤j<m−1} les maj-codages de w et de w′ respectivement, il est clair qu’on a s_{j} = s′_{j} pour tout j < m − 1. Pour abréger les écritures, notons A = ]]x_{m}, ∞]]_{U}, B = ]]x_{m−1}, x_{m}]]_{U}, C = ]]x_{m−1}, ∞]]_{U} et u = x_{1}x_{2} ⋯ x_{m−2}. On calcule maintenant

\begin{matrix}Δ = & s_{m} + s_{m−1} − s′_{m−1} \\ = & ⟨ux_{m−1} , A⟩ + ⟨u , B⟩ − ⟨u , C⟩ \\ = & ⟨x_{m−1} , A⟩ + ⟨u , A ∪ B⟩ + ⟨u , A ∩ B⟩ − ⟨u , C⟩. \end{matrix}

La partie “si”. — Si x_{m−1} ⊁ x_{m}, alors x_{m−1} ∉ A. D’après les propriétés précédentes, on a

Δ = 0 + ⟨u , C⟩ + ⟨u , ∅⟩ − ⟨u , C⟩ = 0.

D’autre part, si x_{m−1} ≻ x_{m}, alors x_{m−1} ∈ A, on a

Δ = 1 + ⟨u , X⟩ + ⟨u , C⟩ − ⟨u , C⟩ = m − 1.

D’où maj_{U} w = maj2_{U} w par récurrence sur la longueur m du mot w.

La partie “seulement si”. — Puisque maj_{U} w = maj2_{U} w pour tout w, on a Δ = 0 si x_{m−1} ⊁ x_{m} et Δ = m − 1 si x_{m−1} ≻ x_{m}. Dans le premier cas, on a Δ = 0+⟨u , A∪B⟩+⟨u , A∩B⟩−⟨u , C⟩ = 0 pour tout u de longueur m−2, et forcément A∩B = ∅ et A∪B = C; et dans le second cas, on a Δ = 1+⟨u , A∪B⟩+⟨u , A∩B⟩−⟨u , C⟩ = m−1 pour tout u de longueur m − 2, et forcément A ∩ B = C et A ∪ B = X. D’après le lemme précédent, le sous-ensemble U est donc un ordre bipartitionnaire.

6. Structures des ordres bipartitionnaires. — D’après la définition de l’ordre bipartitionnaire, on a immédiatement les propriétés suivantes :

x ⊁ y et z ≻ y ⟹ x ⊁ z;  (3)
x ⊁ y et y ⊁ z ⟹ x ⊁ z;  (4)
x ≻ y et y ≻ x ⟹ x ≻ x et y ≻ y;  (5)
x ⊁ y et y ⊁ x ⟹ x ⊁ x et y ⊁ y.  (6)

Soit U ⊂ X × X un sous-ensemble quelconque. Pour tout x, y ∈ X, on dit que la lettre x est incomparable à y, si x ≻ y et y ≻ x ou bien si x ⊁ y et y ⊁ x. On note x ≈ y si x est incomparable à y, et la relation “≈” est appelée relation d’incomparabilité définie par U.

LEMME 4. — Si U ⊂ X × X est un ordre bipartitionnaire, alors la relation d’incomparabilité “≈” définie par U est une relation d’équivalence.

Démonstration. — La reflexivité et la symétrie sont évidentes d’après la définition. Pour la transitivité, on suppose x ≈ y et y ≈ z. D’abord, si x ≻ y et y ≻ x, on a y ≻ y d’après (5). On a alors y ≻ z et z ≻ y. Ainsi, par la relation (1), on a x ≈ z. Dans le second cas, si x ⊁ y et y ⊁ x, c’est la même vérification.

D^{}ÉFINITION. — Une bipartition ordonnée de X est une suite ordonnée (B_{1}, B_{2}, ⋯, B_{k}) de blocs non vides, disjoints deux à deux, de reunion X, dont certains peuvent être soulignés.

TH^{}ÉOR^{}ÈME 5. — Une relation U est bipartitionnaire, si et seulement s’il existe une bipartition ordonnée B = (B_{1}, B_{2}, ⋯, B_{k}) de X, tel que

y ≻ x ⟺ x ∈ B_{l}, y ∈ B_{h}, avec l < h; ou bien x, y ∈ B_{l}, avec B_{l} souligné.  (7)

Démonstration. — La partie “si” est triviale : il est suffit de vérifier les deux relations (1) et (2) de la section 1. Pour la partie “seulement si”, d’après le lemme précédent, l’ensemble quotient X/≈ de X par rapport à la relation d’incomparabilité “≈” existe. Il est clair qu’avec l’ordre induit par la relation U, cet ensemble X/≈ est totalement ordonné. Soient B_{1}, B_{2}, ⋯, B_{k} les éléments de X/≈ suivant cet ordre total. On peut vérifier la relation (7) avec la suite de B_{1}, B_{2}, ⋯, B_{k} ainsi définie.

Exemple. — Pour la relation U donnée dans la section 3, la bipartition associée est B = (\{\underline{0}, \underline{1}\}, \{\underline{2}\}, \{3, 4, 5\}, \{6\}).

BIBLIOGRAPHIE

[CF1] R. J. CLARKE et D. FOATA. — Eulerian Calculus, I : Univariable Statistics, Europ. J. Combinatorics, t. 15, 1994, p. 345-362.

[CF2] R. J. CLARKE et D. FOATA. — Eulerian calculus, II : An extension of Han’s fundamental transformation, à paraître dans Europ. J. Combinatorics.

[FZ] D. FOATA et D. ZEILBERGER. — Graphical Major Indices, soumis pour publication, 1995.

[K] K. W. J. KADELL. — Weighted inversion numbers, restricted growth function, and standard Young tableaux, J. Comb. Theory, Ser. A, t. 40, 1985, p. 22-44.

[H] G.-N. HAN. — Une transformation fondamentale sur les réarrangements de mots, Advances in Math., t. 105, 1994, p. 26-41.

I.R.M.A., Université Louis Pasteur & C.N.R.S.

7, rue René Descartes, 67084 Strasbourg Cedex, France

email : guoniu@math.u-strasbg.fr