LES DISTRIBUTIONS EULER-MAHONIENNES SUR LES MOTS

Dominique FOATA

R^{}ÉSUM^{}É. — L’objet de cet article est de calculer la distribution euler-mahonienne sur toute classe de réarrangements R(c) d’un même mot. Après avoir réactualisé le calcul de MacMahon de cette distribution, on montre que l’algèbre des fonctions de Schur fournit tous les ingrédients utiles pour obtenir cette distribution. Cette dernière approche permet, en outre, une extension au calcul des distributions sur les bi-mots colorés, ainsi que d’autres extensions hypergéométriques multibasiques qui n’ont pas été reproduites ici.

ABSTRACT. — The purpose of this paper is to calculate the euler-mahonian distribution over each rearragement class R(c) of a given word. After updating MacMahon’s calculation of this distribution, it is shown that the Schur function algebra gives all the necessary ingredients for deriving this distribution. Furthermore, this approach provides an extension to the calculation of some distributions over the colored biwords, as well as other multibasic hypergeometric extensions that have not been reproduced here.

1. Introduction. — Le présent article a été motivé par les récents travaux de Denert [Den90], qui, devant calculer la fonction zêta d’un R-ordre héréditaire dans des algèbres centrales simples, a été amenée à introduire une nouvelle statistique sur les mots, plus tard appelée “den.” Par “mot,” on entend une suite finie w = x_{1}x_{2} … x_{m}, où les lettres x_{1}, x_{2}, …, x_{m} sont des entiers positifs, de sorte que l’on peut parler de réarrangement croissant w′ = x′_{1}x′_{2} … x′_{m} de ce mot. Si w contient c_{1} fois la lettre 1, c_{2} fois la lettre 2, …, c_{r} fois la lettre r, on a donc w′ = 1^{c_{1}}2^{c_{2}} … r^{c_{r}}.

La définition de “den” (revue par Han [Han91]) est mieux comprise, si on introduit, pour deux entiers x et y, l’intervalle cyclique

]]x, y]] = \{ \begin{matrix}]x, y], & si x ≤ y; \\ [1, y] + ]x, +∞[, & si x > y. \end{matrix}

Conservant les mêmes notations que ci-dessus, la statistique den w attachée au mot w est obtenue en calculant d’abord pour chaque entier k = 1, 2, …, m la quantité den_{k} w ci-dessous définie, puis en prenant la somme de ces den_{k} w :

den_{k} w = # {i ≤ k − 1 : x_{i} ∈]]x_{k}, x′_{k}]]}  (1 ≤ k ≤ m) ;
den w = ∑_{1≤k≤m} den_{k} w.

Dans l’exemple suivant, on a représenté le réarrangement croissant en première ligne et le mot lui-même w en seconde ligne d’une même matrice.

D. FOATA

Le calcul des den_{k} w apparaît sur la troisième ligne, d’où l’on tire den w :

\binom{w′}{w} = ( \begin{matrix}1 & 1 & 1 & 2 & 2 & 2 & 3 & 4 & 5 & 5 & 6 & 6 & 6 & 7 \\ 3 & 1 & 2 & 1 & 2 & 4 & 6 & 2 & 6 & 5 & 6 & 1 & 7 & 5 \end{matrix} )
den_{k} w = 0 0 2 1 0 4 5 2 7 0 0 9 12 4

et donc den w = 46.

Il existe une autre définition pour “den w” faisant intervenir le nombre d’inversions des sous-mots de w composés des lettres qui sont respectivement en excédance et en sous-excédance. L’équivalence de ces deux définitions est démontrée dans [FoZe90] et [Cla91] pour les mots sans répétitions (“permutations”) et dans [Han91] pour les mots arbitraires.

Les autres statistiques dont il va être question dans cet article sont plus classiques et sont définies, pour chaque mot w = x_{1}x_{2} … x_{m}, par :

des w = #{i | x_{i} > x_{i+1}}; exc w = #{i | x_{i} > x′_{i}};
maj w = ∑{i | x_{i} > x_{i+1}}; inv w = #{i < j | x_{i} > x_{j}}.

Traditionnellement, “des,” “exc,” “maj” et “inv” sont appelées nombre de descentes, nombre d’excédances, indice majeur, nombre d’inversions.

Soient c = (c_{1}, …, c_{r}) une suite d’entiers positifs et R(c) la classe formée de tous les mots qui sont des réarrangements du mot croissant 1^{c_{1}}2^{c_{2}} … r^{c_{r}}. L’un des problèmes posés par Denert [Den90] était de calculer le polynôme générateur de R(c) par le couple de statistiques (exc, den), c’est-à-dire le polynôme

(1.1)  ∑_{w} t^{exc w}q^{den w}  (w ∈ R(c)).

Comme le couple (exc, den) se prête mal au calcul, il était raisonnable de rechercher dans le corpus des statistiques sur les mots celles qu’on pouvait faire entrer en correspondance avec ledit couple et dont la distribution se calculait bien.

Pour simplifier, nous dirons qu’une statistique définie sur R(c) est eulérienne, si elle a même distribution que “des” sur R(c), qu’elle est mahonienne, si elle a même distribution que l’indice majeur “maj” sur R(c) ; enfin, un couple de statistiques défini sur R(c) est dit eulermahonien, s’il a même distribution que le couple (des, maj) sur R(c).

DISTRIBUTIONS EULER-MAHONIENNES

A ce niveau, se posent deux types de préoccupations : d’une part, faire l’inventaire des statistiques usuelles qui sont eulériennes, mahoniennes ou euler-mahoniennes, d’autre part, faire le calcul analytique de ces distributions. On sait, depuis MacMahon [MacM16], que “exc” est eulérienne et que “inv” est mahonienne sur toute classe R(c), ce qui a soulevé le problème de construire des transformations bijectives Φ_{1} et Φ_{2} de R(c) sur elle-même satisfaisant les identités

exc w = des Φ_{1}(w), inv w = maj Φ_{2}(w).

De telles bijections ont été effectivement construites (cf. Cartier-Foata [Ca-Fo69] pour Φ_{1} et Foata [Fo68] pour Φ_{2}). Il restait encore à imaginer la définition d’une statistique mahonienne, disons “den,” telle que le couple (exc, den) soit euler-mahonien. On doit à Denert [Den90] d’avoir dégagé la définition d’une telle statistique. En d’autres termes, on a le théorème suivant.

Théorème 1.1. — Le couple (exc, den) est euler-mahonien sur toute classe R(c). Il a donc même distribution que (des, maj).

Lorsque R(c) = 𝔖_{n}, à savoir le groupe des permutations d’ordre n, le théorème a été prouvé par Foata et Zeilberger [FoZe90]. Le théorème pour une classe R(c) quelconque est dû à Han [Han91]. Ce dernier a eu aussi le mérite de donner la bonne définition de “den” dans le cas général (définition qui a été rappelée plus haut) et, de façon plus essentielle, de construire une nouvelle transformation bijective Φ_{3} de R(c) sur elle-même satisfaisant :

(des, maj)(w) = (exc, den)(Φ_{3}(w))

identiquement.

Comme dit plus haut, le second type de préoccupations est de calculer les distributions de ces statistiques. Il est clair qu’il existe plusieurs façons d’exprimer celles-ci : on peut calculer la fonction génératrice des polynômes générateurs de chaque classe R(c), ou bien dégager une relation de récurrence pour les coefficients de ces mêmes polynômes (l’exercice consistant de passer d’une forme à l’autre pouvant être plus ou moins facile !).

Grâce à la transformation Φ_{3}, le calcul de la distribution de (exc, den) se ramène donc à celui de la distribution de (des, maj). Pour répondre au problème posé par Denert, tout revient donc à calculer la distribution de (des, maj) sur toute classe R(c). C’est ce que nous nous proposons de faire dans cet article. De façon précise, si

(1.2)  A_{c}(t, q) = ∑_{w} t^{des w}q^{maj w}  (w ∈ R(c))

est le polynôme générateur de (des, maj) sur la classe R(c), le but est de trouver une formule close pour la fonction génératrice (de faculté) de ces polynômes.

Sous une forme équivalente, le résultat n’est pas nouveau et remonte à MacMahon [MacM16] (voir section 2). Nous nous proposons ici, dans cette même section 2, de réactualiser la méthode des anciens. Dans une troisième partie, nous montrons comment les relations de récurrence s’obtiennent à partir de manipulations analytiques sur ces séries de faculté. Dans la quatrième section, nous montrons qu’en fait ce calcul peut s’obtenir, de façon naturelle, à partir des identités de Cauchy sur les fonctions de Schur

∑_{λ} S_{λ}(x)S_{λ}(y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1} et ∑_{λ} S_{λ}(x)S_{λ′}(y) = ∏_{i,j}(1 + x_{i}y_{j}).

L’avantage de cette méthode est, d’une part, d’obtenir interprétations combinatoires et identités entre séries de faculté directement de la théorie classique des fonctions symétriques ; d’autre part, de nécessiter peu de calcul, une fois connues les identités de base et leurs interprétations.

De plus, cette algèbre des fonctions de Schur et les identités classiques sur les fonctions hypergéométriques suggèrent une extension naturelle au cas des bimots dits colorés — ceci fait l’objet de la section 5 —et aussi une extension hypergéométrique à plusieurs bases, qui sera exposée dans la section 7.

Quelques indications sur les notations utilisées. D’abord les notations classiques de la q-factorielle montante

\begin{aligned}(a; q)_{n} & = \{ \begin{matrix}1, & si n = 0 ; \\ (1 − a)(1 − aq) … (1 − aq^{n−1}), & si n ≥ 1 ; \end{matrix} \\ (a; q)_{∞} & = lim_{n}(a; q)_{n} = ∏_{n≥0}(1 − aq^{n}) ; \end{aligned}

et des q-coefficients binomiaux et multinomiaux :

\left[{n \atop m}\right] = \frac{(q; q)_{n}}{(q; q)_{m}(q; q)_{n−m}} ;

(1.3) \left[{c_{1} + c_{2} + … + c_{r} \atop c_{1}, c_{2}, …, c_{r}}\right] = \frac{(q; q)_{c_{1}+c_{2}+···+c_{r}}}{(q; q)_{c_{1}}(q; q)_{c_{2}} … (q; q)_{c_{r}}} .

Si c = (c_{1}, c_{2}, …, c_{r}) est une suite d’entiers, on pose |c| = c_{1} + c_{2} + … + c_{r}. Si maintenant u_{1}, u_{2}, …, u_{r} sont r variables, il sera commode de poser : u^{c} = u_{1}^{c_{1}}u_{2}^{c_{2}} … u_{r}^{c_{r}}. Les lettres grasses représenteront, en général, des suites. Par exemple, on utilisera les notations abrégées du type : (u; q)_{s+1} = (u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}. Enfin, on posera : c + 1_{r} = (c_{1}, …, c_{r−1}, c_{r} + 1) et on notera que toutes les sommations de la forme ∑_{c}, qui interviennent dans l’article, s’étendent à toutes les suites c = (c_{1}, …, c_{r}) de r entiers positifs, y compris la suite nulle.

Ces notations étant rappelées, on peut dire que la section 4 est une étude analytique et combinatoire de l’identité

(1.4)  ∑_{c} A_{c}(t, q)\frac{u^{c}}{(t; q)_{1+|c|}} = ∑_{s≥0} \frac{t^{s}}{(u; q)_{s+1}} ,

que la section 5 porte sur l’étude de

(1.5)  ∑_{c} C_{c}(z, t, q)\frac{u^{c}}{(t; q)_{1+|c|}} = ∑_{s≥0} \frac{(−zu; q)_{s+1}}{(u; q)_{s+1}} t^{s}.

Les formules de récurrence sur les polynômes C_{c}(z, t, q) seront données dans la section 6.

2. Le calcul des anciens actualisé. — On sait, depuis MacMahon [MacM13] que “maj” a la distribution q-multinomiale sur R(c). On a donc, en utilisant la notation (1.3),

(2.1)  A_{c}(t = 1, q) = \left[{c_{1} + c_{2} + … + c_{r} \atop c_{1}, c_{2}, …, c_{r}}\right] ,

identité qu’on peut récrire, en utilisant le théorème q-binomial (cf. [GaRa90], § 1.3])

∑_{n≥0} \frac{(a; q)_{n}}{(q; q)_{n}} z^{n} = \frac{(az; q)_{∞}}{(z; q)_{∞}} ,

comme :

(2.2)  ∑_{c} A_{c}(t = 1, q)\frac{u^{c}}{(q; q)_{|c|}} = \frac{1}{(u_{1}; q)_{∞} … (u_{r}; q)_{∞}} .

La distribution du couple (des, maj) sur R(c) n’est autre que la “textension” de cette identité (2.3)

∑_{c} A_{c}(t, q)\frac{u^{c}}{(t; q)_{1+|c|}} = ∑_{s≥0} \frac{t^{s}}{(u; q)_{s+1}} (= ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} ),

