Voir la source de Permutation

{{Autre4|une notion mathématique|l'album d'[[Amon Tobin]]|Permutation (album)}}
{{confusion|texte=Ne doit pas être confondu avec [[combinaison sans répétition|combinaison]].}}
[[File:Permutations RGB.svg|thumb|Chaque rangée est une permutation des trois billes de couleur.]]

En [[mathématiques]], la notion de '''permutation''' exprime l'idée de réarrangement d'objets discernables. Une permutation d'objets distincts rangés dans un certain ordre correspond à un changement de l'ordre de succession de ces objets.

La permutation est une des notions fondamentales en [[combinatoire]], c'est-à-dire pour des problèmes de dénombrement et de [[probabilité|probabilités discrètes]]. Elle sert ainsi à définir et à étudier le [[Carré magique (mathématiques)|carré magique]], le [[carré latin]], le [[sudoku]], ou le [[Rubik's Cube]]. Les permutations servent également à fonder la [[théorie des groupes]], celle des [[déterminant (mathématiques)|déterminants]], à définir la notion générale de [[symétrie]], etc.

== Définition et exemples ==

=== Définitions ===

Une '''permutation''' (ou '''substitution<ref>{{Ouvrage|auteur1=Alain Bouvier, Michel George, François Le Lionnais|titre=Dictionnaire des mathématiques|éditeur=PUF|année=2005|passage=642, 807}}</ref>''') d'un [[ensemble]] <math>E</math> (ou ''sur'', ''dans'', l'ensemble <math>E</math>) est une [[bijection]] de <math>E</math> sur lui-même.

On définit aussi une '''permutation''' de <math>n</math> objets distincts numérotés formant un <math>n</math>-[[uplet]]  <math>(a_1,\cdots,a_n)</math> comme un [[arrangement]] <math>(a_{i_1},\cdots,a_{i_n})</math> de ces <math>n</math> objets (où <math>n</math> est un [[entier naturel]] non nul).

Les deux notions sont liées par le fait que si <math>\sigma</math> est une permutation sur l'ensemble <math>\{a_1,\cdots,a_n\}</math>, alors <math>(\sigma(a_1),\cdots,\sigma(a_n))</math> est une permutation du ''<math>n</math>''-[[uplet]] <math>(a_1,\cdots,a_n)</math>.

Une permutation de <math>n</math> éléments est aussi appelée '''permutation sans répétition''' de ces éléments, pour insister sur le fait que les <math>n</math> éléments sont distincts ; si ce n'est pas le cas, on parle de [[permutation avec répétition]]<ref>{{Chapitre|titre chapitre=Rappels d'analyse combinatoire|titre ouvrage=Cours d'analyse, université de Tours|lire en ligne=https://celene.univ-tours.fr/pluginfile.php/762814/course/overviewfiles/Probas%20Cours%20Chapitre%201.pdf?forcedownload=1}}</ref> . 

Signalons qu'autrefois, une permutation était aussi appelée « substitution », notamment  par [[Augustin Louis Cauchy]]<ref>{{Article|auteur1=Amy Dahan|titre=Les Travaux de Cauchy sur les Substitutions. Étude de son approche du concept de groupe.|périodique=Archive for History of Exact Sciences|volume=23|numéro=4|pages=279-319|date=31.XII.1980|lire en ligne=https://www.jstor.org/stable/41133599|accès url=payant}}</ref>.

=== Exemples ===

