Séminaire Lotharingien de Combinatoire, B08b, 1982, 6 pp. [Formerly : Publ. I.R.M.A. Strasbourg, 1984, 229/S-08 Actes 8e Séminaire Lotharingien, p. 11-16.]

UNE AUTRE INTERPRÉTATION

DU NOMBRE DE DÉRANGEMENTS

PAR

Jacques DÉSARMÉNIEN

1. Introduction. — L’énumération des dérangements (ou permutations sans points fixes) est un exercice classique de combinatoire remontant au 18e siècle (le problème des rencontres de Montmort [7]), exposé en détail par exemple par Comtet [1]. Deux articles récents de Garsia et Remmel et de Remmel [4, 9] ont renouvelé l’intérêt pour ce problème ; le premier en fournissant un modèle pour une q-extension du nombre de dérangements, le second en montrant comment ce modèle permet d’interpréter la formule de récurrence d_{n} = nd_{n−1} + (−1)^{n} pour laquelle le modèle classique des permutations sans points fixes ne fournit pas de démonstration bijective immédiate.

Nous fournissons un modèle différent de celui de Garsia et Remmel pour lequel la récurrence mentionnée est immédiate et qui présente d’autres intérêts : il est constitué de permutations de forme (up-down sequence) donnée ; on sait grâce à Foata et Schützenberger [3] que les q-dénombrements des inversions et de l’indice majeur inverse coïncident dans ce cas, et, comme nous l’avons développé dans [2], donnent naissance à des fonctions de Schur d’où dérivent à leur tour de nombreuses propriétés algébriques et arithmétiques. De plus, contrairement au modèle de Garsia et Remmel, il est susceptible d’être étendu aux permutations quelconques, prenant en charge le paramètre supplémentaire nombre de points fixes.

Finalement, comme nous a fait remarquer Knuth, il existe une similitude entre notre modèle et un problème de génération de variables aléatoires de distribution exponentielle étudié par von Neumann, dont une généralisation est décrite par Knuth [5]. Le lien entre notre modèle et le problème de von Neumann est établi au moyen d’un codage classique des permutations dû à Lehmer.

2. Le problème des dérangements. — Notons D_{n} l’ensemble des permutations de [n] sans point fixe. Il s’agit de calculer le nombre d’éléments d_{n} de D_{n}

J. DÉSARMÉNIEN

On obtient très facilement, par un argument d’inclusion-exclusion, la formule explicite suivante :

\begin{aligned}d_{n} & = n! − n(n − 1)! + \binom{n}{2}(n − 2)! − ⋯ + (−1)^{n}\binom{n}{n}0! \\ & = ∑_{0≤k≤n}(−1)^{k} \frac{n!}{k!}, \end{aligned}

à partir de laquelle on obtient le résultat asymptotique bien connu :

lim_{n→+∞} \frac{d_{n}}{n!} = \frac{1}{e}.

dont une interprétation est que la probabilité qu’une permutation choisie uniformément parmi toutes les permutations soit un dérangement est asymptotiquement égale à 1/e.

On en déduit aussi la fonction génératrice :

D(x) = ∑_{n≥0} d_{n} \frac{x^{n}}{n!} = \frac{e^{−x}}{1 − x}

ainsi que la formule de récurrence de la proposition suivante.

Proposition 1. — Le nombre de dérangements sur n lettres est donné par la récurrence :

\begin{aligned}d_{0} & = 1, \\ d_{n} & = nd_{n−1} + (−1)^{n} (n ≥ 1). \end{aligned}

Il semble curieux qu’une formule de récurrence aussi simple ne puisse être interprétée de façon directe à partir de la définition des dérangements.

2. Le modèle. — Garsia et Remmel [4] étudient une classe de permutations, dont ils montrent qu’elles sont en bijection avec les dérangements et dont Remmel [9] a montré que leur nombre satisfaisait la récurrence de la proposition 1 par des méthodes purement bijectives. Néanmoins, la classe de permutations ainsi mise en évidence est caractérisée par leur bijection avec les dérangements.

Le modèle que nous proposons, qui est différent de celui de Garsia et Remmel, peut être en revanche défini a priori.

Soit σ = σ(1)σ(2) … σ(n) une permutation. On appelle creux de σ un entier i, 1 ≤ i ≤ n tel que

