CALCUL BASIQUE DES PERMUTATIONS SIGNÉES, I:

LONGUEUR ET NOMBRE D’INVERSIONS (^{∗})

Dominique FOATA^{1} et GuoNiu HAN^{2}

Abstract: The traditional basic calculus on permutation statistic distributions is extended to the case of signed permutations. Résumé: Le calcul basique classique sur les distributions des statistiques de permutations est prolongé au cas des permutations signées.

Sommaire

1. Permutations signées 1.1. Descentes 1.2. Nombre d’inversions et q-séries 1.3. Fonction génératrice du couple nombre de descentes-longueur 1.4. Paires de permutations 1.5. Fonctions de Bessel basiques 1.6. Multipermutations signées

2. Multipermutations signées compatibles

3. La méthode itérative

4. La fonction génératrice de Reiner Bibliographie

1. Permutations signées

1.1. Descentes. Il y a deux démarches possibles lorsqu’on veut étendre les propriétés statistiques connues sur le groupe des permutations au cas des permutations signées, c’est-à-dire lorsqu’on veut passer de l’étude de A_{n} à celle de B_{n}. La démarche géométrique consiste à réinterpréter dans la géométrie des groupes de Coxeter les propriétés statistiques du groupe des permutations et à appliquer ensuite cette interprétation aux permutations signées.

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

1 Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France. (foata@math.u-strasbg.fr)

2 I.R.M.A., Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France. (guoniu@math.u-strasbg.fr)

La démarche analytique consiste à partir des formules de base connues pour les permutations signées, par exemple la formule donnant la fonction génératrice de ces objets par nombre de descentes (une notion définie au paragraphe suivant) et à leur appliquer la modification analytique déjà utilisée dans le cas des permutations ordinaires. C’est cette démarche que nous adoptons dans les deux articles que nous consacrons au calcul basique des permutations signées. Du point de vue de l’analyste, on peut aussi considérer le présent article comme une étude combinatoire des fonctions de Bessel basiques (voir § 1.5) et le second article [FoHa96] comme une étude combinatoire des analogues finis des fonctions de Bessel basiques

La statistique nombre de descentes, puisque c’est elle qui est le point de départ de notre étude, pour les éléments de B_{n} s’impose d’elle-même: d’abord on définit une permutation signée d’ordre n comme un couple (σ, ε), où σ est une permutation σ = σ(1)σ(2) … σ(n) du mot 12 … n et ε = ε(1)ε(2) … ε(n) est un mot de longueur n en l’alphabet à deux lettres {x, y}. On dit que ε est un mot-xy; on note ℓ(ε|x) (resp. ℓ(ε|y)) le nombre de lettres égales à x (resp. égales à y) dans ε. On note également σ_{ε|x} (resp. σ_{ε|y}) le sous-mot de σ formé par toutes les lettres σ(i) telles que ε(i) = x (resp. ε(i) = y).

Définition 1. On dit que l’entier i est une descente de la permutation signée (σ, ε), si l’une des trois conditions suivantes est remplie:

(i) i = n et ε(n) = x; (ii) 1 ≤ i ≤ n − 1, ε(i) = x, ε(i + 1) = y; (iii) 1 ≤ i ≤ n − 1, ε(i) = ε(i + 1) et σ(i) > σ(i + 1).

On note des(σ, ε) le nombre de descentes de (σ, ε).

Exemple. Soit

\begin{matrix}σ = \\ ε = \end{matrix} (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 6 & 7 & 2 & 4 & 3 & 1 & 8 & 5 & 9 \\ x & y & y & y & x & x & y & x & x \end{matrix})

une permutation signée. On a: σ_{ε|x} = 63159, σ_{ε|y} = 7248 et des(σ, ε) = Card{1, 2, 5, 6, 9} = 5.

Naturellement, on peut se donner au départ l’ordre linéaire (n, x) > ⋯ > (1, x) > (n, y) > ⋯ > (1, y) et obtenir une définition équivalente en gardant (i) et en remplaçant les conditions (ii) et (iii) ci-dessus par

(ii′) 1 ≤ i ≤ n − 1 et (σ(i), ε(i)) > (σ(i + 1), ε(i + 1)).

Tous les auteurs comme Brenti [Br94], Stembridge [Stem92], Reiner [Re93a], [Re93b], [Re93c], [Re95a], Steingrímsson [Ste94], Clarke et le premier auteur [ClFo95] ont adopté une définition équivalente à la définition 1 ci-dessus et ont calculé la fonction génératrice exponentielle des polynômes générateurs de “des” sur B_{n}. Si on forme, en effet,

(1.1) W_{n}(X, Y, t) = ∑_{(σ,ε)} X^{ℓ(ε|x)}Y^{ℓ(ε|y)}t^{des(σ,ε)},

les auteurs cités ont établi l’identité

(1.2) \frac{(1 − t) exp((t − 1)X)}{−t + exp((t − 1)(X + Y))} = ∑_{n≥0} \frac{1}{n!} W_{n}(X, Y, t).

Si dans le membre de gauche de (1.2) on remplace X et Y par u, la fraction devient: (1 − t) exp((t − 1)u)/(−t + exp(2(t − 1)u)). (Dans [Re95a, p. 133], le “2” de l’exponentielle doit être mis au dénominateur et non au numérateur.)

Si l’on pose X = 0 et Y = u dans (1.2), on a W_{n}(X, Y, t) = u^{n} A_{n}(t), où A_{n}(t) est le polynôme Eulérien. On retrouve aussi le fait bien connu que A_{n}(t) est la fonction génératrice des permutations ordinaires par nombre de descentes, ansi que l’identité classique

(1.3)  \frac{1 − t}{−t + exp(u(t − 1))} = ∑_{n≥0} \frac{u^{n}}{n!} A_{n}(t),

1.2. Nombre d’inversions et q-séries. On sait (voir [Re95a], par exemple) que la longueur l_{Cox}(σ) d’une permutation σ du groupe symétrique S_{n}, considéré comme un groupe de Coxeter engendré par les transpositions (i, i + 1) (1 ≤ i ≤ n − 1) n’est autre que l’usuel nombre d’inversions inv σ de σ. On connaît, d’autre part, la fonction génératrice des polynômes générateurs de S_{n} par le couple (des, l_{Cox}) = (des, inv) (voir la formule (1.4) ci-dessous). Il est donc naturel de chercher à calculer la fonction génératrice de B_{n} (et des autres groupes classiques) par le couple (des, l_{Cox}). Ce calcul a été entrepris par Stembridge, Brenti, Reiner (op. cit.). Cependant, comme nous le verrons dans la sous-section 1.3, les formules obtenues ne rentrent plus dans le cadre commode des q-séries. Leur manipulation analytique n’est plus aussi aisée. Notons que la dernière étude faite par Reiner [Re95b] est probablement très prometteuse.