Une permutation de [[alphabet|l'alphabet]] de 26 lettres est un [[mot]] de 26 lettres contenant chaque lettre une fois et une seule ; et il est clair que cette définition reste valable pour n'importe quel alphabet de <math>n</math> lettres, avec des mots de longueur <math>n</math>.

Il y a beaucoup d'ordres différents (720) dans lesquels six cloches, de différentes notes, peuvent être sonnées les unes après les autres. Si les cloches sont numérotées de 1 à 6, alors chaque ordre possible peut être représenté par une liste de 6 nombres, sans répétition, par exemple (3, 2, 6, 5, 1, 4).

De la même façon, six livres posés sur un rayonnage et numérotés de 1 à 6, peuvent être permutés de différentes manières : rangement par ordre alphabétique, ordre alphabétique inverse, ordre du plus récent au plus ancien et vice-versa, ordre de préférence, ou ordre choisi « au hasard ». Chacun de ces réarrangements peut être vu comme une bijection de l'ensemble des six livres, ou de façon identique, une bijection de l'ensemble {1, 2, … ,6} sur lui-même. En effet, si l'ordre final des livres est 3, 2, 6, 5, 1, 4, on peut définir l'application ''f'' : « est remplacé par » ainsi :
* 1 est remplacé par 3 soit f(1) = 3 ;
* 2 est remplacé par 2 soit f(2) = 2 ;
* 3 est remplacé par 6 soit f(3) = 6 ;
* 4 est remplacé par 5 soit f(4) = 5 ;
* 5 est remplacé par 1 soit f(5) = 1 ;
* 6 est remplacé par 4 soit f(6) = 4.

Finalement, les objets effectivement permutés comptent peu : la permutation peut être ramenée à une permutation de nombres : les numéros des livres ou les numéros de cloches.

Supposons que <math>n</math> personnes s'assoient sur ''n'' chaises différentes numérotées de 1 à <math>n</math> disposées sur une même rangée. Nous pouvons considérer un placement de ces <math>n</math> personnes sur les chaises, comme une bijection de l'ensemble des <math>n</math> personnes sur lui-même, indiquant la façon dont les personnes sont placées les unes par rapport aux autres sur les chaises.

=== Dénombrement des permutations ===

Soit <math>E</math> un [[ensemble fini]] à ''n'' éléments. Le problème est de compter les permutations de <math>E</math>, c'est-à-dire les bijections de <math>E</math> dans lui-même. Comme pour les exemples précédents, on peut toujours numéroter les éléments de <math>E</math> de 1 à <math>n</math>. Dénombrer les permutations de <math>E</math> revient à dénombrer tous les réarrangements possibles de la liste, c'est-à-dire tous les ''n''-[[uplet]]s formés d'entiers de 1 à <math>n</math> dans un certain ordre.

Il est possible de donner une liste de tous ces réarrangements, sous forme d'une représentation [[arbre (mathématiques)|arborescente]] : il y a <math>n</math> choix pour le premier terme de la liste. Puis pour chacun de ces premiers choix, il y a <math>n</math> – 1 possibilités pour le deuxième choix, <math>n</math> – 2 pour le troisième, ainsi de suite. Finalement il y a <math>n!</math> ([[factorielle]] de <math>n</math>) choix possibles pour constituer une liste. Cette méthode permet d'énumérer une et une seule fois chaque permutation.

{{énoncé||Si ''E'' est un ensemble fini de cardinal ''n'', alors l'ensemble des permutations de ''E'' est fini, de cardinal ''n''!.}}

Lorsque <math>n</math> = 0, le résultat reste encore valable puisqu'il existe une seule application de l'[[ensemble vide]] dans lui-même et qu'elle est bijective.

Il est possible de dénombrer plus généralement les [[arrangement|''p''-arrangements]] de <math>n</math> éléments, ou encore les applications injectives d'un ensemble de cardinal fini <math>p</math> dans un ensemble de cardinal fini <math>n</math>. Ce nombre d'arrangements se note <math>A_n^p</math> et le cas des permutations apparaît comme le cas particulier <math>n=p</math><ref>{{Ouvrage|titre=Algèbre - 2ème année [[Classe préparatoire mathématiques et physique|MP-MP*]]|auteur=C. Antonini|éditeur=[[De Boeck Supérieur]]|date=2015|url={{Google Livres|3EvLDgAAQBAJ|page=39}}|page=39-41}}.</ref>.

=== Notation des permutations ===

Soit <math>E</math> un ensemble fini, de <math>n</math> éléments. Quitte à effectuer une numérotation, permuter les éléments de <math>E</math> revient à permuter les entiers de 1 à <math>n</math>. La notation traditionnelle des permutations place les éléments qui vont être permutés dans l'ordre naturel sur une première ligne, et les images en correspondance, sur une deuxième ligne. Par exemple
:<math>\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 5 & 4 & 3 & 1\end{pmatrix}</math>
est l'application <math>\sigma</math> définie par
:<math>\sigma (1)=2, \sigma (2)=5, \sigma (3)=4, \sigma (4)=3, \sigma (5)=1</math>
ou schématiquement 
:<math>\begin{matrix}1\longmapsto 2\\2\longmapsto 5\\3\longmapsto 4\\4\longmapsto 3\\5\longmapsto 1\end{matrix}</math>

Toutefois, la notation la plus pratique est la forme « [[Canonique (mathématiques)|canonique]] » (voir [[#Décomposition|ci-dessous]]). Sous cette forme, la permutation précédente s'écrit :
:(1 2 5)(3 4)
ce qui signifie 1 donne 2 (c.-à-d. 2 est l'image de 1, donc 1 est remplacé par 2) qui donne 5 qui donne 1 ; 3 donne 4 qui donne 3. Faire tourner les cycles à l'envers permet de savoir facilement où vont les éléments : 1 passe en position 5, 5 passe en position 2 et 2 passe en position 1.
Cette écriture correspond à la [[#Décomposition en produit de cycles à supports disjoints|décomposition]] sous la forme d'une [[#Composition de permutations|composition]] de [[permutation circulaire|permutations circulaires]] de supports disjoints.

Le [[support d'une permutation]] <math>\sigma</math> est l'ensemble des éléments <math>x</math> tels que <math>\sigma(x)</math> est différent de <math>x</math>. La permutation <math>\sigma</math> se restreint donc en l'identité sur le complémentaire de son support, et en une permutation sans [[point fixe]] sur son support.

=== Permutations particulières ===

'''Identité :'''

La permutation de <math>E</math> qui envoie chaque élément sur lui-même est l'[[application identité]] de <math>E</math>.

'''Transposition :'''

Une permutation qui échange deux éléments distincts <math>i</math> et <math>j</math> en laissant tous les autres inchangés est appelée '''transposition'''. On utilise fréquemment une notation allégée pour désigner cette permutation : <math>(i\ j)</math>. Il convient de remarquer qu'avec ce choix de notations, <math>(i\ j)=(j\ i)</math>. Une '''transposition élémentaire''' dans {1, …, <math>n</math>}  échange deux éléments voisins, <math>(i\ i+1)</math><ref>{{Lien web |titre=Option Algèbre et Calcul Formel de l'Agrégation de Mathématiques: Groupe Symétrique et groupes de permutations |url=https://nicolas.thiery.name/Enseignement/Agregation/Notes/groupe_symetrique.html}}</ref>.

'''Permutation circulaire :'''

Plus généralement, on définit les '''[[permutation circulaire|permutations circulaires]]''' ou '''cycles'''. Le ''p''-cycle associé aux éléments distincts ''<math>a_1,\cdots,a_p</math>'' (pris dans cet ordre) envoie l'élément <math>a_1</math> sur <math>a_2</math>, puis '''<math>a_2</math>''' sur <math>a_3</math> etc. et enfin <math>a_p</math> sur <math>a_1</math>. Tous les autres éléments restent inchangés. Un tel cycle se note habituellement sous la forme <math>(a_1\cdots a_p)</math>. Là encore, <math>(a_1\cdots a_p)=(a_2\cdots a_p\ a_1)=\cdots</math>.

== Propriétés algébriques ==

=== Composition de permutations ===

Les permutations de <math>E</math> sont définies comme des applications de <math>E</math> dans <math>E</math>, il est donc possible de définir leur '''produit de [[Composition de fonctions|composition]]''', qui se note <math>\circ</math> (mais ce signe est  souvent omis). Précisément, pour deux permutations <math>\sigma</math> et <math>\sigma'</math>, appliquer <math>\sigma'</math> puis <math>\sigma</math> revient à appliquer une permutation <math>\sigma''=\sigma\circ\sigma'</math> appelée le ''produit'' de <math>\sigma</math> et <math>\sigma'</math>.

La notation des permutations est bien adaptée au calcul du produit de composition. Ainsi en prenant par exemple
:<math>\sigma=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\2 & 5 & 4 & 3 & 1\end{pmatrix}\qquad 
\sigma'=\begin{pmatrix}1 & 2 & 3 & 4 & 5\\3&5&2&4&1\end{pmatrix}</math>
Le calcul du produit peut être présenté sur trois lignes. La première et la deuxième ligne présentent l'effet de la première permutation <math>\sigma'</math>, puis on fait correspondre aux éléments de la deuxième ligne leur image par <math>\sigma</math>.
:<math>\begin{pmatrix}1 & 2 & 3 & 4 & 5\\3&5&2&4&1\\ 4&1&5&3&2\end{pmatrix}</math>
Soit, finalement, en rayant la ligne de calcul intermédiaire
:<math>\sigma''=\sigma\circ\sigma'=
\begin{pmatrix}1 & 2 & 3 & 4 & 5\\4&1&5&3&2\end{pmatrix}</math>

La [[loi de composition]] n'est pas commutative (dès que l'ensemble <math>E</math> a au moins 3 éléments) mais deux permutations de supports disjoints commutent.

=== Structure de groupe ===

{{Article détaillé|groupe symétrique}}

Soient <math>n</math> éléments distincts dans un certain ordre. Appliquer une permutation <math>\sigma</math> revient à en modifier l'ordre. Revenir à l'ordre initial se fait aussi par une permutation ; celle-ci est notée <math>\sigma^{-1}</math>. Plus généralement, cette application <math>\sigma^{-1}</math>, est la [[bijection réciproque]] de <math>\sigma</math>, puisqu'appliquer <math>\sigma</math> puis ''σ''<math>\sigma^{-1}</math>, ou <math>\sigma^{-1}</math> puis <math>\sigma</math>, revient à appliquer la permutation identique. La permutation <math>\sigma^{-1}</math> s'appelle la '''permutation réciproque''' ou '''permutation inverse''' de <math>\sigma</math>.

Soit <math>E</math> un [[ensemble]] quelconque. L'ensemble, noté <math>S(E)</math> ou <math>\mathfrak S(E)</math> des permutations de <math>E</math> est un [[Groupe (mathématiques)|groupe]] pour la loi de composition <math>\circ</math>, appelé [[groupe symétrique]] de <math>E</math>.
Dans le cas particulier où <math>E</math> = {1, …, <math>n</math>} avec <math>n</math> [[entier naturel]], cet ensemble se note <math>S_n</math> ou <math>\mathfrak S_n</math>.

Si nous considérons un ensemble fini <math>E</math> de cardinal <math>n</math> (formé d'éléments qui ne sont pas nécessairement des entiers), nous pouvons numéroter les éléments de <math>E</math> et identifier les permutations des éléments de <math>E</math> avec les permutations des <math>n</math> premiers entiers > 0.

== Décompositions des permutations ==

=== Décomposition en produit de transpositions ===

Toute permutation de support fini peut être décomposée en un produit de [[#Permutations particulières|transpositions]]. Par exemple, cela signifie qu'on peut, par des échanges deux à deux, modifier à volonté l'ordre des cartes d'un paquet.

Comme deux transpositions <math>(i\ j)</math> et <math>(k\ l)</math> concernant [[quatre éléments]] différents commutent, une telle décomposition n'est pas unique. De plus, une transposition est une [[Involution_(math%C3%A9matiques)|involution]], on peut donc également ajouter un échange de deux cartes, puis l'échange des deux mêmes cartes. En revanche on démontre que la parité du nombre de transpositions nécessaire reste la même. Ceci permet de définir la '''parité''' et la '''[[signature d'une permutation]]'''.

Une [[Groupe alterné|permutation paire]] est une permutation qui peut être exprimée comme le produit d'un nombre pair de transpositions. Une définition équivalente est que sa décomposition en cycles disjoints donne un nombre pair (éventuellement nul) de cycles de longueurs paires. Une permutation impaire est une permutation qui peut être exprimée comme produit d'un nombre impair de transpositions.

La permutation identité est une permutation paire car elle peut être considérée comme le produit de 0 transposition, selon la convention sur le [[produit vide]].

La permutation circulaire <math>(1\ 2\cdots p)</math> est le produit des transpositions <math>(1\ p)(1\ p-1)\cdots(1\ 3)(1\ 2)</math>. La décomposition en produits de cycles disjoints (voir ci-dessous) implique donc la décomposition en produit de transpositions.

La transposition <math>(i\ j),i<j</math> est la composition des transpositions élémentaires <math>(i\ i+1)(i+1\ i+2)\cdots(j-1\ j)(j-2\ j-1)\cdots(i\ i+1)</math> ce qui montre que toute permutation est décomposable en un produit de transpositions élémentaires. C'est un outil utile pour visualiser une permutation.

==== Algorithme de décomposition ====

Voici l'étape générale d'un [[Algorithmique|algorithme]] de décomposition d'une permutation <math>\sigma</math> de support fini {1, …, <math>n</math>}.

* si la permutation est l'identité elle est produit de 0 transposition.
* sinon il est possible de considérer le premier point non fixe par <math>\sigma</math>
:<math>k=\min\{s, 1\leqslant s \leqslant n, \sigma(s)\neq s\} </math>
Alors en appelant <math>\tau</math> la transposition qui échange <math>k</math> et <math>\sigma(k)</math>, on forme <math>\sigma_1=\tau\circ\sigma</math> et on reprend l'algorithme avec <math>\sigma_1</math>.

On forme ainsi des permutations <math>\sigma_1,\sigma_2</math> etc. obtenues en multipliant <math>\sigma</math> par une succession de transpositions <math>\tau_1,\tau_2</math> etc., jusqu'à atteindre la permutation identité. Alors il vient
:<math>(\tau_p \tau_{p-1}\dots\tau_1)\sigma= {\rm Id} \qquad \sigma=\tau_1\tau_2\dots \tau_p</math>

La validité de l'algorithme se justifie en remarquant que la position du premier point non fixe augmente strictement à chaque étape, jusqu'à ce que tous les points soient fixes. L'algorithme se conclut après au plus <math>n</math> – 1 opérations, puisque si les <math>n</math> – 1 premiers points sont fixes, ils le sont tous.

Ainsi il est possible d'affirmer plus précisément que toute permutation peut s'écrire comme produit d'au plus <math>n</math> – 1 transpositions. En outre, le nombre minimum de transpositions nécessaires pour écrire une permutation donnée est exactement celui obtenu avec cet algorithme.

L'algorithme ci-dessus correspond à l'algorithme de décomposition en produit de cycles disjoints suivi de l'écriture de chaque cycle comme un produit de transpositions. Le nombre minimum de transpositions nécessaires est donc égal à <math>n-p</math>, où ''<math>p</math>'' est le nombre de cycles disjoints (en comptant les points fixes comme cycles de longueur 1).

=== Décomposition en produit de cycles à supports disjoints ===

==== Orbite d'un élément ====

[[image:050712 perm 1.png|thumb|les deux cycles de la permutation σ]]
L''''orbite''' d'un élément selon une permutation <math>\sigma</math> est l'ensemble de ses images successives obtenues par applications répétées de <math>\sigma</math>. Ainsi en introduisant la permutation <math>\sigma</math>
:<math>\begin{pmatrix}1 & 2 & 3 & 4 & 5&6&7&8\\3&4&5&7&6&1&8&2\end{pmatrix}</math>
L'élément 1 a pour images successivement 3,5,6 puis de nouveau 1,3,5 etc. L'orbite de 1 est donc l'ensemble {1,3,5,6}. L'orbite de 3 est également l'ensemble {1,3,5,6}, mais l'orbite de 2 est {2,4,7,8}.

Plus généralement, pour une permutation quelconque, les orbites sont disjointes et forment une [[partition (mathématiques)|partition]] de l'ensemble {1,2,…,<math>n</math>}. En restriction à une orbite donnée de taille ''<math>p</math>'', la permutation se comporte comme une [[permutation circulaire]] des ''<math>p</math>'' éléments.
[[image:PermutationDiagram34576182.svg|thumb|Le diagramme de la permutation  σ comme produit de transpositions élémentaires se lit de haut en bas.]]

==== Décomposition ====

Pour décrire la permutation, il suffit de prendre un élément dans chaque orbite et de donner l'ordre de succession de ses images par [[itération]] de <math>\sigma</math>. Ainsi toujours avec le même exemple, la permutation <math>\sigma</math> peut s'écrire sous la forme d'une succession des deux [[Permutation circulaire|cycles]]  (1 3 5 6) et (2 4 7 8). L'ordre des cycles n'importe pas mais l'ordre des éléments à l'intérieur d'un cycle doit être respecté jusqu'à l'obtention d'un cycle complet. Ainsi, la même permutation peut être écrite par exemple
:<math>\sigma = (1\ 3\ 5\ 6) \circ (2\ 4\ 7\ 8) = (2\ 4\ 7\ 8)\circ (1\ 3\ 5\ 6) = (7\ 8\ 2\ 4)\circ (6\ 1\ 3\ 5)\;</math> 

Dans cette notation on omet souvent le symbole de composition <math>\circ</math> pour alléger l'écriture.

La décomposition « canonique » d'une permutation en « produit » de cycles s'obtient en plaçant d'abord le plus petit nombre en première position dans chaque cycle et en ordonnant les cycles selon leur premier élément. Cette notation omet souvent les points fixes, c'est-à-dire les éléments qui sont leur propre image par la permutation; ainsi la permutation (1 3)(2)(4 5) s'écrit simplement (1 3)(4 5), puisqu'un cycle d'un seul élément n'a aucun effet.

Si, au contraire, on place le plus petit nombre en dernière position dans chaque cycle, sans omettre les points fixes, on obtient une suite de nombres, liée aux [[Nombre de Stirling#Interprétation combinatoire|nombres de Stirling]], qui permet l'analyse combinatoire du nombre de cycles et de la taille des cycles d'une permutation : c'est la [[correspondance fondamentale de Foata]].

==== Applications ====

De nombreuses propriétés de la permutation <math>\sigma</math> peuvent se lire facilement sur sa décomposition en cycles disjoints :
* la [[Signature d'une permutation|signature]] de <math>\sigma</math> est le produit des signatures des cycles : elle vaut (–1)<sup>''n-p''</sup> = (–1)<sup>''q''</sup>, où ''<math>p</math>'' est le nombre de cycles disjoints (en comptant les points fixes comme cycles de longueur 1) et ''<math>q</math>'' est le nombre de cycles de longueur paire ;
* l'[[Ordre (théorie des groupes)|ordre]] de <math>\sigma</math> (en tant qu'élément du [[groupe symétrique]]) est égal au [[Plus petit commun multiple|PPCM]] des longueurs des cycles ;
* la [[action par conjugaison|conjuguée]] d'une permutation <math>\pi</math> par une permutation <math>\sigma</math> est la permutation <math>\sigma\circ\pi\circ\sigma^{-1}</math>. On peut aisément calculer cette permutation, en remplaçant chaque élément <math>i</math> de la décomposition en cycles disjoints de <math>\pi</math> par <math>\sigma(i)</math>;
* le [[théorème des restes chinois]] est clairement illustré par les puissances de <math>\sigma</math>. Il est plus facile à énoncer quand les longueurs des cycles sont premières entre elles : dans ce cas, l'ordre de <math>\sigma</math> est le produit <math>n</math> des longueurs ''<math>n_i</math>'' des cycles et le groupe engendré par les puissances de <math>\sigma</math> est isomorphe à <math>\Z/n\Z</math> qui lui-même est décomposable en produit des <math>\Z/n_i\Z</math>, chaque cycle avançant à son rythme pour ne retomber en phase qu'au produit.

==== Dénombrement ====

Soient <math>n</math> un entier naturel, <math>K</math> un sous-ensemble de <math>\N</math>, et <math>L</math> un sous-ensemble de <math>\N^*</math>. Si on note <math>S_n(K,L)</math> l'ensemble des permutations de l'ensemble des <math>n</math> plus petits entiers naturels non nuls dont le nombre de cycles (en comptant bien un cycle d'ordre 1 pour chaque point fixe) dans la décomposition en produit de cycles à supports disjoints appartient à <math>K</math>, et pour lesquelles tous les cycles de cette décomposition sont d'ordre appartenant à <math>L</math>, alors pour tout sous-ensemble <math>K</math> de <math>\N</math>, pour tout sous-ensemble <math>L</math> de <math>\N^*</math>, et pour tout nombre z de module strictement inférieur à 1, <math>\sum_{n=0}^{\infty} \frac{|S_n(K,L)|}{n!}z^n=\sum_{k \in K}\frac{1}{k!}(\sum_{l \in L}\frac{z^l}{l})^k</math>.

Pour certains ensembles <math>K</math> et <math>L</math>, la fonction génératrice peut s'exprimer simplement à l'aide de fonctions bien connues, comme l'exponentielle et le [[logarithme]]. Parfois, ces deux [[Fonction transcendante|fonctions transcendantes]] se neutralisent entre elles pour donner une [[fonction algébrique]]. Ce théorème permet de résoudre le [[problème des rencontres]], et de démontrer beaucoup d'autres théorèmes, dont ceux-ci :

Pour tout entier naturel <math>n</math> et pour tout entier naturel non nul <math>p</math>, <math>\sum_{k=0}^{n}|S_{pn}(\{k\},p\N^*)|z^k=\frac{(pn)!}{p^n \times n!} \prod_{k=0}^{<n}(z+pk)</math>.

Pour tout entier naturel <math>n</math>, le nombre de permutations d'un ensemble de <math>n</math> éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre pair est égal au carré du nombre de permutations d'un ensemble de <math>n</math> éléments dont la décomposition en produits de cycles à supports disjoints n'a que des cycles d'ordre 2.

== Références ==
{{Références}}

== Articles connexes ==
* [[Code de Lehmer]]
* [[Correspondance fondamentale de Foata]]
* [[Matrice de Costas]]
* [[Matrice de permutation]]
* [[Nombre de Stirling]]
* [[Permutation avec répétition]]
* [[Permutation aléatoire]]
* [[Permutation circulaire]]
* [[Permutation alternée]]
* [[Problème des rencontres]], permutations sans point fixe
* [[Superpermutation]]
* [[Théorème de réarrangement de Riemann]]

{{Portail|mathématiques}}

[[Catégorie:Permutation|*]]