une identité donnée par Rawlings dans sa thèse [Ra79, p. 27], avec l’interprétation (1.1) pour les polynômes A_{c}(t, q), mais non reproduite dans l’article récrit d’après celle-ci [Ra81].

Le membre de droite de (2.3) est symétrique en les u_{i}. Le membre de gauche l’est donc aussi. Pour toute permutation σ de {1, 2, …, r}, notons σc la suite (c_{σ1}, …, c_{σr}) et R(σc) la classe des réarrangements du mot 1^{c_{σ1}}2^{c_{σ2}} … r^{c_{σr}}. On a donc le résultat suivant.

Proposition 2.1. — Les distributions du couple (des, maj) sur R(c) et sur R(σc) sont identiques.

Démonstration. — Donnons une démonstration combinatoire de ce résultat. Suivant un procédé classique, on démontre la proposition lorsque σ est une transposition de deux éléments adjacents (i, i + 1). Considérons un mot w ∈ R(c) et écrivons en gras tous les facteurs de ce mot de la forme (i + 1)i; remplaçons ensuite les facteurs maximaux de la forme i^{p}(i + 1)^{q} ne comportant pas de lettres grasses par les facteurs i^{q}(i + 1)^{p}. Récrivons enfin en maigre les lettres grasses. Il est clair que cette transformation est une bijection qui envoie tout mot w ∈ R(c) sur un mot w′ ∈ R((i, i+1)c). De plus (des, maj)(w) = (des, maj)(w′).

L’identité (2.3) peut donc se récrire :

∑_{λ} \frac{1}{(t; q)_{1+|λ|}} A_{λ}(t, q)m_{λ}(u) = ∑_{s≥0} \frac{t^{s}}{(u; q)_{s+1}} ,

où la sommation à gauche est sur toutes les partitions d’entiers λ dont le nombre de parts l(λ) est au plus égal à r et où m_{λ}(u) = m_{λ}(u_{1}, …, u_{r}) désigne la fonction monomiale symétrique associée à λ en les variables u_{1}, …, u_{r}.

Or considèrons l’identité de Cauchy sur les fonctions symétriques (cf. [Macd79, § 1.4])

∑_{λ} h_{λ}(x)m_{λ}(y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1},

où h_{λ}(x) = h_{λ_{1}}(x) … h_{λ_{r}}(x) désigne la fonction symétrique homogène associée à la partition λ = (λ_{1}, …, λ_{r}) et prenons pour ensembles x et y de variables les ensembles finis {x_{1}, …, x_{s+1}} et {u_{1}, …, u_{r}}, respectivement. Faisons ensuite la substitution x_{i} ← q^{i−1} (i = 1, …, s + 1). On obtient :

∑_{λ} h_{λ}(1, q, …, q^{s})m_{λ}(u_{1}, …, u_{r}) = \frac{1}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} ;

d’où

∑_{λ} ∑_{s≥0} t^{s}h_{λ}(1, q, …, q^{s})m_{λ}(u) = ∑_{s≥0} \frac{t^{s}}{(u; q)_{s+1}} .

Par conséquent, (2.3) implique la formule

(2.4)  \frac{1}{(t; q)_{1+|λ|}} A_{λ}(t, q) = ∑_{s≥0} t^{s}h_{λ}(1, q, …, q^{s}).

