CHAPITRE VI. — L ANALYSE COMBINATOIRE

prises q ^ q» Enfin, comme il y a -^ manières de prendre q lettres du

second groupe, le nombre des arrangements distincts de la classe de rang {q -h i) est

- I Clp-q bq ou CJÎ ap- ,j bq.

En faisant varier q de o k p el faisant la somme, on trouve la formule donnée.

Si l'on remplace les arrangements simples par les arrangements complets, oa retrouve la formule du binôme (n*^ 40).

49. Combinaisons complètes. — Les combinaisons complètes (ou avec répétition) dep objets, pris ç'^q^ sont les groupes que Ton peut former avec q de ces objets, ces objets pouvant être pris jusqu'à q fois, de telle sorte que deux groupes diffèrent par le choix et non par l'ordre des objets.

Si l'on désigne par D^ le nombre des combinaisons complètes, on a:

Nombre des lettres du Tableau D^ q DJÎ

Nombre de fois que a se trouve dans DJÎ - DJ,

Nombre des combinaisons contenant a I^Jl'

Nombre de fois que a se trouve dans Dj~* -- -- DJ" ' .

Par suite, d'où l'on déduit

Ainsi, le nombre des combinaisons complètes de p objets, pris qà q, est le produit des q nombres entiers croissants à partir de Py divisé par le produit des q premiers nombres.

En renversant l'ordre des facteurs du numérateur de D^, on a

ainsi, le nombre des combinaisons complètes de p objets j pris q à y, est égal au nombre des combinaisons simples de{ p '\~q — i ) objets, pris qàq. On peut démontrer directement ce résultat de la manière suivante. Désignons par

ai, «j, «3, ..., dp,

Exemple III. — Décomposer le tableau Dj par la considération de trois lettres «r, ^, c.

Combinaisons ne contenant aucune des trois lettres . . . ^^^-3

» contenant une des trois lettres CJD^lJ

» » deux des trois lettres C| D^I*

» » les trois lettres CJ DJ~'

On a donc la formule

D/, = D2, + 3 D1,Z\ + 3 D^IÎ + D/r' ■

On trouve, par induction, la formule suivante

On peut démontrer directement cette formule par la considération de r lettres déterminées, ou la vérifier a posteriori.

Si l'on exprime les combinaisons complètes au moyen des combinaisons simples, on trouve une formule qui ne diffère pas sensiblement de la formule (i) du n° 48 {Ex. III).

51. Les inversions. — Il y a inversion ou dérangement dans une? permiilation de nombres, inégaux deux à deux, écrits sur une ligne horizontale, toutes les fois qu'un nombre se trouve placé à la gauche d'un nombre plus petit.

Pour compter le nombre des inversions, on peut procéder de deux manières différentes, soit en comptant pour chaque terme le nombre des termes qui sont à la droite plus petits que lui, soit en comptant pour chaque terme le nombre de ceux qui sont à la gauche plus grands que lui, et en faisant le total pour tous les termes dans Tun ou l'autre cas.

On divise les permutations de n nombres en deux classes, suivant que le nombre des inversions est pair ou impair. Les deux classes sont également nombreuses.

L'échange de deux éléments quelconques d'une permutation change la classe de la permutation. Plus généralement, un nombre pair d'échanges d'éléments quelconques d'une permutation n'en modifie pas la classe 5 un nombre impair d'échanges produit sur la permutation primitive un changement de classe. (Bézout. )

Exemple I. — Déterminer le nombre total D^ des inversions dans le tableau des P,, permutations de n éléments. Écrivons d'abord (/i -hi) fois

•CHAPITRE VI. — l'analyse COMB INATOIRE . 71)

le tableau P», nous obtenons ainsi (n-hi)Dn dérangements. Plaçons maintenant le (/n-i)'^"** élément à la dernière place, à ravant-dernière, ..., à la seconde placera la première dans chacun des tableaux; nous produisons successivement pour chaque permutation

nouveaux dérangements et nous avons construit le tableau des P/j+i permutations de (n -f- 1) éléments. On a donc

Drt4-l=(/t-4-l)D„+ — ^ ^Pn.

Posons Dn= P/iQ/i, il vient

remplaçons successivement n par i, 2, 3, . . ., (/i — i), et faisons la somme des égalités obtenues ; nous trouvons

Q/i = — et Dfl=^P/|G;,.

On vérifie immédiatement ce résultat en observant que le nombre total des inversions d'une permutation et de la permutation renversée est égal au nombre GJ des combinaisons de n éléments pris deux à deux.

Exemple IL — Le nombre total des inversions contenues dans les permutations circulaires de n éléments est l (n — i) n(n ■+■ 1).

o2. Les cycles. — On peut encore déterminer la classe d'une permutation par la méthode plus expéditive des cycles, due à Cauchy. Considérons une permutation quelconque de quinze nombres, et plaçons au-dessus de chacun de ses termes les nombres entiers suivant l'ordre ordinaire

1,2, 3,4,5, 6,7, 8, 9, 10, II, 12, i3, 14, i5; 8, 6, 12, I, 5, i{, 2, II, i3, i5, 4, 9, 3, 10, 7.

Au-dessous de i se trouve 8 ; au-dessous de 8 se trouve 1 1 ; audessous de 1 1 se trouve 4 î au-dessous de 4 se trouve i . On forme ainsi le premier cycle