DISTRIBUTION DE L’INDICE MAJEUR RÉDUIT SUR LES DÉRANGEMENTS

Jacques DÉSARMÉNIEN*

Introduction

Le nombre de dérangements de n objets, noté d_{n} satisfait la relation de récurrence très simple :

(∗)  d_{n} = nd_{n−1} + (−1)^{n}.

Assez curieusement, il n’existe pas de démonstration bijective à proprement parler immédiate de cette formule.

Nous avons montré dans [D1] comment un modèle distinct de celui des dérangements et en bijection avec celui-ci permet d’interpréter simplement cette récurrence. Ce travail a été amplifié dans [D–W1, D–W2] et placé dans le contexte des fonctions symétriques. Il est possible également d’en déduire des formules explicites pour les q-dérangements, formules obtenues aussi directement par Michelle Wachs [W].

Dans un article récent [D2], nous nous sommes intéressé à la réduction modulo n des statistiques mahoniennes. Nous allons montrer ici comment la notion d’indice majeur réduit permet d’interpréter directement la formule (∗).

1. Les q-dérangements

Étant donnée une permutation σ de [1, n], considérée comme un mot de longueur n, l’ensemble des descentes de σ est l’ensemble des indices i, 1 ≤ i ≤ n − 1 tels que σ_{i} ≥ σ_{i+1}. L’indice majeur de σ, noté maj σ est la somme des éléments de cet ensemble.

Soit D_{n} l’ensemble des dérangements (ou permutations sans point fixe) de [1, n]. On peut évaluer la fonction génératrice d_{n}(q) = ∑_{σ∈D_{n}} q^{maj σ} de l’indice majeur sur D_{n}. Ce polynôme est appelé q-dérangement. Si l’on note [n] = 1 + q + q^{2} + ⋯ + q^{n−1} et [n]! = [1][2] … [n], on a la formule suivante, énoncée par Ira Gessel et démontrée combinatoirement par Michelle Wachs. C’est le q-analogue de la formule classique donnant le nombre de dérangements.

* Avec le soutien du P.R.C. Math.–Info.

Proposition 1.1. — La fonction génératrice de l’indice majeur sur l’ensemble des dérangements de [1, n] vaut :

d_{n}(q) = [n]! ∑_{0≤k≤n} \frac{(−1)^{k}}{[k]!} q^{k(k−1)/2}.

Cette proposition peut aussi se déduire des formules données dans [D–W1] pour les fonctions symétriques associées aux dérangements en spécialisant les indéterminées en les puissances successives de q.

À partir de la proposition précédente, on vérifie sans peine que les qdérangements satisfont la récurrence suivante.

Proposition 1.2. — Les q-dérangements sont donnés par la récurrence :

\begin{aligned}(i) & : d_{0}(q) = 1 ; \\ (ii) & : d_{n}(q) = [n]d_{n−1}(q) + (−1)^{n}q^{n(n−1)/2}. \end{aligned}

La récurrence (∗) s’obtient bien en faisant q = 1 dans la proposition précédente.

2. L’indice majeur réduit

Dans [D2], nous avons introduit la notion suivante : lorsque σ est une permutation de [1, n], on appelle indice majeur réduit de σ, qu’on note maj∗ σ le reste de l’indice majeur de σ modulo n. De la sorte, la fonction génératrice de maj∗ sur un ensemble de permutations est le reste modulo 1 − q^{n} de la fonction génératrice de maj sur le même ensemble.

En particulier, dans le cas des dérangements, si l’on note d_{n}^{k} le nombre de dérangements de [1, n] dont l’indice majeur réduit vaut k, (0 ≤ k ≤ n − 1), le polynôme d_{n}^{∗}(q) = ∑_{0≤k≤n−1} d_{n}^{k}q^{k} est le reste de d_{n}(q) modulo 1 − q^{n}.

On vérifie immédiatement le lemme suivant.

Lemme 2.1. — Si P (q) est un polynôme, on a la congruence :

P (q)[n] ≡ P (1)[n] (mod 1 − q^{n}).

On peut alors réduire modulo 1 − q^{n} la récurrence de la proposition 1.2 :

d_{n}^{∗}(q) = [n]d_{n−1}(1) + \{ \begin{matrix}q^{n/2}, & si n est pair, \\ −1, & si n est impair, \end{matrix}

compte-tenu du reste de q^{n(n−1)/2} modulo 1 − q^{n}.

Les coefficients de d_{n}^{∗}(q) sont donc tous égaux, sauf celui de q^{n/2} si n est pair et le terme constant si n est impair. Puisque d_{n−1}(1) = d_{n−1}, nombre de dérangements, il s’ensuit qu’on a partitionné l’ensemble D_{n} en n parts, chacune de cardinal d_{n−1} sauf une qui vaut alternativement d_{n−1} + 1 et d_{n−1} − 1.

L’interprétation de la récurrence (∗) est ainsi accomplie par le résultat suivant.

Proposition 2.2. — Le nombre d_{n}^{k} de dérangements de [1, n] dont l’indice majeur est congru à k modulo n vaut d_{n−1} sauf

(i) : lorsque n est pair et k = n/2 auquel cas d_{n}^{n/2} = d_{n−1} + 1,
(ii) : lorsque n est impair et k = 0 auquel cas d_{n}^{0} = d_{n−1} − 1.

Il serait évidemment intéressant de démontrer directement et bijectivement la proposition précédente. On obtiendrait ainsi une démonstration et non plus seulement une interprétation de la récurrence (∗).

RÉFÉRENCES BIBLIOGRAPHIQUES

[D1] D^{}ÉSARM^{}ÉNIEN (J.). — Une autre interprétation du nombre de dérangements, Séminaire Lotharingien de Combinatoire, B08a, 1983.

[D2] D^{}ÉSARM^{}ÉNIEN (J.). — Étude modulo n des statistiques mahoniennes, Séminaire

Lotharingien de Combinatoire, B22a, 1989.

[D–W1] D^{}ÉSARM^{}ÉNIEN (J.) et WACHS (M.). — Descentes sur les dérangements et mots

circulaires, Séminaire Lotharingien de combinatoire, B19a, 1988.

[D–W2] D^{}ÉSARM^{}ÉNIEN (J.) et WACHS (M.). — Derangements and necklaces, prépublica-

tion, 1989.

[W] WACHS (M.). — On q-derangement numbers, Proc. Amer. Math. Soc., t. 106, 1989, p. 273–279.

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

93160-Noisy-le-Grand.