et réciproquement. Puisque h_{l}(1, q, …, q^{s}) = \left[{l+s \atop s}\right] (cf. [Macd79, p. 18]), cette dernière formule peut se récrire aussi :

(2.5)  \frac{1}{(t; q)_{1+|λ|}} A_{λ}(t, q) = ∑_{s≥0} t^{s}\left[{λ_{1} + s \atop s}\right] … \left[{λ_{r} + s \atop s}\right].

C’est sous cette forme que MacMahon, dans son traité [MacM16, vol. 2, p. 211], et Gessel, dans sa thèse [Ge77, p. 98], avaient calculé la distribution du couple (des, maj) sur R(c).

Or, dans l’article de 1913 déjà cité, MacMahon [MacM13] avait utilisé une démonstration authentiquement combinatoire pour établir (2.1), démonstration qu’Andrews a excellemment reproduite dans son livre sur les partitions [An76, p. 42–45] et que Stanley [St72] a étendue au cas de ses (P, ω)-partitions. L’identité (2.1) y est démontrée sous la forme :

(2.6)  \frac{1}{(q; q)_{c_{1}+c_{2}+···+c_{r}}} ∑_{w} q^{maj w} = \frac{1}{(q; q)_{c_{1}}(q; q)_{c_{2}} … (q; q)_{c_{r}}} ,

MacMahon utilise le fait que 1/(q; q)_{m} est la fonction génératrice des partitions d’entiers ayant au plus m parts et construit une bijection entre les suites de partitions comptées par le membre de droite et les paires de partitions et de mots comptées par le membre de gauche. Il est remarquable de voir qu’une simple adaptation de cette bijection permet aussi d’établir (2.5). C’est ce que nous nous proposons de faire ci-dessous.

On utilise, d’une part, l’identité

(2.7)  \frac{1}{(t; q)_{1+|λ|}} = ∑_{i≥0} \left[{|λ| + i \atop i}\right]t^{i}

et, d’autre part, le fait que \left[{m+s \atop s}\right] est le polynôme générateur des partitions ayant au plus m parts, toutes au plus égales à s, ou encore des suites décroissantes (b_{1} ≥ b_{2} ≥ ⋯ ≥ b_{m}) d’entiers positifs satisfaisant :

s ≥ b_{1} ≥ b_{2} ≥ ⋯ ≥ b_{m} ≥ 0.

Le second membre de (2.5) est alors égal à la somme de la série ∑ t^{s}q^{c(T)}, étendue à tous les couples (s, T), où s est un entier positif et T un tableau de coefficients entiers positifs de la forme

(2.8)  \begin{matrix}a_{1,1} & a_{1,2} & … & a_{1,λ_{1}} \\ a_{2,1} & a_{2,2} & … & a_{2,λ_{2}} \\ … & … & … & … \\ a_{r,1} & a_{r,2} & … & a_{r,λ_{r}} \end{matrix}

où chaque ligne est décroissante et a tous ses éléments entre s et 0 et où

c(T) = ∑_{i,j} a_{i,j}.

D’après (2.7), le premier membre de (2.5) est égal à la somme de la série

∑ t^{s′+des w}q^{c(π)+maj w},

étendue à tous les triplets (s′, π, w), où s′ est un entier positif, π une suite (b_{1} ≥ b_{2} ≥ ⋯ ≥ b_{|λ|}) d’entiers compris entre s′ et 0, et w un mot appartenant à R(λ) et où enfin c(π) = b_{1} + ⋯ + b_{|λ|}.

Il s’agit donc de construire une bijection (s, T) ↦ (s′, π, w), satisfaisant :

(2.9)  c(T) = c(π) + maj w  et  s = s′ + des w.

Dans une première étape, on code tout tableau T décrit en (2.8) comme une matrice à deux lignes de la façon suivante. On forme d’abord la matrice :

( \begin{matrix}a_{1,1} & … & a_{1,λ_{1}} & a_{2,1} & … & a_{2,λ_{2}} & … & a_{r,1} & … & a_{r,λ_{r}} \\ 1 & … & 1 & 2 & … & 2 & … & r & … & r \end{matrix} )

puis on réarrange les colonnes de cette matrice [rappelons que |λ| = λ_{1} + ⋯ + λ_{r}]

(2.10)  ( \begin{matrix}v \\ w \end{matrix} ) = ( \begin{matrix}y_{1} & y_{2} & … & y_{|λ|} \\ x_{1} & x_{2} & … & x_{|λ|} \end{matrix} ) ,

de sorte que la première ligne soit décroissante et que si l’on a y_{k} = y_{k+1}, alors x_{k} ≤ x_{k+1}. De façon équivalente :

(2.11)  x_{k} > x_{k+1} ⟹ y_{k} > y_{k+1}.

La première ligne de la matrice (2.10) est un mot v = y_{1}y_{2} … y_{|λ|} de longueur |λ| qui, par construction même, est l’unique réarrangement décroissant de tous les coefficients du tableau T. La seconde ligne de la matrice (2.10) est un mot w = x_{1}x_{2} … x_{m} appartenant à R(λ).

La condition (2.11) permet ainsi de faire correspondre à tout tableau T un et un seul couple de mots (v, w) ayant les propriétés ci-dessus mentionnées.

Enfin, pour i = 1, 2, …, |λ|, notons z_{i} le nombre de descentes dans le facteur droit x_{i}x_{i+1} … x_{|λ|} de w, c’est-à-dire, le nombre d’indices j tels que i ≤ j ≤ |λ| − 1 et x_{j} > x_{j+1}. En particulier,

(2.12)  z_{1} = des w.

Ensuite, par définition de l’indice majeur

(2.13)  maj w = z_{1} + z_{2} + ⋯ + z_{|λ|}.

D’autre part, la condition (2.11) implique que le mot b_{1}b_{2} … b_{|λ|} défini par

(2.14)  b_{i} = y_{i} − z_{i}  (i = 1, 2, …, |λ|),

est décroissant et a toutes ses lettres positives. On pose alors :

s′ = s − des w  et  π = (b_{1}, b_{2}, …, b_{|λ|}).

Comme s ≥ y_{1} = max a_{i,j} et z_{1} = des w, on en déduit : s′ = s − des w ≥ y_{1} − z_{1} = b_{1} ≥ 0. De plus,

\begin{aligned}c(T) = ∑_{i} y_{i} & = ∑_{i} b_{i} + ∑_{i} z_{i} \\ & = c(π) + maj w. \end{aligned}

Enfin, par définition même de s′, on a : s = s′ +des w. Les deux conditions (2.9) sont bien remplies.

On a décrit ici la correspondance entre (s, T) et (s′, π, w). La construction est parfaitement réversible. L’identité (2.5) est donc établie.

Exemple. — Illustrons la dernière construction faite sur un exemple. Partons du tableau T et de l’entier s donnés par

T = 6 5 1 1 0 0 5 4 1 1 3 1  et  s = 7.

Le réarrangement de la matrice

( \begin{matrix}6 & 5 & 1 & 1 & 0 & 0 & 5 & 4 & 1 & 1 & 3 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 3 \end{matrix} )

respectant la condition (2.11) donne :

( \begin{matrix}6 & 5 & 5 & 4 & 3 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 2 & 2 & 3 & 1 & 1 & 2 & 2 & 3 & 1 & 1 \end{matrix} )

D’où

\begin{aligned}v & = & 6 & 5 & 5 & 4 & 3 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ w & = & 1 & 1 & 2 & 2 & 3 & 1 & 1 & 2 & 2 & 3 & 1 & 1 \\ z & = & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ π & = & 4 & 3 & 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{aligned}

des w = 2, s′ = s − des w = 5.

On a bien :

\begin{aligned}c(T) & = 6 + 5 + 1 + 1 + 5 + 4 + 1 + 1 + 3 + 1 = 28 \\ & = c(π) + maj w = (4 + 3 + 3 + 2 + 1) + (5 + 10) = 28. \end{aligned}

