ÉTUDE MODULO n DES STATISTIQUES MAHONIENNES

Jacques Désarménien

Introduction

Sous le nom générique de statistiques mahoniennes, on regroupe un certain nombre de statistiques d’ordre définies sur des ensembles de mots de longueur n. Citons, entre autres, le nombre d’inversions des permutations, leur indice majeur ou majeur-inverse, les mêmes statistiques sur les mots écrits avec les lettres {0, 1}. On peut, par ailleurs, imposer des contraintes sur la forme (“up-down sequence”) des permutations. Un résultat célèbre de Foata et Schützenberger [F–S] établit dans ce cas l’équidistribution du nombre d’inversions et de l’indice majeur-inverse. On peut alors se ramener à l’étude de l’indice majeur d’un tableau de Young, ce qui permet d’utiliser tout l’arsenal de l’algèbre classique. Une telle approche a été utilisée notamment dans [D2, D–F1, D–F2, D–F3, D–F4].

Le but de cet article est d’établir une propriété d’équirépartition des tableaux de Young de forme donnée relativement à la valeur modulo n de leur indice majeur. On en déduit ensuite la même propriété pour toutes les statistiques des permutations, ainsi que de nombreux résultats analogues.

On obtient aussi la décomposition explicite de la représentation du groupe symétrique sur l’algèbre de Lie libre associée à la partition n. Ce résultat, dû à Kraskiewicz et Weyman [K–W], est cité par Reutenauer [R].

Les outils mis en œuvre sont, d’une part le lien entre certains caractères du groupe symétrique et l’indice majeur des tableaux de Young, d’autre part un lemme de nature arithmétique.

Avec le soutien du P.R.C. Math.-Info.

J. DÉSARMÉNIEN

1. Lemme arithmétique

Soit n un entier strictement positif. Notons Φ_{n}(q) le n-ième polynôme cyclotomique (Φ_{1}(q) = 1 − q, Φ_{2}(q) = 1 + q,…). Nous aurons besoin des sommes de Ramanujan c_{n}(m) = ∑_{(i,n)=1} ζ^{im}, où ζ désigne une racine primitive n-ième de l’unité (cf. [H–W]). On peut assez facilement trouver la valeur explicite des sommes de Ramanujan en termes de fonction de Möbius μ(n) et de fonction indicatrice d’Euler φ(n). Plus précisément, on a le résultat suivant, dû à Hölder.

Lemme 1.1 [H–W, p. 238]. — Posons (m, n) = δ et n = δN ; alors

c_{n}(m) = \frac{μ(N)φ(n)}{φ(N)}.

En particulier, si (n_{1}, m) = (n_{2}, m), alors c_{n}(m_{1}) = c_{n}(m_{2}).

Soit maintenant un polynôme P (q) = ∑_{0≤k≤n−1} a_{k}q^{k} à coefficients entiers. Suivant en cela la terminologie de Cohen [C], nous dirons que les coefficients de P (q), et par abus, P (q) lui-même, sont pairs modulo n lorsque, pour tous k et l compris entre 0 et n − 1, l’égalité (k, n) = (l, n) implique l’égalité des coefficients a_{k} = a_{l}.

Les fonctions paires modulo n ont été étudiées par Cohen, qui a montré qu’elles coïncident avec les combinaisons linéaires de sommes de Ramanujan. Ces dernières avaient été utilisées en particulier par Nicol et Vandiver [N–V] pour dénombrer certaines configurations combinatoires.

Proposition 1.2. — Soit P (q) un polynôme à coefficients entiers de degré inférieur à n. Il y a équivalence entre les deux propriétés suivantes :

(i) Pour tout entier d diviseur de n, le résidu r_{d} de P (q) modulo Φ_{d}(q) est un entier ; (ii) Le polynôme P (q) est pair modulo n. On a, de plus,