Dans le cas du groupe symétrique, l’algèbre des q-séries s’est imposée et Stanley [St76] a calculé la fonction génératrice des polynômes générateurs de S_{n} par (des, inv) en interprétant le q-analogue de la formule (1.3). Comme cette algèbre est pleinement utilisée dans cet article, nous en rappelons quelques éléments: d’abord, la définition des qfactorielles montantes [An76, GaRa90]

\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}

ensuite, le célèbre théorème q-binomial

∑_{n≥0}(a; q)_{n} \frac{u^{n}}{(q; q)_{n}} = \frac{(au; q)_{∞}}{(u; q)_{∞}};

ainsi que les développements des deux q-exponentielles

e_{q}(u) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}} ;

E_{Q}(u) = ∑_{n≥0} \frac{Q^{\binom{n}{2}}u^{n}}{(Q; Q)_{n}} = (−u; Q)_{∞};

enfin, la notation pour le coefficient q-binomial \left[{n \atop k}\right]_{q} = \frac{(q; q)_{n}}{(q; q)_{k} (q; q)_{n−k}}.

Le q-analogue de (1.3), obtenu par Stanley consiste à remplacer dans (1.3) l’exponentielle “exp” par la q-exponentielle e_{q} et au second membre la normalisation factorielle n! par la normalisation q-factorielle (q; q)_{n}. On obtient:

(1.4)  \frac{(1 − t)}{−t + e_{q}((t − 1)u)} = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} A_{n}(t, q).

Comme prouvé par Stanley (op. cit), le coefficient A_{n}(t, q) est le polynôme générateur de S_{n} par la paire (des, coinv), où coinv = \binom{n}{2} − inv. De plus, lorsque “exp” est remplacé par la seconde q-exponentielle E_{q}, le polynôme A_{n}(t, q) devient le polynôme générateur de S_{n} par (des, inv).

Si donc on veut rester dans l’algèbre des q-séries et obtenir l’extension souhaitée aux permutations signées, il faut faire jouer à l’identité (1.2) le rôle que joue (1.3) pour les permutations ordinaires. En premier lieu il faut lui trouver un q-analogue, avec une interprétation combinatoire intéressante. C’est cette démarche de nature analytique que nous adoptons dans cet article. La statistique “inv” pour les permutations signées se dégagera directement de cette interprétation.

Un bon choix pour un q-analogue de la formule (1.2) est de remplacer le produit des deux exponentielles du dénominateur par un produit de deux q-exponentielles (et non pas par e_{q}((t − 1)(X + Y)), qui fournit alors un q-développement avec des termes négatifs.) Le développement en q-série

(1.5)  \frac{(1 − t) e_{q}((t − 1)X)}{−t + e_{q}((t − 1)X) e_{q}((t − 1)Y)} = ∑_{n≥0} \frac{1}{(q; q)_{n}} W_{n}(X, Y, t, q)

donne pour les termes W_{n}(X, Y, t, q) des polynômes à coefficients entiers positifs. Une des conséquences de notre résultat principal sera de montrer que chaque W_{n}(X, Y, t, q) est un polynôme générateur des permutations signées d’ordre n par une certaine paire de statistiques “(des, coinv)”:

(1.6)  W_{n}(X, Y, t, q) = ∑_{(σ,ε)} X^{ℓ(ε|x)}Y^{ℓ(ε|y)}t^{des(σ,ε)}q^{coinv(σ,ε)}.

On retrouve pour “des(σ, ε)” le nombre de descentes introduit plus haut; quant à “coinv(σ, ε)” c’est un nombre de co-inversions adapté pour les permutations signées, ainsi définies.

On dit qu’un couple d’entiers (i, j) est une inversion (resp. une coinversion) de la permutation signée (σ, ε) d’ordre n, si l’une des conditions suivantes est vérifiée :

(i) ε(i) = ε(j), i < j; et σ(i) > σ(j) (resp. σ(i) < σ(j)); (ii) ε(i) = y, ε(j) = x et σ(i) > σ(j).

On note inv(σ, ε) (resp. coinv(σ, ε)) le nombre d’inversions (resp. le nombre de co-inversions) de (σ, ε).

En reprenant l’exemple précédent, on a inv (\begin{matrix}6 & 7 & 2 & 4 & 3 & 1 & 8 & 5 & 9 \\ x & y & y & y & x & x & y & x & x \end{matrix}) = 4 +

2 + 11 = 17 ; coinv (\begin{matrix}6 & 7 & 2 & 4 & 3 & 1 & 8 & 5 & 9 \\ x & y & y & y & x & x & y & x & x \end{matrix}) = 6 + 4 + 11 = 21.

Les premières valeurs des polynômes W_{n}, donc des polynômes générateurs des permutations signées par la paire (des, coinv), sont données dans le tableau 1.

W_{1} = tX + Y; W_{2} = t(t + q)X^{2} + 2t(1 + q)XY + (t + q)Y^{2};
W_{3} = (2tq + 2tq^{2} + t^{2} + q^{3})Y^{3} + t(1 + q + q^{2})(3q + 2t + 1)XY^{2}

+ t(1 + q + q^{2})(2q + tq + 3t)X^{2}Y + t(2tq + 2tq^{2} + t^{2} + q^{3})X^{3}.

Tableau 1 (distribution de (des, coinv))

Une des conséquences également de notre résultat principal sera de montrer que si dans (1.5) on remplace chaque q-exponentielle e_{q}(u) par la seconde Q-exponentielle E_{Q}(u), les polynômes W_{n}(X, Y, t, q) dans le membre de droite sont les polynômes générateurs des permutations signées par le couple (des, inv). Les premières valeurs de ces polynômes sont donnés dans le tableau 2.

W_{1} = Y + tX; W_{2} = (1 + tQ)Y^{2} + 2t(1 + Q)XY + t(1 + tQ)X^{2};
W_{3} = (1 + 2tQ + 2tQ^{2} + t^{2}Q^{3})Y^{3} + t(1 + Q + Q^{2})(3 + Q + 2tQ)XY^{2}

+ t(1 + Q + Q^{2})(3 + Q + 2tQ)X^{2}Y + t(1 + 2tQ + 2tQ^{2} + t^{2}Q^{3})X^{3}.

Tableau 2 (distribution de (des, inv))

Lorsqu’on se restreint aux éléments de S_{n}, la statistique “inv” pour B_{n}, qui vient d’être définie, n’est autre que le nombre des inversions habituel pour les permutations ordinaires. De même, en faisant X = 0 dans (1.5) on retrouve la formule (1.4) avec son interprétation combinatoire.

1.3. Fonction génératrice du couple nombre de descentes-longueur. La longueur l_{Cox} pour B_{n}, telle qu’elle est explicitée par Brenti [Br94] et Reiner [Re95a], à savoir

\begin{aligned}l_{Cox}(σ, ε) & = #\{i < j : ε(i) = ε(j), σ(i) > σ(j)\} \\ & + #\{i < j : ε(i) = x, ε(j) = y\} + ∑_{ε(i)=x} σ(i), \end{aligned}