3. Relations de récurrence et séries de faculté. — L’identité (2.3) sera établie, directement, à partir des identités sur les fonctions de Schur, dans la section suivante. Les relations de récurrence sur des polynômes comme A_{c}(t, q), dont on connaît la fonction génératrice de faculté (2.3) s’obtiennent, en principe, à partir d’équations aux différences, ici partielles, puisqu’on est en présence d’une série à plusieurs variables. On s’y prend comme suit.

Posons A(t, q; u) = A(t, q; u_{1}, …, u_{r}) = ∑_{c} A_{c}(t, q)\frac{u^{c}}{(t; q)_{1+|c|}} ,

et formons la q-différence finie appliquée à la seule variable u_{r} : D_{u_{r}} = A(t, q; u_{1}, …, u_{r}) − A(t, q; u_{1}, …, u_{r−1}, u_{r}q).

Utilisant le membre de gauche de (2.3), on obtient :

D_{u_{r}} = ∑_{{c \atop c_{r}≥1}} A_{c}(t, q)\frac{u^{c}}{(t; q)_{1+|c|}} − ∑_{{c \atop c_{r}≥1}} A_{c}(t, q)\frac{u_{1}^{c_{1}} … u_{r−1}^{c_{r−1}}(u_{r}q)^{c_{r}}}{(t; q)_{1+|c|}}

= ∑_{c} A_{c+1_{r}}(t, q)\frac{u^{c+1_{r}}}{(t; q)_{2+|c|}} − ∑_{c} A_{c+1_{r}}(t, q)\frac{u_{1}^{c_{1}} … u_{r−1}^{c_{r−1}}(u_{r}q)^{c_{r}+1}}{(t; q)_{2+|c|}}

D_{u_{r}} = ∑_{c}(1 − q^{c_{r}+1})A_{c+1_{r}}(t, q)\frac{u^{c+1_{r}}}{(t; q)_{2+|c|}} .  (⋆)

Utilisons maintenant le membre de droite de (2.3). Il vient :

D_{u_{r}} = ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} − ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}q; q)_{s+1}}

= ∑_{s≥0} \frac{t^{s}}{(u; q)_{s+1}} [1 − \frac{1 − u_{r}}{1 − u_{r}q^{s+1}} ]

= u_{r} ∑_{s≥0} \frac{t^{s}}{(u; q)_{s+1}} [1 − q^{s+1} \frac{1 − u_{r}}{1 − u_{r}q^{s+1}} ]

= u_{r}(A(t, q; u_{1}, …, u_{r}) − qA(tq, q; u_{1}, …, u_{r−1}, u_{r}q)).

D’où la relation :

A(t, q; u_{1}, …, u_{r}) − A(t, q; u_{1}, …, u_{r−1}, u_{r}q) = u_{r}(A(t, q; u_{1}, …, u_{r}) − qA(tq, q; u_{1}, …, u_{r−1}, u_{r}q)). (⋆⋆)

Interprétons le second membre de cette dernière relation. On a :

u_{r}A(t, q; u) = ∑_{c} A_{c}(t, q)\frac{u^{c+1_{r}}}{(t; q)_{1+|c|}}

= ∑_{c}(1 − tq^{1+|c|})A_{c}(t, q)\frac{u^{c+1_{r}}}{(t; q)_{2+|c|}} .  (⋆ ⋆ ⋆)

De même,

u_{r}qA(tq, q; u_{1}, …, u_{r}q) = ∑_{c} A_{c}(tq, q)\frac{u_{1}^{c_{1}} … u_{r−1}^{c_{r−1}}(u_{r}q)^{c_{r}+1}}{(tq; q)_{1+|c|}}

= ∑_{c} q^{c_{r}+1}(1 − t)A_{c}(tq, q)\frac{u^{c+1_{r}}}{(t; q)_{2+|c|}} . (⋆ ⋆ ⋆⋆)

Tenant compte de (⋆) — (⋆ ⋆ ⋆⋆), on en tire la relation de récurrence :

(3.1) (1 − q^{c_{r}+1})A_{c+1_{r}}(t, q)

= (1 − tq^{1+|c|})A_{c}(t, q) − q^{c_{r}+1}(1 − t)A_{c}(tq, q).

Écrivons A_{c}(t, q) = ∑_{s≥0} t^{s}A_{c,s}(q), de sorte que A_{c,s}(q) est la fonction

génératrice des mots w ∈ R(c) tels que des w = s par l’indice majeur et calculons le coefficient de t^{s} dans (3.1). On trouve :

(1 − q^{c_{r}+1})A_{c+1_{r},s}(q)

= A_{c,s}(q) − q^{1+|c|}A_{c,s−1}(q) − q^{c_{r}+1+s}A_{c,s}(q) + q^{c_{r}+1+(s−1)}A_{c,s−1}(q),

soit en divisant par (1 − q) et en utilisant la notation [0]_{q} = 0 et [m]_{q} = 1 + q + ⋯ + q^{m−1} (m ≥ 1),

(3.2) [c_{r} + 1]_{q} A_{c+1_{r},s}(q)

= [c_{r} + 1 + s]_{q} A_{c,s}(q) + q^{s+c_{r}}[1 + |c| − s − c_{r}]_{q} A_{c,s−1}(q),

une relation établie combinatoirement par Rawlings [Ra79].

Les relations (3.1) et (3.2) permettent un calcul aisé des tables des premières valeurs des polynômes A_{c}(t, q), tables que Denert [Den90], n’ayant pas à sa disposition la bijection de (exc, den) avec (des, maj), avait dû calculer directement à l’aide d’ordinateurs. On peut retrouver les premières valeurs de A_{c}(t, q) en faisant z = 0 dans la table des polynômes C_{c}(t, q) reproduite dans la section 6.

4. La méthode des fonctions de Schur. — On peut également calculer la distribution jointe de (des, maj) en s’appuyant sur l’algèbre des fonctions de Schur, méthode qui a déjà été utilisée dans des travaux antérieurs ([DesFo85], [DesFo87], [DesFo91], [FoZe91]). On démontre ainsi directement l’identité (2.3) et non pas ses équivalents (2.5), (3.1) ou (3.2). On part de l’autre forme de l’identité de Cauchy [Macd79, p. 33]

∑_{λ} S_{λ}(x)S_{λ}(y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1},

où S_{λ}(x) désigne la fonction de Schur en un ensemble de variables x. Comme précédemment, avec les variables 1, q, …, q^{s} et u_{1}, …, u_{r} pour les ensembles x et y, on obtient

∑_{λ} S_{λ}(u_{1}, …, u_{r})S_{λ}(1, q, …, q^{s}) = \frac{1}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} ,

d’où

(4.1) ∑_{λ}S_{λ}(u_{1}, …, u_{r})∑_{s≥0} t^{s}S_{λ}(1, q, …, q^{s})=∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} .

Les deux identités (2.3) et (4.1) ont donc même membre de droite. Pour démontrer que leurs membres de gauche sont égaux, on utilise les propriétés de la correspondance de Robinson-Schensted, telle qu’elle est exposée dans l’article de Knuth [Kn70] pour les mots avec répétitions. Ici la correspondance de Robinson-Schensted pour les seules permutations (sans répétitions) (cf. [Kn72, p. 48–72]) n’est plus suffisante. Partons d’un bimot

(4.2)  ( \begin{matrix}v \\ w \end{matrix} ) = ( \begin{matrix}1 & 2 & … & m \\ x_{1} & x_{2} & … & x_{m} \end{matrix} ) ,

où x_{1}x_{2} … x_{m} est un mot de la classe R(c), donc un réarrangement du mot 1^{c_{1}}2^{c_{2}} … r^{c_{r}} (c_{1} +c_{2} +⋯+c_{r} = m). La correspondance de Robinson-Schensted fait correspondre à un tel bimot une paire de tableaux droits (T_{1}, T_{2}), de même forme, disons λ, où T_{1} est un tableau semi-standard, de contenu c (i.e., contenant c_{1} fois 1, …, c_{r} fois r) et où T_{2} est un tableau standard d’ordre m.

Par exemple, au bimot

( \begin{matrix}v \\ w \end{matrix} ) = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 1 & 2 & 2 & 3 & 1 & 1 & 2 & 3 & 3 & 1 & 1 \end{matrix} )

correspond la paire de tableaux