a_{k} = \frac{1}{n} ∑_{d|n} r_{d}c_{d}(k)  et  r_{δ} = ∑_{d|n} a_{n/d}c_{d}(n/δ).

Démonstration de la proposition 1.2. — Les polynômes satisfaisant (i) et ceux satisfaisant (ii) forment clairement des ℤ-modules de même dimension, égale au nombre de diviseurs de n. Pour démontrer l’équivalence de ces propriétés, il suffit donc de montrer que l’une implique l’autre.

ÉTUDE MODULO n

Supposons la propriété (ii) satisfaite ; en d’autres termes, si (k, n) = n/d, alors a_{k} = a_{n/d}. Pour montrer la propriété (i), il suffit de voir que lorsque q est égal à une racine primitive δ-ième de l’unité quelconque, δ|n, la valeur prise par P (q) est bien un nombre r_{δ} ne dépendant que de δ. Les racines primitives δ-ièmes sont les ζ^{i}, (i, n) = n/δ, pour lesquelles on a :

\begin{aligned}P (ζ^{i}) & = ∑_{0≤k≤n−1} a_{k}ζ^{ik}, \\ & = ∑_{d|n} a_{n/d} ∑_{(k,n)=n/d} ζ^{ik}. \end{aligned}

On peut écrire k = k′ \frac{n}{d} où (k′, d) = 1 ; de plus, si ζ est une racine primitive n-ième, alors ζ^{n/d} est une racine primitive d-ième. On a donc :

P (ζ^{i}) = ∑_{d|n} a_{n/d} ∑_{(k′,d)=1} ζ^{ik′n/d},

= ∑_{d|n} a_{n/d}c_{d}(i),

= ∑_{d|n} a_{n/d}c_{d}(n/δ).

On obtient bien la propriété (i) et la valeur annoncée de r_{δ}.

Réciproquement, (i) implique (ii). Pour vérifier que les a_{k} s’expriment en fonction des r_{d} comme indiqué, on peut utiliser une formule d’inversion de Cohen [C, théorème 2]. Pour rester autonome, nous allons en fait établir directement cette formule d’inversion dans notre cas particulier.

Supposons satisfaite la propriété (i). Soient ζ^{0}, ζ^{1}, …, ζ^{n−1} les n racines n-ièmes de l’unité. Les racines primitives d-ièmes sont donc les ζ^{k}, (k, n) = n/d. Puisque P (q) ≡ r_{d} (mod Φ_{d}(q)), on a, pour tout k tel que (k, n) = n/d, l’égalité P (ζ^{k}) = r_{d}. Puisque nous connaissons la valeur de P (q) en n points distincts, nous pouvons appliquer la formule d’interpolation de Lagrange :

P (q) = ∑_{0≤i≤n−1} P (ζ^{i}) ∏_{j≠i} \frac{(q − ζ^{j})}{(ζ^{i} − ζ^{j})},

= ∑_{0≤i≤n−1} P (ζ^{i}) ∏_{j≠i} \frac{(ζ^{n−i}q − ζ^{n−i+j})}{(1 − ζ^{n−i+j})},

= ∑_{0≤i≤n−1} P (ζ^{i}) ∏_{j≠0} \frac{(ζ^{n−i}q − ζ^{j})}{(1 − ζ^{j})}.

Le polynôme dont les racines sont les ζ^{j}, j ≠ 0 étant ∑_{0≤k≤n−1} q^{k}, on a donc :

P (q) = \frac{1}{n} ∑_{0≤i≤n−1} P (ζ^{i}) ∑_{0≤k≤n−1} ζ^{(n−i)k}q^{k},

qui, en regroupant les indices i selon la valeur n/d de (i, n) et en remplaçant P (ζ^{i}) par r_{d}, permet d’écrire

P (q) = \frac{1}{n} ∑_{d|n} r_{d} ∑_{(i,n)=n/d} ∑_{0≤k≤n−1} ζ^{(n−i)k}q^{k},