σ(i − 1) > σ(i) < σ(i + 1).

INTERPRÉTATION DU NOMBRE DE DÉRANGEMENTS

(Par convention, on convient que σ(0) = σ(n + 1) = +∞ .)

On note alors K_{n} l’ensemble des permutations de [n] dont le plus petit creux (que nous appellerons premier creux) est pair.

Définissons maintenant une application f de D_{n} sur l’ensemble S_{n} de toutes les permutations. Pour cela, partons d’un dérangement δ, que nous décomposons en produit de cycles. Ces cycles sont écrits par ordre décroissant de leur plus petit élément ; ce plus petit élément est placé dans chaque cycle en seconde position. (On remarque que ceci est possible, puisque δ n’a aucun cycle de longueur 1.) La permutation f(δ) est obtenue en enlevant les parenthèses dans ce dernier mot.

Exemple. — Partons du dérangement :

δ = 974382651

dont la décomposition en cycles est :

(19)(276)(34)(58).

Après réordonnement des cycles, on obtient :

(85)(43)(627)(91)

Par conséquent,

f(δ) = 854362791.

Proposition 2. — L’application f est une bijection de D_{n} sur K_{n}. On remarque tout d’abord qu’un creux de f(δ) correspond nécessaire-

ment au plus petit élément d’un cycle de δ. Réciproquement, au plus petit élément d’un cycle de δ correspond un creux de f(δ) sauf s’il se trouve dans un cycle de longueur 2 et est plus petit que le premier élément du cyle suivant après réordonnement.

Il s’ensuit que les cycles de δ qui précèdent l’élément correspondant au premier creux de f(δ) sont de longueur 2. Par conséquent, le premier creux de f(δ) est pair.

Pour voir que f est une bijection, il suffit de vérifier que l’application g définie ci-après est l’inverse de f, ce qui ne pose pas de difficultés particulières.

Pour définir g, on part d’un élément τ de K_{n}. On lit τ de droite à gauche jusqu’à lire 1. Le cycle de g(τ) auquel 1 appartient est constitué de l’élément à gauche de 1, de 1 et de tous les éléments suivant 1 à droite de celui-ci, dans cet ordre. On répète cette opération sur ce qui reste de τ après qu’on en a enlevé le cycle précédemment détecté, en remplaçant 1 par le plus petit élément restant. On remarque ici que le fait que le premier creux de τ soit pair assure que ce plus petit élément ne se trouve jamais en première position.

Si on note k_{n} le nombre d’éléments de K_{n}, on sait maintenant que l’on a k_{n} = d_{n}. On va alors interpréter bijectivement la récurrence de la proposition 1 écrite pour les entiers k_{n}.

Interprétation de la proposition 1. — Partons d’une permutation τ = τ(1)τ(2) … τ(n) dans K_{n}. On lui associe la permutation φ(τ) dans S_{n−1} par :