T_{1} = 3 2 2 2 3 1 1 1 1 1 1 3 T_{2} = 11 6 7 8 12 1 2 3 4 5 9 10

tous deux de forme λ = (7, 4, 1).

Cette correspondance ({v \atop w} ) ↦ (T_{1}, T_{2}) a la propriété supplémentaire suivante : si l’entier i est tel que x_{i} > x_{i+1} (dans le mot w), alors le coefficient (i + 1) dans le tableau T_{2} est situé au-dessus de i et réciproquement.

Dans l’exemple traité, les seuls entiers i pour lesquels x_{i} > x_{i+1} sont i = 5 et i = 10 (écrits en gras dans la matrice à deux lignes) et, en effet, seuls les coefficients 5 et 10 ont leurs successeurs 6 et 11 situés au-dessus d’eux dans T_{2}.

Si donc on pose

ides T_{2} = |{i : (i + 1) au-dessus de i dans T_{2}}|
imaj T_{2} = ∑_{i} i ((i + 1) au-dessus de i dans T_{2}),

on en déduit :

des w = ides T_{2} et maj w = imaj T_{2}.

Par conséquent,

A_{c}(t, q) = ∑_{|λ|=|c|} ∑_{(T_{1},T_{2})} t^{ides T_{2}}q^{imaj T_{2}},

où la première sommation est sur toutes les partitions λ de l’entier |c| et la seconde sur les couples (T_{1}, T_{2}), où T_{1} est semi-standard, de contenu c, et T_{2} est standard de même forme que T_{1}.

Le membre de gauche de (2.3) est donc égal à :

∑_{c} \frac{u^{c}}{(t; q)_{1+|c|}} ∑_{|λ|=|c|} ∑_{(T_{1},T_{2})} t^{ides T_{2}}q^{imaj T_{2}}

= ∑_{c} ∑_{|λ|=|c|} ∑_{T_{1}} u^{T_{1}} × \frac{1}{(t; q)_{1+|c|}} ∑_{T_{2}} t^{ides T_{2}}q^{imaj T_{2}},

où l’on a posé u^{T_{1}} = u^{c}, utilisant le fait que T_{1} est de contenu c. Si l’on intervertit les deux premiers signes de sommation au second membre, on voit que la sommation sur c et T_{1} n’est autre que la définition (combinatoire) de la fonction de Schur S_{λ}(u_{1}, …, u_{r}). L’expression à la droite de “×” vaut ∑_{s} t^{s}S_{λ}(1, q, …, q^{s}), d’après un lemme classique (voir théorème 4.1 dans [DesFo85]). Par conséquent, le membre de gauche de (2.3) est égal à :

∑_{λ} S_{λ}(u_{1}, …, u_{r}) ∑_{s≥0} t^{s}S_{λ}(1, q, …, q^{s}).

On retrouve le membre de gauche de (4.1). L’identité (2.3) est donc bien établie.

5. Une extension hypergéométrique basique. — Comme il est d’usage (cf. [GaRa90, p. 4], à une modification près de la variable t), notons

(5.1)  _{p}φ_{r}({v_{1}, …, v_{p} \atop u_{1}, …, u_{r}}; q, t) = ∑_{s≥0} \frac{(v_{1}; q)_{s} … (v_{p}; q)_{s}}{(u_{1}; q)_{s} … (u_{r}; q)_{s}} \frac{t^{s}}{(q; q)_{s}}

la fonction hypergéométrique basique. Alors le membre de droite de (2.3) vaut

\begin{aligned}∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} & = \frac{1}{t} ∑_{s≥1} \frac{(q; q)_{s}}{(u_{1}; q)_{s} … (u_{r}; q)_{s}} \frac{t^{s}}{(q; q)_{s}} \\ & = \frac{1}{t}(_{1}φ_{r}({q \atop u_{1}, …, u_{r}}; q, t) − 1). \end{aligned}

Ceci suggère de trouver une interprétation combinatoire pour une fonction hypergéométrique basique ayant (r + 1) paramètres au numérateur. Nous nous proposons dans cette section d’étudier la fonction

(5.2) \frac{1}{t}(_{r+1}φ_{r}({q, −zu_{1}, …, −zu_{r} \atop u_{1}, …, u_{r}}; q, t) − 1)

= ∑_{s≥0} \frac{(−zu_{1}; q)_{s+1} … (−zu_{r}; q)_{s+1}}{(u_{1}; q)_{s+1} … (u_{r})_{s+1}} t^{s}

et de montrer qu’elle se développe, en utilisant les mêmes notations qu’au paragraphe précédent, en une série

(5.3)  ∑_{c} C_{c}(z, t, q)\frac{u^{c}}{(t; q)_{1+|c|}}

où C_{c}(z, t, q) est pour tout c un polynôme sur des bimots bicolorés (dans un sens qui sera précisé plus loin).

Comme dans la section précédente, on considère les bimots w = ({v \atop w} ) de la forme (4.2) et on appelle bimot coloré la donnée d’un tel mot et d’un choix, disons J, de bilettres ({i \atop x_{i}} ) supposées colorées en jaune, les autres l’étant en bleu. On extrait de ce bimot coloré, qu’on notera (w, J), les deux sous-bimots unicolores formés par les bilettres jaunes et les bilettres bleues, respectivement ({v_{1} \atop w_{1}} ) et ({v_{2} \atop w_{2}} ). Notons que le mot v étant (strictement) croissant, les deux mots v_{1} et v_{2} le sont aussi.

Permutons les bilettres de ({v_{1} \atop w_{1}} ) (le bimot jaune) de façon à obtenir un bimot ({a_{1}...a_{m_{1}} \atop b_{1}...b_{m_{1}}} ) dont la ligne du bas b_{1} … b_{m_{1}} est décroissante, et si l’on a b_{k} = b_{k+1}, alors a_{k} > a_{k+1}, les lettres a_{i} étant, en effet, distinctes. On permute ensuite les bilettres de ({v_{2} \atop w_{2}} ) (le bimot bleu) pour obtenir un bimot ({c_{1}...c_{m_{2}} \atop d_{1}...d_{m_{2}}} ), dont la ligne du bas est cette fois croissante, et si l’on a d_{k} = d_{k+1}, alors c_{k} < c_{k+1}. L’associé ass(w, J) du couple (w, J) est défini comme le produit de juxtaposition des mots du haut

ass(w, J) = a_{1} … a_{m_{1}}c_{1} … c_{m_{2}}.

Prenons, par exemple, le bimot coloré

(w, J) = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 4 & 1 & 2 & 1 & 3 & 3 & 4 & 1 & 4 & 2 & 1 & 3 \end{matrix} ) ,

où les couples verticaux colorés en jaune (resp. bleu) apparaissent en maigre (resp. en gras). On a :

( \begin{matrix}v_{1} \\ w_{1} \end{matrix} ) = ( \begin{matrix}1 & 2 & 5 & 6 & 10 & 12 \\ 4 & 1 & 3 & 3 & 2 & 3 \end{matrix} ) et ( \begin{matrix}v_{2} \\ w_{2} \end{matrix} ) = ( \begin{matrix}3 & 4 & 7 & 8 & 9 & 11 \\ 2 & 1 & 4 & 1 & 4 & 1 \end{matrix} ) .

En permutant les bilettres de ces bimots, comme indiqué, on obtient :

( \begin{matrix}1 & 12 & 6 & 5 & 10 & 2 \\ 4 & 3 & 3 & 3 & 2 & 1 \end{matrix} ) et ( \begin{matrix}4 & 8 & 11 & 3 & 7 & 9 \\ 1 & 1 & 1 & 2 & 4 & 4 \end{matrix} )

On a donc : ass(w, J) = 1, 12, 6, 5, 10, 2, 4, 8, 11, 3, 7, 9.

Revenons au cas général et notons y_{1}y_{2} … y_{m} l’associé du mot coloré (w, J). Par construction même, ce mot est une permutation de 12 … m. On appelle ligne inverse de route de (w, J) l’ensemble, noté Iligne(w, J), de tous les entiers i tels que 1 ≤ i ≤ m − 1 et tels que (i + 1) est à la gauche de i dans y_{1}y_{2} … y_{m}. On pose alors