= \frac{1}{n} ∑_{0≤k≤n−1} q^{k} ∑_{d|n} r_{d} ∑_{(i,n)=n/d} ζ^{ik},

= \frac{1}{n} ∑_{0≤k≤n−1} q^{k} ∑_{d|n} r_{d}c_{d}(k).

On obtient bien la valeur annoncée pour le coefficient a_{k}.

Ceci achève la démonstration de la proposition 1.2.

2. Caractères et congruences

Pour tout ce qui concerne les définitions et propriétés générales des fonctions symétriques, le lecteur est renvoyé à [M]. On sait que les fonctions sommes de puissances p_{λ}, où λ est une partition, forment une ℚ-base de l’espace vectoriel des fonctions symétriques. Par ailleurs, à toute représentation du groupe symétrique est associée une fonction symétrique. C’est ainsi que les fonctions de Schur S_{λ} sont associées aux représentations irréductibles lorsque λ est une partition (ou une forme principale). Les fonctions de Schur constituent une ℤ-base de l’espace vectoriel des fonctions symétriques. Plus précisément, si on note χ_{λ}(μ) la valeur en μ du caractère irréductible du groupe symétrique associé à λ, on a les décompositions :

S_{λ} = ∑_{μ} \frac{1}{z_{μ}} χ_{λ}(μ)p_{μ},

p_{μ} = ∑_{λ} χ_{λ}(μ)S_{λ},

où z_{μ} est l’entier égal à 1^{μ_{1}}2^{μ_{2}} … μ_{1}! μ_{2}! … lorsque μ est la partition constituée de μ_{1} parts égales à 1, de μ_{2} parts égales à 2, …

Étant donné un tableau de Young standard T de forme λ et d’ordre n, notons rec T l’ensemble des entiers i, 1 ≤ i ≤ n − 1 tels que i + 1 se trouve à gauche (au sens large) de i dans T (reculs de T), et imaj T la somme des entiers i ∈ rec T (indice majeur-inverse de T). En particulier, si la forme λ est un ruban (cf. [D2]), le tableau T peut être considéré comme une permutation dont la forme est donnée par λ, et la statistique ainsi définie sur T coïncide avec l’indice majeur-inverse. Notons (q, q)_{n} = (1 − q)(1 − q^{2}) ⋯ (1 − q^{n}) la q-factorielle.

Le rapport entre fonctions de Schur et statistiques mahoniennes est, en substance, contenu dans le lemme ci-dessous (cf. [D–F1]).

Lemme 2.1. — La fonction génératrice de la statistique imaj sur les tableaux standard de forme λ est donnée par :

∑_{T} q^{imaj T} = (q, q)_{n}S_{λ}(1, q, q^{2}, …),

où la somme est étendue à tous les tableaux standard de forme λ.

Soit P_{λ}(q) = ∑_{0≤k≤n−1} a_{k}(λ)q^{λ} le polynôme dont le coefficient a_{k}(λ) est le nombre de tableaux T de forme λ tels que imaj T ≡ k (mod n). Nous pouvons maintenant énoncer le résultat principal de cet article.

Théorème 2.2. — Pour une forme λ donnée d’ordre n, la valeur de a_{k}(λ) ne dépend que du plus grand commun diviseur (k, n). Plus précisément,

a_{k}(λ) = \frac{1}{n} ∑_{d|n} χ_{λ}(d^{n/d})c_{d}(k).

Démonstration du théorème 2.2. — Soit d|n; puisque 1−q^{n} est divisible par Φ_{d}(q), le reste modulo Φ_{d}(q) de P_{λ}(q) et celui de la série génératrice de imaj sur les tableaux de forme λ sont égaux. En vertu du lemme 2.1, il est égal au reste de (q, q)_{n}S_{λ}(1, q, q^{2}, …) modulo Φ_{d}(q).

On peut alors utiliser l’écriture de S_{λ} comme combinaison linéaire de sommes de puissances. On obtient :