se spécialise aussi en le nombre d’inversions lorsqu’on se restreint à S_{n}. En revanche, les polynômes générateurs de B_{n} par (des, l_{Cox}) sont différents des polynômes W_{n} définis dans la précédente sous-section dès que n ≥ 2. Par exemple, les trois premiers polynômes générateurs de B_{n}, disons W′′_{n} (n = 1, 2, 3) par (des, l_{Cox}) sont donnés dans le tableau 3.

W′′_{1} = Y + tX; W′′_{2} = (t + q)Y^{2} + tq(1 + q)^{2}XY + tq^{3}(t + q)X^{2};
W′′_{3} = (t^{2}q^{3} + 2tq^{2} + 2tq + 1)Y^{3}
+ t(1 + q + q^{2})(1 + q + 2q^{2} + tq + tq^{3})XY^{2}
+ t^{2}(1 + q + q^{2})(1 + q^{2} + 2tq + tq^{2} + tq^{3})X^{2}Y
+ tq^{6}(t^{2}q^{3} + 2tq^{2} + 2tq + 1)X^{3}.

Tableau 3 (distribution de (des, l_{Cox}))

Posant Y = 1 et ne conservant que la variable d’homogénéité X, Reiner [Re95a] donne la fonction génératrice des polynômes W′′_{n} (n ≥ 0) sous la forme suivante:

(1.7) \frac{1 − t}{1 − t e_{q}(u(1 − t))} ∑_{n≥0} \frac{(u(1 − t))^{n}}{(−Xq; q)_{n} (q; q)_{n}}

= ∑_{n≥0} \frac{u^{n}}{(−Xq; q)_{n} (q; q)_{n}} W′′_{n}.

Nous établirons cette identité dans le paragraphe 4. La normalisation des polynômes W′′_{n} par le facteur peu commode (−Xq; q)_{n} (q; q)_{n} et la présence de la série correctrice ∑_{n}(u(1 − t))^{n}/((−Xq; q)_{n} (q, q)_{n}) dans le membre de gauche de (1.7) pour laquelle on ne voit pas a priori de propriété analytique intéressante, nous ont fait abandonner la statistique l_{Cox} au profit de “inv” défini au § 1.2. Ce faisant, le calcul statistique sur les paires de permutations, tel qu’il a été initialisé par Carlitz et ses collaborateurs [Ca76] et poursuivi par Stanley [Sta76] et Fedou et Rawlings [FeRa95], se prolonge de façon naturelle au cas de B_{n} dans l’algèbre des q-séries. Ce que nous expliquons maintenant, après avoir rappelé le calcul de Carlitz.

1.4. Paires de permutations. Dans les années soixante-dix, Carlitz et ses collaborateurs [Ca76] avaient réussi à interpréter combinatoirement l’inverse de la fonction de Bessel J_{0}(u). De façon précise, soit

(1.8)  J_{0}(u) = ∑_{n≥0}(−1)^{n} \frac{(u/2)^{2n}}{n! n!}

la fonction de Bessel, de première espèce, d’ordre zéro (voir, e.g., Erdélyi [Er53, vol. 2, p. 4]) ; ils avaient posé

(1.9)  J(u) = J_{0}(2\sqrt{u}) = ∑_{n≥0}(−1)^{n} \frac{u^{n}}{n! n!},

et avaient observé que les coefficients ω_{n} de u^{n}/(n! n!) dans la série inverse

(1.10)  \frac{1}{J(u)} = ∑_{n≥0} ω_{n} \frac{u^{n}}{n! n!}

étaient des entiers positifs et donc susceptibles de recevoir une interprétation combinatoire. Poussant plus loin leurs investigations, ils avaient développé en série la fraction

(1.11)  \frac{1 − t}{−t + J(u(1 − t))} = 1 + ∑_{n≥1} \frac{u^{n}}{n! n!} ∑_{0≤k≤n−1} ω(n, k)t^{k},

qui se réduit à (1.10) lorsque t = 0, d’où ω(n, 0) = ω_{n} (n ≥ 0) et avaient cherché à donner une interprétation combinatoire aux coefficients ω(n, k). Ils avaient ainsi introduit la notion de descente en commun dans une paire de permutations, notion qu’on peut décrire de la façon suivante.

Soient π et ρ deux permutations de 12 … n, qu’on identifie aux mots π = π(1)π(2) … π(n) et ρ = ρ(1)ρ(2) … ρ(n). Le nombre de descentes en commun de π et ρ, noté ddes(π, ρ), est défini comme le nombre d’indices k tels que 1 ≤ k ≤ n − 1 et π(k) > π(k + 1), ρ(k) > ρ(k + 1). Le résultat principal de Carlitz [Ca76] affirme que

ω(n, k) est précisément égal au nombre de couples (π, ρ) de permutations d’ordre n tels que ddes(π, ρ) = k.

Les premières valeurs des ω(n, k) sont consignés dans le tableau 4.

k =  0  1  2  3  4
n = 1  1
2  3  1
3  19  16  1
4  211 299 65  1
5  3651 7346 3156 246 1

Tableau 4 (distribution de ddes sur S_{n} × S_{n})

Toujours dans l’article précité, les auteurs avaient noté la ressemblance de la formule (1.11) avec la formule (1.3) donnant la fonction génératrice des polynômes Eulériens A_{n}(t). Comme A_{n}(t) est un polynôme générateur du groupe symétrique S_{n} (et non plus de S_{n} × S_{n}), l’idée avait germé que la fonction de Bessel était pour les paires de permutations ce qu’était la fonction exponentielle pour les permutations.

Les travaux ultérieurs ont confirmé cette idée, puisqu’on a su, d’une part, poursuivre l’étude des polynômes Eulériens dans l’algèbre des qséries, où l’on a cherché et obtenu des q-analogues des différentes formules les concernant (voir, par exemple [Ca54], [Ca59], [Ca71]), d’autre part, prolonger l’étude des p, q-analogues des fonctions de Bessel, d’abord analytiquement (voir Ismail [Is82]), ensuite combinatoirement, en particulier par l’école bordelaise (voir [DeFe93], [Fe95]) pour des comptages de diagrammes de Ferrers gauches et de polyominos et en termes de paires de permutations par Stanley [Sta76], Fedou et Rawlings [FeRa94], [FeRa95].

1.5. Fonctions de Bessel basiques. Le q-analogue de la formule (1.2), à savoir (1.5), pouvant donc être interprété combinatoirement comme indiqué, il est naturel, comme l’avaient fait Carlitz, Stanley, Fedou et Rawlings (op. cit.) pour (1.3), d’étudier le développement de (1.5), lorsqu’on remplace cette fois les exponentielles par des analogues de fonctions de Bessel. Autrement dit, il importe d’étudier dans l’algèbre des séries à une ou plusieurs bases le développement de

