Notions de mathématiques

Les permutations

Soit un ensemble fini X à n éléments, nous pouvons attribuer un numéro à chaque élément de cet ensemble à l’aide d’une bijection e : X → [n]. Nous nous intéressons ici au groupe de symétrie des ensembles finis, c’est à dire l’ensemble des bijections de ces ensembles sur eux mêmes. Comme il existe une bijection e pour ces ensembles finis, il n’est pas nécessaire de travailler sur l’ensemble X, nous pouvons donc nous intéresser uniquement au groupe de symétrie sur l’ensemble [n]. Nous notons Sn le groupe de symétrie de l’ensemble [n]. Les éléments qui appartiennent à Sn sont appelés des permutations de taille n. 

Représentation des permutations

Il existe de nombreuses façons de représenter une permutation, et nous allons en montrer deux. La première est l’utilisation typique issue de l’algèbre sur les permutations. Comme les permutations appartiennent à un groupe fini, il est possible de représenter ces dernières comme un ensemble de cycles. Un cycle dans la permutation σ ∈ Sn de représentant i ∈ [n] est défini par la séquence (i, σ(i), σ(σ(i)), . . . , σ −1 (i)). Nous pouvons donc ainsi représenter une permutation comme un ensemble de tous ses cycles. Par exemple si σ = {(1, 2),(3)}, alors nous avons la permutation σ(1) = 2, σ(2) = 1 et σ(3) = 3. Pour ce cas, nous avons un cycle de taille 1 ce qui nous donne un point fixe. La deuxième représentation provient d’un contexte que nous verrons plus souvent dans ce manuscrit. Il s’agit de représenter la permutation sous la forme d’un mot. Nous nous en servons particulièrement pour le cas du problème du tri, où cette représentation est utilisée pour encoder l’ordre dans la séquence d’entrée. Supposons que nous ayons une séquence ordonnée que nous voulons trier S = (s1, . . . , sn). Il existe alors une permutation σ ∈ Sn telle que S 0 = (sσ−1(1), . . . , sσ−1(n)) est la séquence triée des éléments de S. Pour tout i le rang de si est ainsi donné par ri = σ(i). La séquence (r1, . . . , rn) est alors une autre façon de définir σ. Nous verrons par la suite qu’il existe des algorithmes de tri qui n’utilisent que la comparaison entre les éléments pour trier une telle séquence S. Pour ces algorithmes, il n’y a alors aucune différence, en terme de coût, à trier S ou à trier la séquence (r1, . . . , rn). Nous écrivons de cette façon σ = (r1, . . . , rn) sa représentation sous forme de mot et qui définie un ordre sur la séquence S. Si nous reprenons, notre exemple précédent, nous avons que la permutation σ = (2, 1, 3) = {(1, 2)(3)}. Par la suite, nous omettrons souvent les parenthèses et les virgules, lorsqu’il n’y a aucune ambiguïté, nous aurons ainsi sur notre exemple σ = 213 = (21)(3). 

Statistiques sur les permutations

Dans ce qui suit, nous allons introduire des statistiques et des notations sur les permutations qui auront un intérêt particulier au chapitre 6 sur la génération de permutations non-uniformes. Cycles : Nous l’avons vu précédemment, nous pouvons écrire une permutation sous la forme d’une décomposition en cycles. Il se trouve que le nombre de cycles est une statistique d’intérêt et est même à la base de la distribution d’Ewens qui sera étudiée au chapitre 6. Nous dénotons par cyc(σ) le nombre de cycles d’une permutation σ ∈ Sn. Nous dénotons de plus par cyc≥k (σ) le nombre de cycles dont la taille est supérieure ou égale à k. Finalement nous utilisons cyck (σ) pour le nombre de cycles dont la taille est égale à k. En particulier cyc1 (σ) compte le nombre de points fixes de σ. Records : Les records sont de deux types possibles. Un min-record est un élément i d’une permutation σ tel que dans sa représentation en mot σ(i) est plus petit que tout élément qui le précède, soit ∀j ∈ [i − 1] on a σ(i) < σ(j). Respectivement, un max-record est défini de la même façon pour la relation >. Sur tout Sn, ces statistiques avec le nombre de cycles ont les mêmes cardinalités et nous verrons par la suite des bijections pour le prouver. Dans la permutation σ = 46527381 nous comptons 4 max-records et 3 min-records. Descentes et montées : Une permutation σ admet une descente en position i si l’on a la relation σ(i) > σ(i + 1). Respectivement, une montée en position i signifie que l’on a la relation σ(i) < σ(i + 1). Par exemple, dans la permutation σ = 46527381 nous comptons 3 montées et 4 descentes. Le nombre de montées et le nombre de descentes est une statistique bien connue en combinatoire sur les permutations. 

Relations entre les statistiques

