|
|||||||||||||||||||||||||||||||||||||||||||||||||||||
|
PERMUTATIONS et CYCLES Calcul de la quantité de cycles La notion de cycles engendrés par les permutations
a été vue. Cette page montre comment calculer la quantité de cycles. On sait
que ces quantités sont appréhendées avec les nombres de Stirling de première
espèce qui forment un triangle à la manière du triangle
de Pascal. Néanmoins
la formule de calcul général existe et sa démonstration
mérite le coup d'œil. |
Cette page est la
suite de la page d'introduction sur les cycles en
permutations
|
|
||
|
Quantité de type de cycles On montre à droite:
Notez que pour les permutations
circulaires de n éléments (k = 1): Q1 = (n – 1)! La somme des Qi vaut n! On note parfois ces quantités: S (4, 2) = 11: quantité de permutations de 4 éléments avec deux
cycles. |
Valeurs 4, [6,
11, 6, 1] Pour quatre éléments, il y a six cycles de
longueur 1, onze de longueur 2, etc. (Revoir l'exemple) 5, [24,
50, 35, 10, 1] 6, [120,
274, 225, 85, 15, 1] 7, [720,
1764, 1624, 735, 175, 21, 1] 8, [5040,
13068, 13132, 6769, 1960, 322, 28, 1] 9,
[40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1] 10,
[362880, 1026576, 1172700, 723680, 269325, 63273, 9450, 870, 45, 1] Ce sont
les nombres de Stirling
de première espèce. |
|
|
|
||
|
Quantité et calcul avec
factorielles Il est possible de retrouver
ces quantités avec la formule générale indiquée, même dans le cas de
configurations "panachées". Exemple Prenons l'exemple n = 4. Il y a
3 cas avec deux cycles de 2 éléments:
On note cette recherche avec les valeurs de ki en fonction de i croissant: [0, 2, 0, 0]. L'application de la formule générale donne bien 3. |
Formule de calcul de la quantité de
cycles de permutation pour n éléments
n = 4 simple Deux cycles de longueur 2
n = 4 "panachée" Deux cycles de longueur 1 et un de longueur 2. Notez que le total fait bien 4: (2x1 + 1x2).
n = 5 "panachée" Un cycle de longueur 2 et un de 3. |
|
|
|
|||
|
Démonstration Cette
démonstration ne présente pas de difficulté particulière sinon la maîtrise
des paramètres. A la clé,
un bel artifice mathématique de simplification à la fin de la démonstration. |
Pour "apprivoiser" les paramètres, je
vous propose d'aborder la justification de la formule en présentant deux
exemples:
|
||
|
Premier calcul Prenons un exemple pour bien comprendre le
principe du calcul combinatoire. Soit, deux cycles de longueur 1 et trois de
longueur 2, pour un total n = 8 (= 2x1 + 3x2) (Voir le tableau) Il y a huit possibilités de choix pour le premier
cycle (un nombre de 1 à 8); et sept pour le deuxième cycle; en effet, en
éliminant le premier choisi, il reste les sept autres (comme si on
tirait les nombres dans une urne). Même principe avec les cycles suivants. Il reste
six chiffres parmi lesquels choisir. On en tire 2, soit 2 parmi 6,
ce qui fait (6x5/1x2 =) 15 possibilités, puis 6 pour le couple suivant, et
enfin 1 pour le dernier couple. Au total 5 040 possibilités ( le produit). Oui, mais! Parmi les deux nombres choisis pour
les cycles unités, on retrouve deux fois le même choix (1),(2) et (2),(1), par
exemple; avec les trois couples c'est 3! = 6 fois. Au total: 2! x 3! = 12
redondances. D'où le calcul du tableau. |
Tableau de calcul de Q sur un
exemple
Notes: Ne vous
laissez pas abuser par le choix des nombres de 1 à 8 pour les cycles. On
aurait pu choisir n'importe quoi. Les exemples de cycles sont
donnés pour fixer les idées. Ne pas y donner plus d'importance. Rappelez-vous
qu'il y a 5 040 combinaisons. Difficile à représenter! |
||
|
Explication du calcul final de Q On explicite le calcul des combinaisons en
relisant le tableau ci-dessus. Du fait de tous les calculs successifs, le
numérateur est égal à 8! = n! Nous allons voir ce que devient le reste en abordant
le prochain calcul. |
|
||
|
Deuxième
calcul Même principe
que précédemment avec introduction de cycles de longueur 3. Alors, lorsqu'on
sélectionne un cycle de trois éléments (5, 6, 7), viennent avec lui les permutations circulaires de ce cycle. Ici: (5, 7, 6). Ce facteur
multiplicatif est introduit dans le tableau. |
Calcul avec introduction des
permutations circulaires
|
|
Calcul final de Q Le facteur multiplicatif, loin de compliquer les
choses, va introduire une belle simplification. |
|
|
Propriété |
|
|
Application:
Simplification
de Q |
|
|
Généralisation |
La
formule de calcul de Q devient explicite pour deux cycles. Elle est
généralisable à une configuration quelconque de cycles. La
formulation précise est d'une écriture un peu lourde; on se contentera de
l'extrapolation de la formule trouvée numériquement. |
|
Formule
littérale relative à l'exemple précédent Avec
simplification |
|
|
Formule
générale |
|
Merci à Alain Rodot pour sa majeure contribution à la
création de cette page,
Notamment pour la démonstration de la formule de calcul
de Q.
|
Retour |
|
|
Suite |
|
|
Voir |
|
|
Sites |
|
|
Cette page |