ides(w, J) = # Iligne(w, J) et imaj(w, J) = ∑_{i} i (i ∈ Iligne(w, J)).

A toute classe de réarrangements R(c) (c_{1} + ⋯ + c_{r} = m), on associe le polynôme

(5.4)  C_{c} = C_{c}(z, t, q) = ∑_{(w,J)} z^{|J|}t^{ides(w,J)}q^{imaj(w,J)},

où la somme est sur tous les bimots w ∈ R(c), et sur toutes les parties J de l’intervalle [m] = {1, 2, …, m}.

Théorème 5.1. — La fonction (5.2) se développe en la série de faculté (5.3), où C_{c}(z, t, q) est le polynôme défini en (5.4).

Avant d’établir ce théorème, notons que lorsque z = 0, les seules contributions à la précédente somme sont les bimots dont toutes les bilettres sont bleues. Pour déterminer l’associé de chacun de ces bimots, on permute toutes les bilettres (bleues) de w, de sorte à avoir un bimot ({c_{1}...c_{m} \atop d_{1}...d_{m}} ) tel que d_{1} ≤ ⋯ ≤ d_{m} et tel que si d_{k} = d_{k+1}, alors c_{k} < c_{k+1}. L’associé est ici c_{1} … c_{m}. Si donc (i+1) est à la gauche de i dans ce dernier mot, disons aux positions k et l, soit

( \begin{matrix}c_{1} & … & (i + 1) & … & i & … & c_{m} \\ d_{1} & … & d_{k} & … & d_{l} & … & d_{m} \end{matrix} ) ,

on a forcément d_{k} ≤ d_{l}, donc a fortiori d_{k} < d_{l}, à cause des conditions sur les c_{i} et d_{i} juste rappelées. Par conséquent, dans le bimot w originel, on avait la situation

w = ( \begin{matrix}v \\ w \end{matrix} ) = ( \begin{matrix}… & i & (i + 1) & … \\ … & d_{l} & d_{k} & … \end{matrix} ) .

Le mot w a donc une descente en position i. Réciproquement, si cette dernière condition est réalisée, les règles de réarrangement ci-dessus entraînent que (i + 1) est à la gauche de i dans c_{1} … c_{m}. Par conséquent,

ides(w, ∅) = des w  et  imaj(w, ∅) = maj w.

On en tire : (5.5) C_{c}(z = 0, t, q) = A_{c}(t, q).

Pour démontrer le théorème 5.1, nous faisons de nouveau appel à la correspondance de Robinson-Schensted. Conservant les mêmes notations que précédemment, au bimot ({v_{i} \atop w_{i}} ) correspond une paire de tableaux (P_{i}, Q_{i}), de même forme, disons λ, où P_{i} est un tableau semi-standard, dont les coefficients sont les lettres de w_{i}, où Q_{i} est un tableau injectif dont les coefficients sont les lettres (distinctes) de v_{i} (i = 1, 2).

Par exemple, au bimot coloré précédent correspondent les paires de tableaux :

( \begin{matrix}v_{1} \\ w_{1} \end{matrix} ) = ( \begin{matrix}1 & 2 & 5 & 6 & 10 & 12 \\ 4 & 1 & 3 & 3 & 2 & 3 \end{matrix} ) ↦ (P_{1}, Q_{1}) = (\begin{matrix}4 \\ 3 \\ 1 & 2 & 3 & 3 , \end{matrix}\begin{matrix}10 \\ 2 \\ 1 & 5 & 6 & 12 \end{matrix} );

( \begin{matrix}v_{2} \\ w_{2} \end{matrix} ) = ( \begin{matrix}3 & 4 & 7 & 8 & 9 & 11 \\ 2 & 1 & 4 & 1 & 4 & 1 \end{matrix} ) . ↦ (P_{2}, Q_{2}) = (\begin{matrix}2 & 4 & 4 \\ 1 & 1 & 1 , \end{matrix} \begin{matrix}4 & 8 & 11 \\ 3 & 7 & 9 \end{matrix} ) .

Revenant au cas général, on associe alors à chaque bimot coloré (w, J) la paire de tableaux gauches

T_{1} = P_{1} ⊗ P_{2}, T_{2} = Q′_{1} ⊗ Q_{2},

où Q′_{1} est le transposé du tableau Q_{1} et où le symbole “⊗” désigne le produit usuel des tableaux : pour T_{1}, par exemple, le tableau P_{2} est placé à la droite et plus bas que P_{1}. La ligne inverse, Iligne T, d’un tableau gauche T est encore définie comme l’ensemble des entiers i tels que (i + 1) est écrit plus haut que i dans T. On note, comme précédemment, ides T (resp. imaj T) le cardinal (resp. la somme des éléments) de Iligne T. Les propriétés classiques de la correspondance de Robinson-Schensted (voir, par exemple, [DesFo85], § 3) entraînent alors le résultat suivant.

Proposition 5.2. — A tout bimot coloré (w, J) de longueur m correspond bijectivement un diagramme gauche λ ⊗ μ et une paire de tableaux (T_{1}, T_{2}), respectivement de forme λ ⊗ μ et λ′ ⊗ μ, où T_{1} est semistandard et a comme coefficients les lettres du mot w, où T_{2} est bijectif de contenu [m] et où |λ| = |J| et |μ| = m − |J|. De plus

Iligne(w, J) = Iligne T_{2}.

En particulier

ides(w, J) = ides T_{2}  et  imaj(w, J) = imaj T_{2}.

Au bimot coloré traité dans l’exemple courant correspond la paire de tableaux suivante (où l’on a souligné les éléments de Iligne(w, J) et de Iligne T_{2}) :

T_{1} = 4 3 1 2 3 3 2 4 4 1 1 1 T_{2} = 12 6 \underline{5} 1 2 10 \underline{4} 8 \underline{11} \underline{3} \underline{7} \underline{9}

On a :

Iligne(w, J) = Iligne(1, 12, 6, \underline{5}, 10, 2, \underline{4}, 8, \underline{11}, \underline{3}, \underline{7}, \underline{9}) = \{\underline{5}, \underline{4}, \underline{11}, \underline{3}, \underline{7}, \underline{9}\}
= Iligne T_{2}.

Il en résulte que le polynôme C_{c}(z, t, q) peut encore s’exprimer par

C_{c}(z, t, q) = ∑_{|λ|+|μ|=|c|} z^{|λ|} ∑_{(T_{1},T_{2})} t^{ides T_{2}}q^{imaj T_{2}},

où la seconde sommation est sur tous les couples (T_{1}, T_{2}) tels que T_{1} est semi-standard de forme λ ⊗ μ et T_{2} est standard de forme λ′ ⊗ μ.

On a donc l’identité

∑_{c} \frac{u^{c}}{(t; q)_{1+|c|}} C_{c}(z, t, q)

= ∑_{c} \frac{u^{c}}{(t; q)_{1+|c|}} ∑_{|λ|+|μ|=|c|} z^{|λ|} ∑_{(T_{1},T_{2})} t^{ides T_{2}}q^{imaj T_{2}}

= ∑_{c} ∑_{|λ|+|μ|=|c|} z^{|λ|} ∑_{T_{1}} u^{T_{1}} × \frac{1}{(t; q)_{1+s}} ∑_{T_{2}} t^{ides T_{2}}q^{imaj T_{2}}.

Comme précédemment, on utilise la définition combinatoire de la fonction de Schur gauche S_{λ⊗μ}(u_{1}, …, u_{r}) ; de plus, la dernière quantité à droite du symbole “×” est égale à ∑_{s≥0} t^{s}S_{λ⊗μ}(1, q, …, q^{s}), en utilisant le même lemme sur les fonctions de Schur ([DesFo85], théorème 4.1). On en tire :

∑_{c} \frac{u^{c}}{(t; q)_{1+|c|}} C_{c}(z, t, q) = ∑_{λ,μ} z^{|λ|} ∑_{|c|=|λ|+|μ|}∑_{T_{1}} u^{T_{1}} ∑_{s≥0} t^{s}S_{λ′⊗μ}(1, q, …, q^{s})