Nous l’avons évoqué précédemment, il existe des relations entre certaines de ces statistiques, et nous allons le démontrer à l’aide de bijections. La bijection fondamentale : La première bijection que nous allons voir est la bijection fondamentale (voir [13, p. 109-110] pour plus de détails et références). Cette bijection permet de montrer qu’à partir d’une permutation de taille n et de k cycles, il est possible de construire une autre permutation de taille n et de k min-records. La bijection fondamentale procède en écrivant la permutation dans sa décomposition en cycles. Pour chacun de ces cycles, nous faisons en sorte de prendre la représentation avec le plus grand élément en première position. Enfin, nous trions les cycles dans l’ordre croissant par les valeurs prisent par leurs premiers éléments, puis nous retirons les parenthèses pour obtenir la forme en mot de la permutation image. Exemple. Prenons la permutation σ = 926857341. Sa représentation en cycle est σ = (367)(19)(5)(48)(2). Nous pouvons la réarranger en faisant en sorte que le plus grand élément de chaque cycle apparaît en premier ce qui donne σ = (736)(91)(5)(84)(2). On tri ensuite dans l’ordre croissant de ces premiers 16 éléments et on obtient σ = (2)(5)(736)(84)(91). En retirant les parenthèses nous obtenons l’image de σ par la bijection fondamentale soit F(σ) = 257368491. On voit bien ici, que chaque élément de début de cycle de σ est alors un record dans F(σ) et qu’il y a donc conservation entre ces deux statistiques. De plus, il est facile de voir à l’aide de cette remarque comment revenir en arrière puisqu’il suffit de chercher les min-records de l’image pour retrouver la décomposition en cycles de la permutation initiale et donc de voir que cette application est bien une bijection. Remarque. Il est facile d’obtenir une bijection fondamentale pour les maxrecords en mettant le plus grand élément de chaque cycle en première position et en les triant dans l’ordre décroissant. Bijections entre montées et descentes : Il existe deux involutions qui permettent à partir d’une permutation de transformer toutes les montées en descentes et réciproquement. La première est de représenter une permutation σ sous forme de mot et de prendre le mot miroir σe qui pour chaque i ∈ [n] associe σe(i) = σ(n + 1 − i). Dans ce cas, une montée en position i ∈ [n] dans σ ∈ Sn devient une descente en position n−i dans σe. Une autre involution, notons la η, qui possède la même propriété d’inversion des descentes et des montées procède en remplaçant chaque élément σ(i) de σ ∈ Sn, avec i ∈ [n], par n + 1 − σ(i). Cette application laisse invariant la position des montées devenues des descentes et réciproquement. Exemple. Prenons à nouveau la permutation σ = 926857341. Nous avons alors σe = 143758629 et η(σ) = 184253769. 

Résultats provenant de la combinatoire

Nombres de Stirling de la première espèce non-signés : Les nombres de Stirling apparaissent dans de nombreux problèmes de combinatoire. En particulier, les nombres de Stirling de la première espèce non-signés comptent les permutations de Sn composées de k cycles. Ces nombres sont notés c(n, k). Il n’est alors pas étonnant de les voir apparaîtrent dans les expressions des probabilités faisant intervenir des permutations distribuées en fonction de leur nombre de cycles, comme c’est le cas de la distribution d’Ewens dont nous discuterons au cours du chapitre 6. Remarque. Comme nous avons pu le voir précédemment, les records sont en bijection avec les cycles, et ainsi c(n, k) comptent également les permutations de taille n avec k records. Par convention, nous considérons que c(0, 0) = 1. Par définition, comme il est impossible d’avoir des permutations de tailles non-nulles et composées de moins de 0 cycle, nous avons pour tout n > 0 et tout k ≤ 0 que c(n, k) = 0. De la même façon, il est impossible d’avoir des permutations composées d’un plus grand nombre de cycles que son nombre d’éléments, autrement dit pour tout n ≥ 0 et pour tout k > n, nous avons c(n, k) = 0. Nous allons maintenant présenter des propriétés remarquables de ces nombres. Lemme 1. Pour tout n > 0, pour tout k > 0, nous avons la relation de récurrence c(n + 1, k) = nc(n, k) + c(n, k − 1) 17 qui est vérifiée. Démonstration. La preuve se fait par construction. Pour obtenir une permutation de taille n + 1 qui est composée de k cycles, nous pouvons partir d’une permutation de taille n et insérer l’élément n+1 afin d’obtenir une nouvelle permutation de taille n + 1. Pour avoir une permutation de taille n + 1 composée de k cycle après l’insertion de l’élément n + 1, il y a deux cas possibles : — Soit la permutation initiale possède déjà k cycles, dans ce cas, il suffit de rajouter l’élément n + 1 dans un des cycles déjà existants. Il y a n positions possibles dans ce cas. Comme nous avons c(n, k) permutations qui ont exactement k cycles, il y a en tout nc(n, k) possibilités d’obtenir une permutation de taille n + 1 à k cycles de cette façon. — Soit la permutation initiale possède déjà k − 1 cycles, dans ce cas il est nécessaire de créer un nouveau cycle constitué uniquement de n + 1. Comme il y a en tout c(n, k − 1) permutations qui ont exactement k − 1 cycles, il y a en tout c(n, k −1) possibilités d’obtenir une permutation de taille n + 1 à k cycles de cette façon.