(q, q)_{n}S_{λ}(1, q, q^{2}, …) = ∑_{μ} \frac{1}{z_{μ}} χ_{μ}(λ)T_{μ}(q),

où

T_{μ}(q) = (q, q)_{n}p_{μ}(1, q, q^{2}, …).

On voit facilement que

T_{μ}(q) = \frac{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})}{(1 − q)^{μ_{1}}(1 − q^{2})^{μ_{2}} ⋯ (1 − q^{n})^{μ_{n}}} .

Les seuls facteurs de l’expression précédente sont des polynômes cyclotomiques. On trouve sans grande difficulté le reste modulo un polynôme cyclotomique quelconque (cf. [D1, D2, D–F4]). Ici, seul nous intéresse le reste modulo Φ_{d}(q), pour lequel nous allons redonner le résultat. La multiplicité de Φ_{d}(q) dans T_{μ}(q) vaut

\frac{n}{d} − (μ_{d} + μ_{2d} + ⋯ + μ_{n}).

Puisque

n = μ_{1} + 2μ_{2} + ⋯ + nμ_{n} ≥ d(μ_{d} + μ_{2d} + ⋯ + μ_{n}),

il s’ensuit que T_{μ}(q) est divisible par Φ_{d}(q), sauf si μ = d^{n/d}. Dans ce dernier cas,

T_{d^{n/d}}(q) = \frac{(1 − q) ⋯ (1 − q^{d})(1 − q^{d+1}) ⋯ (1 − q^{2d}) ⋯ (1 − q^{n})}{(1 − q^{d})^{n/d}},

et la substitution à q d’une quelconque racine primitive d-ième de l’unité dans l’expression précédente donne

T_{d^{n/d}}(q) ≡ d^{n/d}(n/d)! = z_{d^{n/d}} (mod Φ_{d}(q)).

Par conséquent, on a la congruence :

(q, q)_{n}S_{λ}(1, q, q^{2}, …) ≡ χ_{λ}(d^{n/d}) (mod Φ_{d}(q)).

La condition (i) de la proposition 1.2 est ainsi satisfaite pour le polynôme P_{λ}(q) et le théorème 2.2 est démontré.

3. Conséquences combinatoires

Le théorème 2.2 s’applique à toutes les formes λ, y compris les rubans, comme mentionné plus haut. Les tableaux de Young de forme ruban sont exactement les permutations dont la forme est donnée par le ruban. Par combinaison linéaire des fonctions de Schur de formes ruban, on obtient les permutations dont la forme est sujette à des conditions. C’est précisément sur ces ensembles de permutations que Foata et Schützenberger [F–S] ont montré l’équidistribution du nombre d’inversions et de l’indice majeurinverse. On déduit donc du théorème 2.2 le résultat suivant.

Proposition 3.1. — Le nombre de permutations de [1, n] sujettes à des conditions sur leur forme et dont le nombre d’inversions est congru à k modulo n ne dépend que du plus grand commun diviseur (k, n).

On peut en déduire des résultats analogues pour toutes les suites analogues aux suites classiques de nombres étudiées dans [D2] : permutations alternantes, permutations eulériennes, dérangements, …

Nous avons étudié, à la suite de Gessel [D–W], les fonctions symétriques associées aux mots de Lyndon d’un type donné. On en déduit, de manière tout-à-fait analogue au lemme 3.2, l’existence de fonctions symétriques L_{λ} de degré n telles que la fonction génératrice de la statistique imaj étendue aux permutations dont la structure cyclique est de type λ est égale à (q, q)_{n}L_{λ}(1, q, q^{2}, …). En décomposant les fonctions L_{λ} en sommes de fonctions de Schur, et en appliquant le théorème 2.2 à chacune des fonctions de Schur, on obtient le résultat suivant.

Proposition 3.2. — Le nombre de permutations de [1, n] dont la structure cyclique est de type λ et dont l’indice majeur-inverse est congru à k modulo n ne dépend que du plus grand commun diviseur de k et de n.