(1.12)  \frac{(1 − t) J((1 − t)X; Q, q)}{−t + J((1 − t)X; Q, q) J((1 − t)Y; Q, q)},

où J est une fonction de Bessel basique définie ci-après.

Soient L et l deux entiers positifs fixés et Q = (Q_{1}, Q_{2}, …, Q_{L}), q = (q_{1}, q_{2}, …, q_{l}) deux suites de variables. Posons

Q^{\binom{n}{2}} = Q\binom{n}{2}_{1} … Q\binom{n}{2}_{L},
(Q; Q)_{n} = (Q_{1}; Q_{1})_{n} … (Q_{L}; Q_{L})_{n},
(q; q)_{n} = (q_{1}, q_{1})_{n} … (q_{l}; q_{l})_{n}.

Utilisant la notation “H” pour le produit d’Hadamard de deux séries, à savoir

(∑_{n≥0} α_{n}u^{n}) H(∑_{n≥0} β_{n}u^{n}) = ∑_{n≥0}(α_{n}β_{n})u^{n},

on définit la fonction de Bessel à plusieurs bases par

(1.13) J(u; Q, q) = (∑_{n≥0}(−u)^{n}) H E_{Q_{1}}(u) H E_{Q_{2}}(u) H ⋯

H e_{q_{1}}(u) H e_{q_{2}}(u) H ⋯

On a encore

(1.14) J(u; Q, q) = ∑_{n≥0}(−1)^{n} \frac{Q^{\binom{n}{2}}}{(Q, Q)_{n}} \frac{1}{(q; q)_{n}} u^{n}.

Si L = l = 1, on a

J(u; Q, q) = ∑_{n≥0}(−1)^{n} \frac{Q^{\binom{n}{2}}}{(Q, Q)_{n}} \frac{1}{(q; q)_{n}} u^{n}.

Enfin, pour L = 0 et l = 1, on retrouve la q-exponentielle

J(u; -, q) = ∑_{n≥0}(−1)^{n} \frac{1}{(q; q)_{n}} u^{n} = e_{q}(−u),

et pour L = 1 et l = 0, la Q-exponentielle

J(u; Q, -) = ∑_{n≥0}(−1)^{n} \frac{Q^{\binom{n}{2}}}{(Q, Q)_{n}} u^{n} = E_{Q}(−u).

Comme expliqué dans le prochain paragraphe, le développement en série en base Q et q de l’expression (1.12) fait apparaître des polynômes qui sont les fonctions génératrices d’objets combinatoires, appelés multipermutations signées, par une suite de statistiques dont l’une des composantes est le nombre de descentes qui généralise au cas de B_{n} le nombre de descentes communes introduite par Carlitz.

1.6. Multipermutations signées. On appelle multipermutation signée, d’ordre n, un triplet (\underline{Σ}, \underline{σ}, ε), où \underline{Σ} = (Σ_{1}, …, Σ_{L}) et \underline{σ} = (σ_{1}, …, σ_{l}) sont, respectivement, deux suites de L et l permutations d’ordre n et où ε est un mot-xy de longueur n.

Définition 2. On dit que l’entier i est une descente de la multipermutation signée (\underline{Σ}, \underline{σ}, ε), si l’une des quatre conditions suivantes est remplie:

(i) i = n et ε(n) = x; (ii) 1 ≤ i ≤ n − 1, ε(i) = x, ε(i + 1) = y; (iii) 1 ≤ i ≤ n − 1, ε(i) = ε(i + 1) et Σ_{1}(i) > Σ_{1}(i + 1), …, Σ_{L}(i) >

Σ_{L}(i + 1), ainsi que σ_{1}(i) > σ_{1}(i + 1), …, σ_{l}(i) > σ_{l}(i + 1); On note ddes(\underline{Σ}, \underline{σ}, ε) le nombre de descentes de (\underline{Σ}, \underline{σ}, ε). On pose

Q^{inv(\underline{Σ},ε)} = Q_{1}^{inv(Σ_{1},ε)} ⋯ Q_{L}^{inv(Σ_{r},ε)} ;
q^{coinv(\underline{σ},ε)} = q_{1}^{coinv(σ_{1},ε)} ⋯ q_{l}^{coinv(σ_{l},ε)}.

Le principal objet de ce premier article est de démontrer le résultat suivant.

Théorème 1.1. On a l’identité

(1.15) \frac{(1 − t) J((1 − t)X; Q, q)}{−t + J((1 − t)X; Q, q) J((1 − t)Y; Q, q)}

= ∑_{n≥0} \frac{1}{(Q; Q)_{n}(q; q)_{n}} W_{n}(X, Y, t, Q, q),

où X et Y sont deux variables et où le coefficient W_{n}(X, Y, t, Q, q) est le polynôme générateur des multipermutations signées (\underline{Σ}, \underline{σ}, ε) par les statistiques “ddes,” “inv” et “coinv.” En d’autres termes, on a

(1.13) W_{n}(X, Y, t, Q, q)

= ∑_{(\underline{Σ},\underline{σ},ε)} X^{ℓ(ε|x)}Y^{ℓ(ε|y)}t^{ddes(\underline{Σ},\underline{σ},ε)}Q^{inv(\underline{Σ},ε)}q^{coinv(\underline{σ},ε)},

la sommation étant faite sur toutes les multipermutations signées de longueur n.

La liste des premières valeurs des polynômes W_{n}(X, Y, t, Q, q) (pour L = l = 1) est donnée dans le tableau 5.

W_{1} = Y + tX;
W_{2} = Y^{2}(Qq + q + tQ + 1) + XY (2 t(Q + 1)(q + 1)) + X^{2}t(Qq + q + tQ + 1);
W_{3} = c_{0}Y^{3} + c_{1}XY^{2} + c_{2}X^{2}Y + c_{3}X^{3},  où
c_{0} = 2 Qq + 2 Q^{2}q + 2 q + 2 Q^{3}tq + 2 Q^{3}tq^{2} + 2 Q^{2}q^{3} + 2 q^{2}
+ q^{3} + 1 + 2 Qq^{3} + 2 tQq + 2 tQ^{2}q + 2 q^{2}tQ + 2 q^{2}tQ^{2}
+ 2 Qq^{2} + Q^{3}t^{2} + 2 tQ + 2 tQ^{2} + 2 Q^{2}q^{2} + Q^{3}q^{3}
c_{1} = t(1 + Q + Q^{2})(q^{2} + q + 1)(3 Qq + 3 q + 2 tQ + Q + 3)
c_{2} = t(1 + Q + Q^{2})(q^{2} + q + 1)(2 Qq + tQq + 2 q + tq + 3 tQ + 2 + t)
c_{3} = t c_{0}.

Tableau 5 (distribution de (ddes, inv, coinv))