= ∑_{s≥0} t^{s} ∑_{λ,μ} z^{|λ|}S_{λ⊗μ}(u_{1}, …, u_{r})S_{λ′⊗μ}(1, q, …, q^{s})

= ∑_{s≥0} t^{s} ∑_{λ,μ}z^{|λ|}S_{λ}(u_{1}, …, u_{r})S_{μ}(u_{1}, …, u_{r})

× S_{λ′}(1, q, …, q^{s})S_{μ}(1, q, …, q^{s})

= ∑_{s≥0} t^{s} \frac{(−zu_{1}; q)_{s+1} … (−zu_{r}; q)_{s+1}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} ,

d’après les formules de Cauchy

∑_{λ} z^{|λ|}S_{λ}(x)S_{λ′}(y) = ∏_{i,j}(1+zx_{i}y_{j}) et ∑_{μ} S_{μ}(x)S_{μ}(y) = ∏_{i,j}(1−x_{i}y_{j})^{−1} ,

utilisées avec les variables x = {1, q, …, q^{s}} et y = {u_{1}, …, u_{r}}.

6. Une étude des polynômes C_{c}. — On peut trouver également une relation de récurrence pour les polynômes C_{c}(z, t, q) suivant la méthode développée dans la section 3.

Posant C(z, t, q; u) = C(z, t, q; u_{1}, …, u_{r}) = ∑_{c} C_{c}(z, t, q)\frac{u^{c}}{(t; q)_{1+|c|}} ,

et

D_{u_{r}} = C(z, t, q; u_{1}, …, u_{r}) − C(z, t, q; u_{1}, …, u_{r−1}, u_{r}q).

On trouve d’abord

D_{u_{r}} = ∑_{c}(1 − q^{c_{r}+1})C_{c+1_{r}}(z, t, q)\frac{u^{c+1_{r}}}{(t; q)_{2+|c|}} ,

et ensuite

D_{u_{r}} = ∑_{s≥0} \frac{(−zu_{1}; q)_{s+1} … (−zu_{r}; q)_{s+1}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} t^{s}

− ∑_{s≥0} \frac{(−zu_{1}; q)_{s+1} … (−zu_{r}q; q)_{s+1}}{(u_{1}; q)_{s+1} … (u_{r}q; q)_{s+1}} t^{s}

= ∑_{s≥0} \frac{(−zu; q)_{s+1}}{(u; q)_{s+1}} t^{s}[1 − \frac{(1 − u_{r})(1 + zu_{r}q^{s+1})}{(1 − u_{r}q^{s+1})(1 + zu_{r})}]

= ∑_{s≥0} \frac{(−zu; q)_{s+1}}{(u; q)_{s+1}} t^{s}[u_{r} \frac{1 + z}{1 + zu_{r}} − u_{r}q^{s+1} \frac{(1 − u_{r})(1 + zu_{r}q^{s+1})}{(1 − u_{r}q^{s+1})(1 + zu_{r})}

−u_{r}q^{s+1} \frac{(1 − u_{r})z}{(1 + zu_{r})}].

D’où l’on tire, en posant C(z, t, q; u_{r}q) = C(z, t, q; u_{1}, …, u_{r−1}, u_{r}q), l’identité

C(z, t, q; u) − C(z, t, q; u_{r}q)

− u_{r}(zC(z, t, q; u_{r}q) − C(z, t, q; u))

+ u_{r}q(C(z, tq, q; u_{r}q) + zC(z, tq, q; u))

+ u_{r}^{2}zq(C(z, tq, q; u_{r}q) − C(z, tq, q; u)) = 0.

On en déduit la relation de récurrence :

(6.1) (1 − q^{c_{r}+1})C_{c+1_{r}}(z, t, q)

− (1 − tq^{1+|c|})(1 + zq^{c_{r}})C_{c}(z, t, q)

+ q(1 − t)(q^{c_{r}} + z)C_{c}(z, tq, q)

+ z(1 − t)(1 − tq^{1+|c|})(q^{c_{r}} − q)C_{c−1_{r}}(z, tq, q) = 0,

où l’on pose C_{0}(z, t, q) = 1 et où C_{c}(z, t, q) = 0, si l’une des composantes c_{i} de c est négative.

La relation (6.1) permet le calcul des premières valeurs. On trouve :

C_{(1)} = 1 + z;  C_{(1,1)} = (1 + z)^{2}(1 + tq) ;  C_{(2)} = (1 + z)(1 + ztq) ;

C_{(1,1,1)} = (1 + z)^{3}(1 + t(2q + 2q^{2}) + t^{2}q^{3}) ;

C_{(2,1)} = (1 + z)^{2}(1 + t(q + q^{2}) + zt(q + q^{2}) + zt^{2}q^{3}) ; C_{(3)} = (1 + z)(1 + zt(q + q^{2}) + z^{2}t^{2}q^{3}) ;

C_{(1,1,1,1)} = (1 + z)^{4}(1 + t(3q + 5q^{2} + 3q^{3}) + t^{2}(3q^{3} + 5q^{4} + 3q^{3}) + t^{3}q^{6}) ;

C_{(2,1,1)} = (1 + z)^{3}(1 + t(2q + 3q^{2} + 2q^{3}) + t^{2}(q^{2} + 2q^{4} + q^{5})

+ zt(q + 2q^{2} + q^{3}) + zt^{2}(2q^{3} + 3q^{4} + 2q^{5}) + zt^{3}q^{6}) ;

C_{(2,2)} = (1 + z)^{2}(1 + t(q + 2q^{2} + q^{3}) + t^{2}q^{4} + zt(2q + 2q^{2} + 2q^{3})

+ zt^{2}(2q^{3} + 2q^{4} + 2q^{5}) + z^{2}tq^{2} + z^{2}t^{2}(q^{3} + 2q^{4} + q^{5}) + z^{2}t^{3}q^{6}) ;

C_{(3,1)} = (1 + z)^{2}(1 + t(q + q^{2} + q^{3}) + zt(q + 2q^{2} + q^{3})

+ zt^{2}(q^{3} + 2q^{4} + q^{5}) + z^{2}t^{2}(q^{3} + q^{4} + q^{5}) + z^{2}t^{3}q^{6}) ;

C_{(4)} = (1 + z)(1 + zt(q + q^{2} + q^{3}) + z^{2}t^{2}(q^{3} + q^{4} + q^{5}) + z^{3}t^{3}q^{6}).

Dans les notations des sections 3 et 4, le polynôme A_{(1^{n})}(t, q) n’est autre que le polynôme q-eulérien, fonction génératrice de (des, maj) sur le groupe des permutations 𝔖_{n}, habituellement noté A_{n}(t, q). Les formules (3.1) et (3.2) redonnent directement les relations de récurrence de ces polynômes pour c = (1^{n}). Cette remarque est utilisée dans la démonstration de la proposition suivante.

Proposition 6.1.

(i) Les polynômes C_{c} sont symétriques en l’argument c.

(ii) Si c_{1} ≥ ⋯ ≥ c_{r} ≥ 1, alors le polynôme C_{c}(z, t, q) est divisible par (1 + z)^{r}.

(iii) On a : C_{(1^{n})}(z, t, q) = (1 + z)^{n}A_{(1^{n})}(t, q) (n ≥ 1), où A_{(1^{n})}(t, q) est le q-polynôme eulérien.

(iv) On a : C_{(n)}(z, t, q) = (1 + z)(−ztq; q)_{n−1} (n ≥ 1).

La propriété (i) de symétrie résulte de l’expression même de la fonction génératrice de ces polynômes. On peut évidemment la prouver combinatoirement par un argument analogue à celui développé dans la proposition 2.1.

Les trois autres propriétés résultent immédiatement de la formule de récurrence (6.1). Ces polynômes ont des propriétés de symétrie en les z et t qui seront étudiées dans des travaux ultérieurs.

7. Quelques remarques pour conclure. — Faisons q = 1 dans (2.3), de sorte qu’on obtient la fonction génératrice du nombre de descentes (ou du nombre d’excédances) sur l’ensemble des mots tirés d’un alphabet à r lettres. On obtient

∑_{c} A_{c}(t, q = 1)\frac{u^{c}}{(1 − t)^{1+|c|}} = ∑_{s≥0} \frac{t^{s}}{(1 − u_{1})^{s+1} … (1 − u_{r})^{s+1}} ,