φ(τ)(k) = \{ \begin{matrix}τ(k) & si τ(k) < τ(n), \\ τ(k) − 1 & si τ(k) > τ(n), \end{matrix}

où 1 ≤ k ≤ n − 1.

On remarque que, en général, le premier creux de τ reste le premier creux de φ(τ). Le seul cas où il n’en est pas ainsi est lorsque n est pair et τ = n n − 1 … 2 1. Dans ce cas, le premier creux de φ(τ) vaut n − 1 qui est impair. Dans tous les autres cas, φ(τ) est dans K_{n}.

L’application ψ qui à τ ∈ K_{n} associe le couple (φ(τ), τ(n)) envoie donc K_{n} dans K_{n−1} ×[n] si n est impair et dans K_{n−1} ×[n]∪{((n−1 … 2 1), 1)} si n est pair.

Réciproquement, partant d’un couple dans K_{n−1} × [n], on peut reconstruire l’unique permutation τ auquel il correspond par ψ, sauf lorsque n est impair et qu’on part du couple ((n − 1 … 2 1), 1) qui devrait provenir de τ = n n − 1 … 2 1 lequel a son premier creux en n qui est ici impair.

On a donc établi que ψ est une bijection entre un ensemble de k_{n} éléments et un ensemble de nk_{n−1} + 1 (resp. de nk_{n−1} − 1) éléments si n est pair (resp. si n est impair).

Ceci établit l’interprétation combinatoire annoncée de la proposition 1.

3. Le codage de Lehmer et le problème de von Neumann. Von Neumann a indiqué dans une courte note [8] une méthode pour obtenir une variable aléatoire de loi exponentielle à partir d’une variable aléatoire de loi uniforme sur l’intervalle [0, 1]. Cette méthode a été généralisée et est exposée par exemple par Knuth [5]. À l’origine, cette méthode s’applique à des variables aléatoires réelles. Nous allons en présenter une version discrète.

Soit une suite T = (T_{i})_{i≥1} de variables aléatoires indépendantes telles que T_{i} soit équirépartie sur l’ensemble [i] des entiers entre 1 et i. Soit k(T) le plus petit entier tel que T_{i} ≠ 1.

Proposition 3. — La probabilité que k(T) soit impair est égale à 1/e.

En effet, la probabilité :

\begin{aligned}P (k(T) = n) & = 1 × \frac{1}{2} × ⋯ × \frac{1}{n − 1} × \frac{n − 1}{n}, \\ & = \frac{1}{(n − 1)!} − \frac{1}{n!}. \end{aligned}

La probabilité que k(n) soit impair est donc :

∑_{i≥0} (\frac{1}{(2i)!} − \frac{1}{(2i + 1)!}) = \frac{1}{e}.

Le lien entre ce résultat et notre ensemble K_{n} est obtenu au moyen d’un codage de Lehmer. Celui-ci a introduit un tel codage précisément pour produire une permutation aléatoire équirépartie sur S_{n}.

Soit donc σ ∈ S_{n} On note :

L σ(i) = card{j : 1 ≤ j ≤ i, σ(j) ≤ σ(i)}, 1 ≤ i ≤ n.

Le mot L σ = L σ(1) L σ(2) … L σ(n) est le codage de Lehmer de σ. On constate sans peine qu’il s’agit bien là d’une bijection de S_{n} sur l’ensemble des suites d’entiers de longueur n dont le i-ème élément est compris entre 1 et i.

Exemple. — Partons de la permutation :

τ = 854362791.

Son codage de Lehmer est :

L τ = 111141681.

La proposition suivante est immédiate, et fait le lien entre K_{n} et le problème de von Neumann.

Proposition 4. — Les permutations dans K_{n} sont exactement celles dont le codage de Lehmer commence par un nombre pair de 1.

Une des applications possibles de notre modèle est d’obtenir par l’intermédiaire de son codage de Lehmer un élément aléatoire équiréparti de K_{n} et, par notre application inverse de f, un dérangement aléatoire équiréparti dans D_{n}.

BIBLIOGRAPHIE

[1] Comtet (L.). — Advanced combinatorics. — D. Reidel, Dordrecht, 1974.

[2] Désarménien (J.). — Fonctions de Schur associées à des suites classiques de nombres, Ann. Scient. École Normale Supérieure, vol. 16, 1983, p. 271-304.

[3] Foata (D.) et Schützenberger (M.-P.). — Major index and inversion number of permutations, Math. Nachr., vol. 83, 1978, p. 143-159.

[4] Garsia (A. M.) et Remmel (J.). — A combinatorial interpretation of qderangements and q-Laguerre numbers, Europ. J. Combinatorics, vol. 1, 1980, p. 47-59.

[5] Knuth (D. E.). — The art of computer programming, vol. 2 : Seminumerical algorithms. — 2e éd., Addison-Wesley, Reading, Mass., 1981.

[6] Lehmer (D. H.). — The machine tools of combinatorics, Applied combinatorial mathematics [E. F. Beckenbach, éd.], p. 5-31. — J. Wiley and Sons, New York, 1964, Univ. of California Engeneering and Physical Sciences Extension Series.

[7] Montmort (P.-R.). — Essai d’analyse sur les jeux de hazard. — Paris, 1708.

[8] von Neumann (J.). — Various techniques used in connection with random digits, J. Res. Nat. Bur. Stand. Appl. Math. Series, vol. 3, 1951, p. 36-38 (=Collected works, [A. H. Taub, éd.], vol. 5, p. 768-770).

[9] Remmel (J.). — A note on a recursion for the number of derangements, Europ. J. Combinatorics, vol. 4, 1983, p. 371-374.

Jacques DÉSARMÉNIEN, Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France.