Si dans le précédent tableau on fait q = 0, on retrouve le tableau 2. D’autre part, en ne retenant que les coefficients des plus hautes puissances de Q, on retrouve le tableau 1. Par ailleurs, on voit apparaître dans ces premières valeurs les polynômes gaussiens \left[{n \atop α}\right]_{Q} et \left[{n \atop α}\right]_{q} (0 ≤ α ≤ n). En effet, on démontrera, dans le prochain paragraphe, qu’on peut écrire

W_{n}(X, Y, t, Q, q) = ∑_{0≤α≤n} X^{α}Y^{n−α}\left[{n \atop α}\right]_{Q} \left[{n \atop α}\right]_{q} W_{α,n−α},

où W_{α,n−α} est un polynôme générateur d’une sous-classe de multipermutations signées, dites compatibles.

Pour démontrer le théorème 1.1, nous proposons une méthode itérative. Elle est développée dans le paragraphe 3. Nous concluons l’article par une démonstration de la formule de Reiner, utilisant toujours cette méthode itérative.

Notons que l’identité (1.15) avec les interprétations combinatoires énoncées dans le Théorème 1.1 se spécialise en plusieurs identités établies précédemment par différents auteurs. Avec X = 0, on retrouve les résultats sur A_{n} établis par Carlitz, Stanley. Pour L = 0, l = 1 on déduit (1.5) avec son interprétation combinatoire en termes de nombres de descentes et de coinversions.

Dans le second article, nous proposerons une extension de notre Théorème 1.1 à l’aide des analogues finis des fonctions de Bessel basiques en utilisant une approche différente. Nous obtiendrons d’autres interprétations combinatoires pour les polynômes générateurs des permutations signées.

2. Multipermutations signées compatibles

Introduisons tout d’abord la notion de multipermutation signée compatible. Soit (σ, ε) une permutation signée, où σ ∈ S_{n} et où ε = ε(1) … ε(n) est un mot-xy. On rappelle que le mot σ_{ε|x} (resp. σ_{ε|y}) est défini comme le sous-mot de σ(1) … σ(n) tel que ε(i) = x (resp. ε(i) = y). On peut introduire le nombre d’inversions “inv(σ_{ε|y}, σ_{ε|x})” entre les mots σ_{ε|y} et σ_{ε|x}, en posant

inv(σ_{ε|y}, σ_{ε|x}) = #{(i, j) : ε(i) = y, ε(j) = x, σ(i) > σ(j)}.

On voit alors qu’une autre façon de définir les statistiques “inv” et “coinv” est de poser:

inv(σ, ε) = inv σ_{ε|x} + inv σ_{ε|y} + inv(σ_{ε|y}, σ_{ε|x}) ;
coinv(σ, ε) = coinv σ_{ε|x} + coinv σ_{ε|x} + inv(σ_{ε|y}, σ_{ε|x}).

Définition. Supposons que ε a α lettres égales à x et β lettres égales à y (α + β = n). On dit que la permutation σ est compatible avec ε (ou encore que la permutation signée (σ, ε) est compatible), si

inv(σ_{ε|y}, σ_{ε|x}) = 0,

ou, de façon équivalente, si le sous-mot σ_{ε|y} est un réarrangement du mot 12 … β (et donc σ_{ε|x} est un réarrangement de (β + 1)(β + 2) … n).

Une multipermutations signée (\underline{Σ}, \underline{σ}, ε), telle que \underline{Σ} = (Σ_{1}, …, Σ_{L}) et \underline{σ} = (σ_{1}, …, σ_{l}) est dite compatible, si les permutations Σ_{1}, …, Σ_{L}, σ_{1}, …, σ_{l} sont toutes compatibles avec ε.

Le polynôme

W_{n}(X, Y, t, Q, q) = ∑_{(\underline{Σ},\underline{σ},ε)} X^{ℓ(ε|x)}Y^{ℓ(ε|y)}t^{ddes(\underline{Σ},\underline{σ},ε)}Q^{inv(\underline{Σ},ε)}q^{coinv(\underline{σ},ε)},

où la somme est sur toutes les multipermutations signées (\underline{Σ}, \underline{σ}, ε) de longueur n, est un polynôme homogène de degré n en X et Y. On peut donc écrire:

(2.1)  W_{n}(X, Y, t, Q, q) = ∑_{α+β=n} \left[{n \atop α}\right]_{Q} \left[{n \atop α}\right]_{q}X^{α} Y^{β} W_{α,β}

Proposition 2.1. Le polynôme W_{α,β} apparaissant dans (2.1) est le polynôme générateur des multipermutations signées (\underline{Σ}, \underline{σ}, ε) compatibles, telles que ε contient exactement α lettres égales à x et β lettres égales à y, par la suite de statistiques (ddes, inv, coinv).

Démonstration. Pour ne pas alourdir les notations, supposons L = l = 1. Soit (Σ, σ, ε) une bipermutation signée de longueur n telle que ℓ(ε|x) = α. Notons I l’ensemble des α lettres du mot σ_{ε|x}. Il existe une et une seule bijection croissante f_{Σ} (resp. f_{σ}) envoyant l’image Σ(I) de l’ensemble I par Σ (resp. σ(I)) sur l’intervalle [n−α+1, n] et le complémentaire Σ([ n]\ I) (resp. σ([n] \ I)) sur l’intervalle [1, n − α]. Le triplet (f_{Σ} ∘ Σ, f_{σ} ∘ σ, ε) est alors une permutation signée compatible. L’application (Σ, σ, ε) ↦ (f_{Σ} ∘ Σ, f_{σ} ∘ σ, ε) est surjective. De plus, si (Σ_{0}, σ_{0}, ε) est compatible, le nombre d’antécédents (Σ, σ, ε) envoyés sur (Σ_{0}, σ_{0}, ε) par cette surjection est égal à \binom{n}{α}\binom{n}{α}.

Si (Σ_{0}, σ_{0}, ε) est compatible et si (f_{Σ} ∘ Σ, f_{σ} ∘ σ, ε) = (Σ_{0}, σ_{0}, ε), alors

ddes (Σ, σ, ε) = ddes (Σ_{0}, σ_{0}, ε);
inv (σ, ε) = inv (σ_{0}, ε) + inv(σ_{ε|y}, σ_{ε|x});
coinv (σ, ε) = coinv (σ_{0}, ε) + inv(σ_{ε|y}, σ_{ε|x}).

Ces propriétés résultent du fait que f_{Σ} et f_{σ} sont des applications croissantes.

Il en résulte que la somme

∑_{(Σ,σ,ε)} Q^{inv(Σ,ε)} q^{coinv(σ,ε)},

étendue à tous les triplets (Σ, σ, ε) tels que (f_{Σ} ∘ Σ, f_{σ} ∘ σ, ε) = (Σ_{0}, σ_{0}, ε), est égale à

Q^{inv(Σ_{0},ε)} q^{coinv(σ_{0},ε)} ∑_{(Σ,σ,ε)} Q^{inv(Σ_{ε|y},Σ_{ε|x})} q^{inv(σ_{ε|y},σ_{ε|x})},

ou encore à