d’où, par le changement de variables u_{i}/(1 − t) ← v_{i} (i = 1, 2, …, r), l’identité

∑_{c} A_{c}(t, q = 1)v^{c} = \frac{1 − t}{(1 − v_{1}(1 − t)) … (1 − v_{r}(1 − t)) − t},

ou, sous une forme équivalente,

∑_{c} A_{c}(t, q = 1)v^{c}

= \frac{1}{1 − e_{1}(v) + (1 − t)e_{2}(v) − ⋯ + (−1)^{r}(1 − t)^{r−1}e_{r}(v)},

où les e_{i}(v) sont les fonctions symétriques élémentaires en les v_{i}. On peut encore transformer cette identité en

∑_{c} A_{c}(t, q = 1)v^{c} = 1/D,

où D est le déterminant

D = | \begin{matrix}1 − v_{1} & −tv_{2} & … & −tv_{r−1} & −tv_{r} \\ −v_{1} & 1 − v_{2} & … & −tv_{r−1} & −tv_{r} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ −v_{1} & −v_{2} & … & 1 − v_{r−1} & −tv_{r} \\ −v_{1} & −v_{2} & … & −v_{r−1} & 1 − v_{r} \end{matrix} |

et on retrouve ainsi le calcul direct de la fonction génératrice du nombre des excédances, lorsqu’on applique le “Master Theorem” de MacMahon [MacM16, vol. 1, p. 97 et p. 186] à la matrice triangulaire qui n’a que des t strictement au-dessus de la diagonale et des 1 partout ailleurs.

La méthode des sections 4 et 5 avait été utilisée dans [DesFo85] pour un calcul analogue sur les seules permutations, et non pas sur les mots (avec ou sans répétitions). Toutefois, sur les permutations, on peut traiter simultanément des statistiques sur la permutation elle-même et aussi sur son inverse. On retrouvait ainsi les résultats de Garsia-Gessel [GaGe79] sur la distribution du vecteur (des, maj, ides, imaj), où l’on pose, pour toute permutation σ : ides σ = des σ^{−1} et imaj σ = maj σ^{−1}.

Si on multiplie l’identité (1.5) par (1 − t) et si l’on fait t = 1, on trouve

∑_{c} C_{c}(z, t = 1, q)\frac{u^{c}}{(q; q)_{1+|c|}} = \frac{(−zu; q)_{∞}}{(u; q)_{∞}} ,

une extension-produit de la formule q-binomiale.

Comme me le faisait remarquer Reiner [Rei92], la méthode des sections 4, 5 et 7, qui repose sur l’algèbre des fonctions de Schur, utilise en fait deux fois les propriétés de la correspondance de Robinson-Schensted, une première fois, lorsqu’on exprime le polynôme générateur des mots en termes de paires de tableaux, une seconde fois, lorsqu’on applique le lemme de comptage sur les fonctions de Schur (théorème 4.1 de [DesFo85]). C’est vrai. On peut économiser une utilisation, mais il faut alors faire appel à l’étude des (P, ω)-partitions chère à Stanley [St72] et invoquer sa proposition 8.3.

Remerciements. — L’auteur remercie Guo-Niu Han pour sa relecture attentive du manuscrit et pour ses suggestions qui ont amélioré la rédaction finale. Il a également calculé une table des polynômes C_{c}(z, t, q) plus étendue que celle reproduite ici.

Note ajoutée lors de la correction des épreuves. — Les polynômes C_{c}(z, t, q) ont, en fait, déjà été introduits par Rawlings (Multicolored Simon Newcomb Problems, J. Combinatorial Theory, Ser. A, 53 (1990) 53–67) dans une interprétation combinatoire quasiment analogue, de sorte que le théorème 5.1 doit lui être attribué. Au lieu de s’appuyer sur l’algèbre des fonctions de Schur comme ici, il fait appel à une algèbre des matrices bicolorées, par lui développée.

Depuis la conférence de Montréal de juin 1992, au cours de laquelle le présent article avait été présenté, le calcul eulérien a eu d’autres prolongements. Voir les trois articles par Robert J. Clarke et l’auteur, devant paraître dans European J. Combinatorics en 1994 et 1995.

BIBLIOGRAPHIE

[An76] ANDREWS (George E.). — The Theory of Partitions. — London, Addison-Wesley,

1976 (Encyclopedia of Math. and Its Appl., 2).

[CaFo79] CARTIER (Pierre) et FOATA (Dominique). — Problèmes combinatoires de permutations et réarrangements. — Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

[Cla90] CLARKE (R. J. ). — A short proof of a result of Foata and Zeilberger, à paraître dans Adv. Appl. Math., 1990.

[Den90] DENERT (M.). — The genus zeta function of hereditary orders in central simple

algebras over global fields, Math. Comp., t. 54, 1990, p. 449-465.

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

[DesFo87] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Fonctions symétriques et séries hypergéométriques basiques multivariées, II, Combinatoire Énumérative [Actes Colloque Univ. Québec, Montréal. 1985], p. 68–90. — Berlin, Springer-Verlag, 1987 (Lecture Notes in Math., 1234).

[DesFo91] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Statistiques d’ordre sur les

permutations colorées, Discrete Math., t. 87, 1991, p. 133–148.

[Fo68] FOATA (Dominique). — On the Netto inversion number of a sequence, Proc.

Amer. Math. Soc, t. 19, 1968, p. 236-240.

[FoZe90] FOATA (Dominique) and ZEILBERGER (Doron). — Denert’s Permutation Statistic Is Indeed Euler-Mahonian, Studies in Appl. Math., t. 83, 1990, p. 31–59.

[GaRa90] GASPER (George) and RAHMAN (Mizan). — Basic Hypergeometric Series. London, Cambridge Univ. Press, 1990 (Encyclopedia of Math. and Its Appl., 35).

[GaGe79] GARSIA (Adriano M.) and GESSEL (Ira). — Permutation Statistics and Parti-

tions, Advances in Math., t. 31, 1979, p. 288–305.

[Ge77] GESSEL (Ira). — Generating functions and enumeration of sequences, Ph.D. thesis, department of mathematics, M.I.T., Cambridge, Mass., 111 p., 1977.

[Han91] HAN (Guo-Niu). — Une transformation fondamentale sur les réarrangements de mots, Adv. Math., t. 105, 1994, p. 26–41.

[Knu70] KNUTH (Donald E.). — Permutations, matrices, and generalized Young tableaux, Pacific J. Math., t. 34, 1970, p. 709–727.

[Knu72] KNUTH (Donald E.). — The Art of Computer Programming, vol. 3, Sorting and Searching. — Don Mills, Ontario, Addison-Wesley, 1972.

[Macd79] MACDONALD (Ian G.). — Symmetric Functions and Hall Polynomials. — Oxford, Clarendon Press, 1979.

[MacM13] MACMAHON (Percy Alexander). — The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math., t. 35, 1913, p. 314–321.

[MacM15] MACMAHON (Percy Alexander). — Combinatory Analysis, vol. 1 et 2. — Cam-

bridge, Cambridge Univ. Press, 1915 (Réimprimé par Chelsea, New York, 1955).

[Ra79] RAWLINGS (Don). — Permutation and Multipermutation Statistics, Ph. D. thesis, Univ. Calif. San Diego. — Publ. I.R.M.A. Strasbourg, 49/P-23, 1979.

[Ra81] RAWLINGS (Don). — Generalized Worpitzky Identities with Applications to Permutation Enumeration, Europ. J. Comb., t. 2, 1981, p. 67–78.

[Re87] REMMEL (J. B.). — Permutation Statistics and (k, l)-hook Schur functions, Discrete Math., t. 67, 1987, p. 271–298.

[Rei92] REINER (Vic). — Commutation orale, 1992.

[St72] STANLEY (Richard P.). — Ordered Structures and Partitions. — Providence, R.I., Amer. Math. Soc., 1972 (Memoirs Amer. Math. Soc., 119).

Dominique Foata,

I.R.M.A. et département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg Cedex.

email : foata@math.u-strasbg.fr