Si l'on considère la suite des substitutions
le nombre total des substitutions de n lettres étant fini, on doit nécessairement retomber sur une substitution déjà obtenue : supposons, par exemple, que l'on trouve alors
ou
cette formule prouve que la substitution S? laisse invariable une permutation quelconque; ainsi
et k désignant un entier quelconque
les puissances successives de S forment donc une suite périodique.
Si [3 est le plus petit entier donnant Si^ = i, on dit que S est d'ordre [3.
Si au lieu de SP-=* on écrit S-=<; on a
On voit facilement que si S remplace la permutation a par la permutation h. S"* remplacera h par a.
Soit [3 l'ordre de S et
/désignant le plus grand commun diviseur de a et [3, y.^ el j3i seront premiers entre eux. Pour déterminer l'ordre x de la substitution S^ posons
d'où
il en résulte que (3i ou -^ est la plus petite valeur de x, donc :
Si S est d'ordre (3, S" sera d'ordre ^i f étant le plus grand
commun diviseur de a et ^. On remarquera que S'^ et S sont de même ordre si c/. et ^ sont premiers entre eux. Dans ce cas, les puissances de S* seront égales, à l'ordre près, à celles de S ; par exemple, si l'on pose
on aura
a.r — pj = /;,
équation qui a toujours une solution si a et (3 sont premiers entre eux.
Exemple. — Soit
e a h cl de
I c a c h d\ le a h \a h c d c ] '^ \a h à
ldcah\ ^ - \a h d e)
\a I) d cj et S est du quatrième ordre; si l'on pose, par exemple,
on a
et l'on a aussi
(«■)-(fir.)=^'
Si l'on applique celte substitution à la fonction
«3-1- 3rt;/;2 2ff^e,
on a
Substitutions circulaires.
143. Une substitution est dite circulaire, quand elle substitue à chaque lettre du dénominateur celle qui la suit et quand elle remplace la dernière parla première.
La substitution
est circulaire, car elle remplace chaque lettre de a h d e par la suivante et la dernière e par a; une pareille substitution se représente encore par une suite de lettres entre paren-
236 QL'ATRIÈME PARTIE. — CHAPITRE I.
thèses, ainsi
ç^ ^ [^ c d ''/'\ = {n b c cl c) = {b c d e a), \a b c cl e I
L'ordre d'une substitution circulaire est évidemment égal au nombre des lettres qu'elle déplace. Car, par une application répétée de cette substitution, on remplace successivement a par b c d e a el, quand on a remplacé a par a, on obtient la substitution i.
lii. Toute substitution est un produit de substitutions circulaires.
Prenons, en effet, une lettre arbitrairement au dénominateur de cette substitution, elle se trouve remplacée par une seconde, celle-ci par une troisième et ainsi de suite jusqu'à ce que l'on tombe sur la première; ces lettres constituent une substitution circulaire ou un cycle. Si l'on opère de la même façon sur les autres lettres, on obtient de nouveaux cycles. Une substitution ou un cycle qui opère sur deux lettres est ce que l'on appelle une transposition; elle revient à l'échange de ces lettres; un C3'cle composé d'une seule lettre peut être négligé.
La substitution
-,/// k cl f h j a g e c i m l n \a b c cl e f g II i j k l m n ,
peut se décomposer ainsi
S = (« h g){b k i e){c dfj)(lm){n),
OÙ le dernier cycle formé d'une seule lettre peut être laissé de côté. Il est évident que l'ordre dans lequel on écrit les cycles est indifférent. .
lio. L'ordre d'une substitution est égal au plus petit multiple des ordres de ses cycles.
Soit, en effet,
S = CoCiCo. . .
une substitution décomposée en ses facteurs circulaires, et soit
comme les cycles sont relatifs à des lettres différentes, on a
La plus petite valeur que puisse prendre x est, d'après cela, le plus petit des nombres satisfaisant à la fois aux égalités précédentes.
Si tous les cycles de S sont de même ordre, cet ordre sera aussi celui de S, et une pareille substitution est dite régulière; il ne faut pas oublier que les cycles considérés doivent tous contenir des lettres différentes.
{ab){cd) est une substitution régulière du second ordre, mais (aô) (6c) ^ (aôc) est une substitution circulaire du troisième ordre.
146. Si S est une substitution circulaire d'ordre [3, S^ sera une substitution régulière composée de f cycles, f désignant le plus grand commun diviseur de a et [3. Si a et [3 sont premiers entre eux, S"^ sera elle-même circulaire.
Soit
S remplace ap par a^+i, S^ remplace «p par a^+a, ..., S'^ remplace «p par rtp+a; si l'on effectue la substitution S'-*, on obtiendra d'abord un cycle
ou un indice tel que p -\- xy. devra être remplacé par le reste de sa division par (3, s'il est plus grand que ,3. Alors, pour retomber sur la lettre ap, il faut que
^-4- o£x = p — Pj ou .r=-^,
OÙ X désigne le nombre des lettres du cycle. Si a et |3 sont premiers entre eux / == a, a; := [3, et la substitution S est cir-
Exemple :
238 QUATRIÈME PAIITIE. — CHAPITRE I.
culaire. Si a =/ai, (3 =:/j3i, alors/ = ^ et le nombre des cycles est
S = inbcdef), S2= {ace){bdf), S^ = (ad){be){cf), S^=(aec){bfd), S-' = (afedcb), S«=i.
147. Toute substitution régulière est une puissance d'une substitution circulaire.
Soit la substitution régulière
S = {ciibiCi . . .gOiOibiCo . . . o-a)- • ■(amb,nC„, . ■ .gm}- Si l'on pose
G = (rti r^2 . • . ffm bi bi . . . b„i . . . gig2 . . .g,n ),
on a évidemment
lis. Toute substitution peut être décomposée en facteurs primitifs, c'est-à-dire en facteurs dont l'ordre est un nombre premier ou une puissance d'un nombre premier.
Supposons S d'ordre n et
a et [3 désignant des nombres premiers entre eux. On peut toujours trouver des entiers x, / tels que
Alors
Or, on a
de sorte que les facteurs S"'^, SP^ sont d'ordre (3 et a respectivement; on peut ainsi poursuivre la décomposition en facteurs jusqu'à ce que l'on n'ait plus que des facteurs d'un ordre égal à un nombre premier, ou à une puissance d'un nombre premier.
Exemple .
S = {abcdef)
est d'ordre 2 x 3 =6; on a donc où
Substitutions semblables et échangeables.