Un cas particulier digne d’intérêt est celui où le type est réduit à une seule part n. Les permutations sous-jacentes sont donc les permutations cycliques. Dans ce cas, la fonction L_{n}, somme des poids des mots de Lyndon de longueur n, peut être évaluée par le théorème de Pólya :

L_{n} = \frac{1}{n} ∑_{d|n} μ(d)p_{d}^{n/d}.

Écrivons maintenant la décomposition des sommes de puissances comme sommes de fonctions de Schur :

L_{n} = \frac{1}{n} ∑_{d|n} ∑_{λ} μ(d)χ_{λ}(d^{n/d})S_{λ},

= ∑_{λ}(\frac{1}{n} ∑_{d|n} μ(d)χ_{λ}(d^{n/d}))S_{λ},

= ∑_{λ} a_{1}(λ)S_{λ}.

La dernière expression de L_{n} résulte du théorème 2.2 et de la remarque du lemme 1.1 que c_{d}(1) = μ(d). On en déduit la décomposition suivante, obtenue par d’autres moyens par Kraskiewicz et Weyman [K–W].

Proposition 3.3. — La multiplicité de S_{λ} dans L_{n} est égale au nombre de tableaux de Young de forme λ dont l’indice majeur-inverse est congru à 1 modulo n.

Ce résultat, comme l’indique Reutenauer [R], a d’autres conséquences. En effet, partons de l’identité de la proposition précédente :

L_{n} = ∑_{λ} a_{1}(λ)S_{λ}.

Utilisant les techniques et les notations de [D–W], on peut écrire

L_{n} = ∑_{λ} a_{1}(λ) ∑_{T} ∑_{s⊥rec T} w(s),

où la seconde somme est étendue aux tableaux standard T de forme λ. On peut récrire

L_{n} = ∑_{E⊂[1,n−1]} ∑_{s⊥E} w(s)A^{E},

où A^{E} est le nombre de couples de tableaux standard (U, V) d’ordre n, de même forme, où imaj U ≡ 1 (mod n) et rec T = E.

La construction de Robinson-Schensted-Schützenberger établit précisément une bijection entre les couples (U, V) de tableaux de Young de même forme et les permutations σ. De plus, l’ensemble des reculs de U est égal à l’ensemble des reculs de σ et l’ensemble des reculs de V à celui des descentes de σ. Par conséquent, A^{E} est aussi le nombre de permutations de σ de [1, n] dont l’ensemble des descentes est E et telles que imaj σ est congru à 1 modulo n.

D’un autre côté,

L_{n} = ∑_{E⊂[1,n−1]} ∑_{s⊥E} w(s)C^{E},

où C^{E} est le nombre de permutations circulaires de [1, n] dont l’ensemble des descentes est E (cf. [D–W]). Il s’ensuit, par identification (en fait en résolvant un système triangulaire) l’égalité A^{E} = C^{E}. Utilisant encore le résultat de Foata et Schützenberger, on a établi la proposition suivante, due à Reutenauer [R].

Proposition 3.4. — Soit E ⊂ [1, n − 1]. Les ensembles suivants ont même cardinal :

(i) Les permutations circulaires dont l’ensemble des descentes est E; (ii) Les permutations dont l’ensemble des descentes est E et dont l’indice majeur-inverse est congru à 1 modulo n; (iii) Les permutations dont l’ensemble des descentes est E et dont le nombre d’inversions est congru à 1 modulo n.

Dans un autre ordre d’idées, mentionnons pour finir que la proposition 1.2 s’applique aussi aux polynômes gaussiens, ou q-binomiaux. Nous avons établi, dans [D1] la congruence suivante : si n = ka+r et m = kb+s sont les divisions respectives des entiers n et m par k, alors,

\left[{n \atop m}\right] ≡ \binom{a}{b}\left[{r \atop s}\right] (mod Φ_{k}).

