CHAPITRE VI. — l'analyse COMBINATOIRE

Cette démonstration est due à 0. Rodrigues; mais le résultat précédent est de M. Catalan (Journal de Liouville, i^ série, t. III et VI).

44. Permutations avec répétition. — Ce sont les diverses manières de disposer n objets en ligne droite, ces objets n'étant pas tous distincts. Par exemple, si a lettres sont égales à a, si ^ lettres sont égales à 6, . . . , X lettres à /, avec la condition

le noijibre des permutations avec répétition est

Exemple /. — De combien de manières peut-on effectuer le produit de n facteurs égaux ou inégaux?

Si a facteurs sont égaux àa, pà6, y^^)***» ^^ désignant par a, b, c, ... des facteurs quelconques inégaux, il faut diviser

Ort = 2»-*. 1.3.5. ... (2/1 — 3),

par le produit des factorielles

Exemple IL — De combien de manières peut-on remplacer le produit de n facteurs par des produits de deux facteurs dans le cas de n pair, et par des produits de deux facteurs et d'un seul, dans le cas de n impair?

Exemple III, — De combien de manières peut-on décomposer un produit de 3n facteurs en n produits de trois facteurs?

On trouve

45. Arrangements simples. — Les arrangements simples de p objets distincts, pris ^^ à y, sont les manières de disposer en ligne droite q de ces objets, de telle sorte que deux dispositions diffèrent soit par le choix, soit par Vordre des objets.

En désignant leur nombre par A^, on déduit ces arrangements des arrangements AJ~*, en écrivant successivement à la suite de ces derniers les (/? — 7 + 0 lettres qui n'y entrefnt pas

par suite,

K=PiP— i)(/>-2) ... (;? — ^-hi).

Ainsi, le nombre des arrangements simples de p objets, pris q à q, est le produit des q nombres entiers décroissants à partir de p.

Si p = q, on retrouve les permutations ; si ^ <C y^ on a A^ ^^^ o, conformément à la définition.

Si Ton exprime, de deux manières différentes, le nombre de fois qu^une lettre a entre dans le tableau des arrangements à une place déterminée, à la première par exemple, on a encore la formule de récurrence

Exempte /. — Former les arrangements simples de p lettres, prises q à q^ en suivant Tordre alphabétique.

Connaissant un arrangement simple, trouver son rang dans le tableau.

Inversement, écrire un arrangement simple de rang donné.

Exemple II. — Trouver la somme de tous les nombres du système décimal qui n'ont pas plus de cinq chiffres, et formés seulement des chiffres o, 1,2, 3, 4> les chiffres ne pouvant être répétés.

Exemple III. — Décomposer le tableau des arrangements simples de p lettres, prises q k q^ d'après la considération d'une lettre a.

Exemple IV. — Décomposer le tableau des arrangements simples de p lettres, prises q ^ q^ d'après la considération de deux lettres a e\ b.

46. Arrangements complets. — Les arrangements complets de p objets, pris q ^ q^ sont les manières de disposer en ligne droite q de ces objets, ces objets pouvant être répétés jusqu'à q fois, mais de telle sorte que deux dispositions diffèrent soit par le choix, soit par V ordre de ces objets.

En désignant leur nombre par B^, on a

Ainsi, le nombre des arrangements complets de p objets, pris q à q^ est le produit de q nombres égaux à p.

Si l'on écrit tous les nombres du système de base /? jusqu'à q chiffres, en complétant par des zéros à la gauche tous ceux qui ont moins de q chiffres, et en commençant par ooo. • .o, on forme les arrangements complets de/? chiffres pris q et q»

Exemple /. — Connaissant un arrangement complet de/? chiffres pris 7 à ^, trouver son rang et inversement.