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.