Lorsque k divise n, le polynôme \left[{r \atop s}\right] vaut 0 ou 1 selon que k ne divise pas ou divise m. Dans tous les cas, le second membre de la congruence est un entier. Compte tenu des interprétations combinatoires des polynômes gaussiens, dues à MacMahon, on a pour les statistiques mahoniennes sur les mots un résultat analogue au théorème 2.2.

Proposition 3.5. — Le nombre de mots contenant m fois la lettre 0 et n−m fois la lettre 1 dont le nombre d’inversions (ou, de façon équivalente, l’indice majeur) est congru à k modulo n ne dépend que du plus grand commun diviseur (k, n).

RÉFÉRENCES BIBLIOGRAPHIQUES

[C] COHEN (E.). — A class of arithmetical functions, Proc. Nat. Acad. Sci. U.S.A., t. 41, 1955, p. 939–944.

[D1] D^{}ÉSARM^{}ÉNIEN (J.). — Un analogue des congruences de Kummer pour les qnombres d’Euler, Europ. J. Combin., t. 3, 1982, p. 19–28.

[D2] D^{}ÉSARM^{}ÉNIEN (J.). — Fonctions symétriques associées à des suites classiques de

nombres, Ann. Scient. École Normale Supérieure, t. 16, 1983, p. 271–304.

[D–F1] D^{}ÉSARM^{}ÉNIEN (J.) et FOATA (D.). — Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, t. 113, 1985, p. 3–22.

[D–F2] D^{}ÉSARM^{}ÉNIEN (J.) et FOATA (D.). — Fonctions symétriques et séries hypergéométriques basiques multivariées II, Combinatoire énumérative, [Labelle (G.) et Leroux (P.), éd. ; Montréal, 28 mai–1 juin 1985], p. 68–90. — Heidelberg, Springer-Verlag (Lecture Notes in Mathematics, vol. 1234), 1987.

[D–F3] D^{}ÉSARM^{}ÉNIEN (J.) et FOATA (D.). — Statistiques d’ordre sur les permutations

colorées, Discrete Math. (à paraître).

[D–F4] D^{}ÉSARM^{}ÉNIEN (J.) et FOATA (D.). — The signed Eulerian numbers, Discrete

Math. (à paraître).

[D–W] D^{}ÉSARM^{}ÉNIEN (J.) et WACHS (M.). — Descentes sur les dérangements et mots circulaires, Séminaire lotharingien de combinatoire, 19^{e} session, [Strehl (V.), éd. ; Schloß Schwannberg/Ufr. 22–25 mars 1988], p.13–21. — Strasbourg, Publ. I.R.M.A. 361/S–19, 1988.

[F–S] FOATA (D.) et SCH^{}ÜTZENBERGER (M.). — Major index and inversion number

of permutations, Math. Nachr., t. 83, 1978, p. 143–159.

[H–W] HARDY (G.M.) et WRIGHT (E.M.). — An introduction to the theory of numbers

(5^{e} éd.). — Oxford, Clarendon Press, 1979.

[K–W] KRASKIEWICZ (W.) et WEYMAN (J.). — Algebra of invariants and the action of a Coxeter element, prépublication, Institut de mathématique de l’Université Copernic, Toruń, Pologne.

[M] MACDONALD (I.G.). — Symmetric functions and Hall polynomials. — Oxford,

Clarendon Press, 1979. [N–V] NICOL (C.A.) et VANDIVER (H.S.). — A Von Sterneck arithmetical function and

restricted partitions with respect to a modulus, Proc. Nat. Acad. Sci. U.S.A., t. 40, 1954, p. 825–835.

[R] REUTENAUER (C.). — Number of permutations with given descent set and cycle stucture, à paraître dans les actes de la 21^{e} session du Séminaire lotharingien de combinatoire.

Institut Gaspard-Monge, Université Marne-la-Vallée,

93160-Noisy-le-Grand.