Q^{inv(Σ_{0},ε)} q^{coinv(σ_{0},ε)}\left[{n \atop α}\right]_{Q} \left[{n \atop α}\right]_{q}.

De là W_{n}(X, Y, t, Q, q)

= ∑_{α+β=n} X^{α}Y^{β} ∑_{{(Σ_{0},σ_{0},ε) (comp.) \atop ℓ(ε|x)=α}} t^{ddes(Σ_{0},σ_{0},ε)} ∑_{{(Σ,σ,ε) \atop (f_{Σ}∘Σ,f_{σ}∘σ,ε)=(Σ_{0},σ_{0},ε)}} Q^{inv(Σ,ε)}q^{coinv(σ,ε)}

= ∑_{0≤α≤n} X^{α}Y^{n−α}\left[{n \atop α}\right]_{Q} \left[{n \atop α}\right]_{q}W_{α,β}.

3. La méthode itérative

Posons (Q; Q)_{n} = (Q)_{n} et (q; q)_{n} = (q_{n}) et pour ne pas alourdir les notations, supposons L = l = 1. L’identité (1.15) peut se récrire

(1 − ∑_{i+j≥1} \frac{(t − 1)^{i+j−1}Q^{\binom{i}{2}+\binom{j}{2}}X^{i}Y^{j}}{(Q)_{i} (q)_{i} (Q)_{j} (q)_{j}} )^{−1}J((1 − t)X; Q, q)

= ∑_{k≥0} \frac{1}{(Q)_{k} (q)_{k}} W_{k}(X, Y, t, Q, q),

une identité de la forme (1 − R)^{−1}S = T, qui, lorsque l’on la récrit S = (1 − R)T, montre que (1.15) est équivalente à la formule de récurrence

(3.1) W_{n}(X, Y, t, Q, q) = Q^{\binom{n}{2}}(t − 1)^{n}X^{n}

+ ∑_{{i+j+k=n, \atop i+j≥1}} \left[{n \atop i, j, k}\right]_{Q} \left[{n \atop i, j, k}\right]_{q}(t − 1)^{i+j−1}Q^{\binom{i}{2}+\binom{j}{2}}X^{i}Y^{j} W_{k}(X, Y, t, Q, q),

avec n ≥ 1 et W_{0}(X, Y, t, Q, q) = 1.

Maintenant utilisant la décomposition (2.1) et déterminant le coefficient de X^{α}Y^{β} dans les deux membres de (3.1), on voit que la précédente formule de récurrence est encore équivalente à l’ensemble des deux formules

(3.2) W_{n,0} = Q^{\binom{n}{2}}(t − 1)^{n} + ∑_{1≤i≤n} \left[{n \atop i}\right]_{Q} \left[{n \atop i}\right]_{q} (t − 1)^{i−1} Q^{\binom{i}{2}} W_{n−i,0};

(3.3) W_{α,β} = ∑_{{0≤i≤α \atop 0≤j≤β} ; i+j≥1} \left[{α \atop i}\right]_{Q} \left[{α \atop i}\right]_{q} \left[{β \atop j}\right]_{Q} \left[{β \atop j}\right]_{q} (t − 1)^{i+j−1} Q^{\binom{i}{2}+\binom{j}{2}} W_{α−i,β−j};

avec n ≥ 1, α + β ≥ 1 et W_{0,0} = 1.

Pour démontrer (1.15), il suffit, partant de la définition du polynôme W_{n}(X, Y, t, Q, q) comme fonction génératrice des bipermutations signées de longueur n d’établir (3.1), ou bien partant de la définition de W_{α,β} comme polynôme générateur des bipermutations signées compatibles (Σ, σ, ε) telles que ε contient α lettres x et β lettres y, établir (3.2) et (3.3). Les deux façons reposent sur la même identité que nous allons établir maintenant.

Notons d’abord que si (Σ, σ, ε) est une bipermutation signée telle que ε contient α lettres x et β lettres y, chaque permutation signée (Σ, ε), (σ, ε) est une permutation des bilettres (1, y) … (β, y)(1 + β, x) … (α + β, x). Par conséquent, le facteur gauche (Σ(1), σ(1), ε(1)) … (Σ(k), σ(k), ε(k)) (1 ≤ k ≤ α + β) de (Σ, σ, ε) est décroissant, si l’on a Σ(1) > ⋯ > Σ(k) et σ(1) > ⋯ > σ(k). Toute bipermutation signée compatible (b.s.c.) a un plus long facteur gauche décroissant (p.l.f.g.d.), de longueur au moins égale à 1. Une lettre (Σ(i), σ(i), ε(i)) de la bipermutation signée (Σ, σ, ε) est dite grande (resp. petite), si ε(i) = x (resp. ε(i) = y).

Dans la suite de la démonstration, les b.s.c. sont supposées avoir α grandes lettres et β petites lettres. On note F (i, j) la fonction génératrice de ces b.s.c., dont le p.l.f.g.d. est de longueur (i + j) et débute par i grandes lettres suivies de j petites lettres (0 ≤ i ≤ α, 0 ≤ j ≤ β, i + j ≥ 1). On désigne par G(≥ i, ≥ 0, ≥ k) (resp. G(= i, ≥ j, ≥ k)) la fonction génératrice de ces b.s.c. dont le p.l.f.g.d. est de longueur au moins égale à k et débute par au moins i grandes lettres (resp. et débute par i grandes lettres suivies par au moins j petites lettres). Posons

u_{i,j} = \left[{α \atop i}\right]_{Q} \left[{α \atop i}\right]_{q} \left[{β \atop j}\right]_{Q} \left[{β \atop j}\right]_{q} Q^{\binom{i}{2}+\binom{j}{2}} W_{α−i,β−j},

de sorte que (3.2) et (3.3) peuvent se récrire

(3.4)  W_{α,0} = Q^{\binom{α}{2}}(t − 1)^{α} + ∑_{1≤i≤α} u_{i,0}(t − 1)^{i−1} (β = 0);
(3.5)  W_{α,β} = ∑_{{0≤i≤α \atop 0≤j≤β} ; i+j≥1} u_{i,j}(t − 1)^{i+j−1} (β ≥ 1).

Lemme 3.1. On a les identités:

(3.6) t^{i} u_{i,0} = t F (i, 0) + G(≥ i, ≥ 0, ≥ i + 1);
(3.7) t^{i+j} u_{i,j} = t F (i, j) + G(= i, ≥ j + 1, ≥ i + j + 1), si j ≥ 1.

Démonstration. En effet, le produit t^{i} u_{i,0} est la fonction génératrice des b.s.c. débutant par un facteur décroissant de i grandes lettres, avec la restriction que le nombre de descentes initial est compté i (au lieu de i−1) lorsque le p.l.f.g.d est de longueur exactement i. Rentrent donc dans cette fonction génératrice, outre les b.s.c. juste décrits, celles dont le p.l.f.g.d. contient i grandes lettres et au moins une petite lettre, plus toutes celles dont le p.l.f.g.d. contient au moins i + 1 grandes lettres et aucune petite lettre. Ceci prouve (3.6).

Lorsque j ≥ 1, le produit t^{i+j} u_{i,j} est la fonction génératrice des b.s.c. débutant par un facteur décroissant ayant i grandes lettres et au moins j petites lettres, toujours avec la restriction que le nombre de descentes initial est compté i + j (au lieu de i + j − 1) lorsque le p.l.f.g.d est de longueur i + j. En plus de ces b.s.c. on trouve dans la fonction génératrice toutes les b.s.c. dont le p.l.f.g.d. contient i grandes lettres et au moins j +1 petites lettres.

Comme F (i, 0) = G(≥ i, ≥ 0, ≥ i) − G(≥ i, ≥ 0, ≥ i + 1), on tire de (3.6) l’identité

(3.8) G(≥ i, ≥ 0, ≥ i) = t^{i−1} u_{i,0} + \frac{t − 1}{t}G(≥ i, ≥ 0, ≥ i + 1);

de même, on tire de (3.7), lorsque j ≥ 1,

(3.9) G(= i, ≥ j, ≥ i + j) = t^{i+j−1}u_{i,j} + \frac{t − 1}{t}G(= i, ≥ j + 1, ≥ i + j + 1).

On a en plus l’identité (3.10) G(≥ i, ≥ 0, ≥ i + 1) = G(= i, ≥ 1, ≥ i + 1)

+ G(≥ i + 1, ≥ 0, ≥ i + 1).

Ces trois formules permettent le calcul de W_{α,β} par itération. En effet, le polynôme W_{α,β} est égal à G(≥ 1, ≥ 0, ≥ 1) + G(= 0, ≥ 1, ≥ 1). Par itération, on obtient

(3.11) W_{α,β} = u_{1,0} + (t − 1)u_{2,0} + ⋯ + (t − 1)^{α−2}u_{α−1,0}

+ \frac{(t − 1)^{α−1}}{t^{α−1}} G(≥ α, ≥ 0, ≥ α)

+ \frac{(t − 1)^{α−1}}{t^{α−1}} G(= α − 1, ≥ 1, ≥ α)

+ ⋯ + \frac{(t − 1)}{t}G(= 1, ≥ 1, ≥ 2) + G(= 0, ≥ 1, ≥ 1).

Si β = 0, on a G(≥ α, ≥ 0, ≥ α) = G(= α, = 0, = α) = F (α, 0) = t^{α}Q^{\binom{α}{2}} et toutes les quantités de la forme G(= i, ≥ 1, ≥ i + 1) sont nulles. Puisque u_{α,0} = Q^{\binom{α}{2}}, on obtient

W_{α,0} = u_{1,0} + (t − 1)u_{2,0} + ⋯ + (t − 1)^{α−2}u_{α−1,0} + t(t − 1)^{α−1}Q^{\binom{α}{2}}
= u_{1,0} + (t − 1)u_{2,0} + ⋯ + (t − 1)^{α−2}u_{α−1,0} + (t − 1)^{α−1}u_{α,0}
+ (t − 1)^{α}Q^{\binom{α}{2}},

qui n’est autre que la formule (3.4) à démontrer.

Lorsque β ≥ 1, on peut continuer l’itération de l’expression (3.11) et du fait que G(≥ α + 1, ≥ 0, ≥ α + 1) = 0 obtenir

W_{α,β} = u_{1,0} + (t − 1)u_{2,0} + ⋯ + (t − 1)^{α−1}u_{α,0}

+ \frac{(t − 1)^{α}}{t^{α}} G(= α, ≥ 1, = α + 1)

+ ⋯ + \frac{(t − 1)}{t}G(= 1, ≥ 1, ≥ 2) + G(= 0, ≥ 1, ≥ 1).

On itère ensuite chaque expression G(= i, ≥ 1, ≥ i + 1) en faisant usage des relations G(= i, ≥ β + 1, ≥ i + β + 1) = 0 (0 ≤ i ≤ α) et l’on obtient (3.5).

Une variante de la méthode itérative consiste à établir directement la formule de récurence (3.1). Notons F_{m} la fonction génératrice de toutes les bipermutations signées de longueur n dont le p.l.f.g.d. est de longueur m et posons : G_{m} = F_{m} + F_{m+1} + ⋯ + F_{n}. Partant toujours du Lemme 3.1, on peut établir la formule itérative :

tF_{m} + G_{m+1} = W_{n−m}(X, Y, t, Q, q)t^{m}\left[{n \atop m}\right]_{Q}\left[{n \atop m}\right]_{q}

× ∑_{i+j=m} \left[{m \atop i}\right]_{Q}\left[{m \atop i}\right]_{q}Q^{\binom{i}{2}+\binom{j}{2}}X^{i}Y^{j} (n ≥ 1),

qu’on applique à G_{1} = W_{n}(X, Y, t, Q, q). On en déduit (3.1) en utilisant la formule aux bornes:

G_{n} = t^{n−1}( ∑_{i+j=n} \left[{m \atop i}\right]_{Q}\left[{m \atop i}\right]_{q}Q^{\binom{i}{2}+\binom{j}{2}}X^{i}Y^{j} + (t − 1)X^{n}Q^{\binom{n}{2}}).

Une autre méthode de démonstration des identités (3.2) et (3.2) s’appuie sur la technique des permutations “virgulées” (“commaed”) illustrée dans [Ge82], [Ze80], [FoZe91]. Nous ne reproduisons pas ici cette démonstration.

4. La fonction génératrice de Reiner

Dans ce dernier paragraphe, nous montrons comment le calcul de la fonction génératrice des permutations signées par le couple (des, l_{Cox}), dans l’expression (1.7) que lui a donnée Reiner, se ramène en fait à un calcul sur les permutations ordinaires par l’intermédiaire des polynômes générateurs

A_{n,k}(t, q) = ∑_{σ∈S_{n}} t^{des_{k} σ}q^{inv σ} (0 ≤ k ≤ n),

où pour toute permutation σ ∈ S_{n} on pose:

des_{k} σ = \{ \begin{matrix}des σ, & si σ(n) ≤ n − k; \\ 1 + des σ, & si σ(n) ≥ n − k + 1. \end{matrix}

Après quelques manipulations faciles, on montre que le polynôme générateur W′′_{n} des permutations signées par le couple (des, l_{Cox}) peut s’écrire:

(4.1)  W′′_{n} = ∑_{0≤k≤n} X^{k} q^{\binom{k+1}{2}} \left[{n \atop k}\right]_{q} A_{n,k}(t, q).

Pour prendre en charge le facteur X^{k} q^{\binom{k+1}{2}} \left[{n \atop k}\right]_{q}, il n’est donc pas étonnant que Reiner ait dû prendre des normalisations peu commodes comme (−Xq; q)_{n} (q, q)_{n}.

Ensuite le membre de gauche de (1.7), d’après le résultat de Stanley [Sta76] ou le théorème 1.1 avec les paramètres X = 0, l = 0, L = 1, peut encore s’écrire:

∑_{l≥0} \frac{u^{l}}{(q; q)_{l}} A_{l,l}(t, q) ∑_{m≥0} \frac{(u(1 − t))^{m}}{(−Xq; q)_{m} (q; q)_{m}} ,

qu’on pose égal à

∑_{n≥0} \frac{u^{n}}{(−Xq; q)_{n} (q; q)_{n}} W_{n}^{(3)}.

De nouveau, par des manipulations classiques sur les q-séries, on peut aboutir à l’expression:

W_{n}^{(3)} = ∑_{0≤k≤n} X^{k} q^{\binom{k+1}{2}} ∑_{0≤m≤n−k} \left[{n \atop m}\right] A_{n−m,n−m}(t, q)\left[{n − m \atop k}\right] q^{mk}(1 − t)^{m}.

Pour démontrer que l’on a W_{n}^{(3)} = W′′_{n} (donnée en (4.1)), on voit qu’il suffit d’établir, pour 0 ≤ k ≤ n, la formule de récurrence:

(4.2) A_{n,k}(t, q) = ∑_{0≤m≤n−k} \left[{n − k \atop m}\right]_{q} A_{n−m,n−m}(t, q) q^{mk} (1 − t)^{m}.

Cette formule peut également être démontrée par la méthode itérative illustrée dans le paragraphe précédent. Si une permutation d’ordre n se termine par un terme au plus égal à (n − k), on peut considérer son plus long facteur droit croissant (p.l.f.d.c.); il est de longueur strictement positive. Si la permutation se termine par un terme supérieur ou égal à (n − k + 1), on convient que son p.l.f.d.c. est de longueur nulle.

Pour m = 0, 1, …, n − k, désignons par F_{m} la fonction génératrice de ces permutations dont le p.l.f.d.c est de longueur m et posons G_{m} = F_{m} + ⋯ + F_{n−k}. Alors u_{m} = \left[{n−k \atop m}\right]_{q} A_{n−m,n−m}(t, q) q^{mk} est la fonction génératrice des permutations dont le p.l.f.d.c. est de longueur au moins égale à m, si l’on convient d’ajouter une descente supplémentaire lorsque le p.l.f.d.c. est de longueur supérieure ou égale à (m + 1). On a donc l’identité:

u_{m} = F_{m} + t G_{m+1};

d’où

(4.3)  G_{m} = u_{m} + (1 − t)G_{m+1}.

Comme A_{n,k}(t, q) = G_{0} et que G_{n−k} = A_{k,k}(t, q) q^{(n−k)k}, on en déduit la formule de récurrence (4.2) en itérant la formule (4.3) à partir de G_{0}.

Bibliographie

[An76] George E. Andrews. — The Theory of Partitions. — London, Addison-Wesley, 1976 (Encyclopedia of Math. and Its Appl., 2).

[Br94] Francesco Brenti. — q-Eulerian Polynomials Arising from Coxeter Groups, Europ. J. Combinatorics, vol. 15, 1994, p. 417–441.

[Ca54] L. Carlitz. — q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc., vol. 76, 1954, p. 332–350.

[Ca59] L. Carlitz. — Eulerian numbers and polynomials, Math. Magazine, vol. 33, 1959, p. 247–260.

[Ca71] L. Carlitz. — A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly, vol. 82, 1975, p. 51–54.

[Ca76] L. Carlitz, R. Scoville and T. Vaughan. — Enumeration of pairs of permutations,

Discrete Math., vol. 14, 1976, p. 215–239.

[ClFo95] Robert J. Clarke and Dominique Foata. — Eulerian Calculus, II: An Extension of Han’s Fundamental Transformation, Europ. J. Combinatorics, vol. 16, 1995, p. 221–252.

[DeFe93] M.-P. Delest and J.-M. Fedou. — Enumeration of skew Ferrers’ diagrams, Discrete

Math., vol. 112, 1993, p. 65–79.

[Er53] A. Erdélyi, ed. — Higher Transcendental Functions, vol II, (The Bateman Manuscript Project). — New York, McGraw-Hill, 1953.

[Fe95] J.-M. Fedou. — Sur les fonctions de Bessel, Discrete Math., vol. 139, 1995,

p. 473–480.

[FeRa94] J.-M. Fedou and D. Rawlings. — More Statistics on Permutations Pairs, Electronic J. Combinatorics, vol. 1, 1994, R11, 17 pp.

[FeRa95] J.-M. Fedou and D. Rawlings. — Adjacencies in words, à paraître dans Advances in Appl. Math., 1995.

[FoHa96] Dominique Foata et Guo-Niu Han. — Calcul basique des permutations signées, II: analogues finis des fonctions de Bessel, Strasbourg, 28 p., 1996.

[FoZe91] Dominique Foata and Doron Zeilberger. — Multibasic Eulerian Polynomials, Trans. Math. Soc., vol. 329, 1991, p. 843–862.

[GaRa90] George Gasper and Mizan Rahman. — Basic Hypergeometric Series. — London,

Cambridge Univ. Press, 1990 (Encyclopedia of Math. and Its Appl., 35).

[Ge82] Ira Gessel. — A q-analogue of the exponential formula, Discrete Math., vol. 40, 1982, p. 69–80.

[Is82] Mourad E.H. Ismail. — The zeros of basic Bessel functions, J. Math. Anal. and

Appl., vol. 86, 1982, p. 1–19.

[Re93a] V. Reiner. — Signed permutation statistics, Europ. J. Combinatorics, vol. 14, 1993, p. 553–567.

[Re93b] V. Reiner. — Signed permutation statistics and cycle type, Europ. J. Combinatorics, vol. 14, 1993, p. 569–579.

[Re93c] V. Reiner. — Upper binomial posets and signed permutation statistics, Europ. J. Combinatorics, vol. 14, 1993, p. 581–588.

[Re95a] V. Reiner. — Descents and one-dimensional characters for classical Weyl groups, Discrete Math., vol. 140, 1995, p. 129–140.

[Re95b] V. Reiner. — The distribution of descents and length in a Coxeter group, Elec-

tronic J. Combinatorics, vol. 2, 1995, # R25.

[St76] Richard P. Stanley. — Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, vol. 20, 1976, p. 336–356.

[Ste93] Einar Steingrímsson. — Permutation Statistics of Indexed Permutations, Europ.

J. Combinatorics, vol. 15, 1994, p. 187–205.

[Stem92] John Stembridge. — Eulerian numbers, tableaux, and the Betti numbers of a

toric variety, Discrete Math., vol. 99, 1992, p. 307–320.

[Ze80] Doron Zeilberger. — A lattice walk approach to the counting of multiset permutations, J. Math. Anal. Appl., vol. 74, 1980, p. 192–199.