THÉORIE DES COMBINAISONS

Définitions.

213. Considérons m objets quelconques. Si Ton groupe entre eux, de toutes les manières possibles, n quelconques de ces m objets, en ne tenant compte que de l'ordre des objets, on forme ce qu'on appelle les arrangements de ces m objets pris n à n. Deux arrangements diffèrent donc au moins par Tordre des objets qui les composent.

Si, parmi les arrangements obtenus, on ne conserve que ceux qui dijfèrent au moins par un objet, ces arrangements particuliers constituent ce qu'on appelle les combinaisons des m objets pris n à n. Dans les combinaisons, l'ordre des objets n* intervient pas.

On donne quelquefois aux combinaisons le nom de produits différents.

Arrangements.

%ik. Pour fixer les idées, nous supposerons que les objets qu'on veut grouper soient représentés par les lettres de l'alphabet a, b, c, dy . . ., h^ ky l, . , .,

Soient, par exemple, les quatre objets ou les quatre lettres a, 6, c, d.

Pour avoir leurs arrangements deux à deux, on écrira, à la droite de chacune d'elles, les trois autres lettres. On aura

De c. — Cours. III. i3

ainsi

ab, ac, ad;

ba, bCy bd;

^J ca, cb, cd;

duy dby de.

Pour avoir les arrangements trois à trois, on écrira successivement, à la droite de chaque arrangement deux à deux, les deux lettres qui n'y entrent pas. Il viendra

abc, abd, acb, acd, adb, ode;

bac y bad, bca, bcd, bda^ bdc;

cab, Cad, cba, cbd, cda, cdb;

dab, dac, dba, dbc, dca, dcb.

On continuera de la même manière, quels que soient m et n, en se servant toujours des arrangements de Tordre précédent.

215. Nous voulons chercher la formule qui fait connaître le nombre des arrangements de m objets pris nk n.

Nous indiquerons ce nombre par la notation A^y l'indice marquant le nombre total des objets considérés, et l'exposant le nombre de ceux qui doivent entrer dans chaque arrangement.

On peut procéder par induction pour trouver, en opérant de proche en proche, la formule dont il s'agit {Alg, élém,, W)7); mais on peut aussi établir directement la loi qui lie les deux nombres A^r* et AJ,, et en déduire la formule cherchée.

AJj~* représentant le nombre des arrangements des m objets ou des m lettres données prises n — i à n — i, il suffit évidemment, pour avoir tous les arrangements /i à n, et d'après ce qui précède (214), d'écrire successivement, après chaque arrangement n — i à /i — i, les m — (n — i) ou les/n— /i -+-i lettres qui n'y entrent pas.

En effet, on obtient bien de cette manière tous les arrangements /i à /i; car on peut toujours former un arrangement n à n désigné, en plaçant la /i»*™« lettre considérée à la suite d'un certain arrangement des n — i autres lettres.

De plus, tous les arrangements n^ n ainsi trouvés ^oni dis-tincts; car ceux qui correspondent à un même arrangement

ALGEBRE SUPÉRIEURE. IQS

/i — I à n — 1 diffèrent par leur dernière lettre, et ceux qui sont terminés par la même lettre correspondent à des arrangements n — i hn — i différents.

Cela posé, puisque chaque arrangement n — ikn — i donne naissance h m — n-hi arrangements /i à /i, on a

En faisant dans cette relation /i = 2, 3, 4» . . . , /i, on obtient

successivement •

AJi = Al,(m~i),

Ai. = A?J//i-3),

A^,==A?„-Hm-n-M).

Si Ton multiplie toutes ces égalités membre à membre, et si Ton remarque que le premier membre de chaque égalité est reproduit par le premier facteur du second membre de l'égalité suivante, on a, en opérant les réductions et en remplaçant A*, par sa valeur évidente m,

AJj=: m{m — i) {m — 2) {m — 3). ..(m — /i-hi).

Cette formule, qui donne le nombre des arrangements n à n de m objets quelconques, est composée de n facteurs ; le premier facteur est m; les autres facteurs diminuent successivement d'une unité jusqu'au /i»«°*'» qui est m — /i -f- 1.

Permutations.

216. Si Ton fait n=zm dans la formule précédente, on a le nombre des arrangements de m objets pris m à m.

Ces arrangements, où entrent tous les objets donnés, ont reçu le nom de permutations

Si Ton désigne leur nombre par P,» et si Ton renverse Tordre des facteurs du second membre, on a évidemment

Les facteurs du second membre forment la suite naturelle des nombres entiers, depuis i jusqu'à m.

On voit que le nombre des permutations augmente très ra-

pidement avec le nombre des objets considérés. On a

Pio=36a88oo.

217. On rencontre très souvent en Analyse le produit des m premiers nombres entiers consécutifs. On le représente symboliquement par la notation m\ Dans ces conditions, la formule du nombre de permutations de m objets devient

Les analystes ont donné aux produits de cette forme le nom de/actorielles^ et en ont étudié les propriétés.

218. Pour obtenir les permutations d'un certain nombre d'objets, on adopte la marche suivante :

Soient, par exemple, les trois objets ou les trois lettres a, b, c. On commence par écrire les permutations des deux premières lettres a et h. II n'y en a évidemment que deux,

ahj ha.

On prend alors la troisième lettre c, et on lui fait occuper toutes les places, de droite à gauche, dans chacune des permutations précédentes. On a ainsi

ahc^ acbj cab^ bac, bca, cba.

On continue de même pour quatre lettres, cinq lettres, . . . , m lettres, en se servant toujours des permutations de Tordre précédent.

219. On peut, d'après cela, donner de la formule des permutations (216) une démonstration indépendante de la formule des arrangements.

Supposons qu'on connaisse le nombre des permutations de k objets ou P^t.

Si, à chacune de ces permutations, on adjoint un nouvel objet ou une nouvelle lettre, en lui faisant occuper successivement toutes les places de droite à gauche, places qui sont évidemment au nombre de A: 4-1, on aura toutes les permutations de A:-hi objets, sans en oublier ni sans en répéter aucune. On peut donc écrire

ALGEBRE SUPÉRIEURE. ig^

En faisant successivement A: = i, a, 3, . . . , m — i, on a P,= Pl2, P3=P,3, P4 = P,4> ..M P,„=:P,„-im.

En multipliant toutes ces égalités membre à membre, en supprimant les facteurs communs et en remarquant que P,= i, il vient, comme précédemment,

P;„= i .2.3.^ . , . m:= ml

Combinaisons.

220. Prenons, par exemple, cinq objets ou cinq lettres a, b, c, d, e, et cherchons les combinaisons (213) de ces cinq lettres prises trois à trois.

Nous commencerons par former les combinaisons de ces lettres prises deux à deux, en écrivant successivement, après chacune d'elles, les lettres qui la suivent dans Tordre naturel. Nous aurons

abf aCy ad, ae,

bc, bd, be,

cdy ce, de.

Nous écrirons successivement, à la suite des combinaisons précédentes, les lettres qui, dans Tordre naturel, viennent après la dernière lettre de chaque combinaison, et nous aurons toutes les combinaisons des cinq lettres prises trois à

trois :

abc y abd, abe, acd, ace, ode,

bcd, bce, bde,

cde.

On continuera de la même manière, quels que soient m et Hy en se servant toujours des combinaisons de Tordre précédent.

221. Nous voulons chercher la formule qui fait connaître le nombre des combinaisons de m objets pris n à /t, nombre représenté par C^.

Nous donnerons d'abord une démonstration indirecte, fondée sur les résultats précédents.

igS ALGÈBRE SUPÉRIEURE.

Supposons qu'on ait formé les combinaisons n à n de m objets, c'est-à-dire les arrangements /i à n de ces m objets qui diffèrent au moins par Tun des objets qui y entrent (213). En prenant toutes ces combinaisons et en effectuant les permutations (216) des n objets qui composent chacune d'elles, on obtient tous les arrangements n à n des m objets donnés.

En effet, chaque permutation donne un arrangement /i à /i. Aucun arrangement n'est omis; car chaque combinaison correspond à un certain arrangement, en laissant de côté Tordre des objets qui y entrent; et, en effectuant toutes les permutations de ces objets, on doit trouver Tarrangement particulier qu'on a en vue. Aucun arrangement n'est répété; car ceux qui proviennent d'une même combinaison diffèrent par l'ordre des objets, et ceux qui ne proviennent pas d'une même combinaison diffèrent au moins par l'un des objets qui les composent.

Chaque combinaison contenant n lettres donne lieu à un nombre P„ de permutations. On a donc, d'après ce qu'on vient d'établir.

An — p» p

On en déduit (215, 216)

p„ A* m(m — i)(m — 2)(m — 3)...(m — /iH-î) '" ~ P; "" I . 2 \ 3 \ 4 ~ n

Cette formule générale renferme n facteurs entiers au numérateur et n au dénominateur. Les premiers vont en décroissant depuis m jusqu'à m — /i-+-i; les seconds vont en croissant depuis i jusqu'à n,

222. Tout nombre de combinaisons étant nécessairement entier, la formule obtenue démontre immédiatement ce théorème :

Le produit de n nombres entiers consécutifs quelconques est toujours dii^isible par le produit des n premiers nombres e/itiers,

223. On peut donner à la formule des combinaisons une autre expression qui est souvent plus commode.

On ne change rien au nombre qu'elle représente, en mul-

ALGÈBRE SUPÉRIEURE. IQQ

tipliant ses deux termes par le produit i.2.3...(m — n). On complète ainsi les facteurs du numérateur depuis m jusqu'à i . 11 vient alors, en renversant Tordre de ces mêmes facteurs,

"* I.2.3.4.../IX 1.2.3.4. ..(/w-^w)

Le numérateur contient, dans ce cas, m facteurs qui sont les nombres entiers de i à m; le dénominateur en contient aussi m, qui sont les nombres entiers de i à /i et de i à m— /i. On peut donc écrire, symboliquement (217),

22&>. La nouvelle forme obtenue démontre immédiatement ce théorème :

Le produit des m premiers nombres entiers'est toujours divisible par le produit des n premiers nombres entiers multiplié par celui des m — n premiers nombres entiers, quel que soit /i, pourvu qu'il soit m^oindre que m,

225. On peut présenter, comme il suit, une démonstration directe de la formule des combinaisons.

Supposons que l'on connaisse les combinaisons de m objets pris j9 à p. En associant successivement à chacune d'elles les m — p objets qui n'y entrent pas, on formera des combinaisons de m objets pris/? -i- 1 à /> -i- 1, en nombre égal à

CS,(/n-/>).

Aucune combinaison /? 4- 1 à /? 4- 1 ne peut ainsi échapper, puisqu'on emploie toutes les combinaisons p k p; mais les combinaisons obtenues ne sont pas toutes distinctes. En effet, prenons l'une de ces combinaisons : quel que soit l'objet qu'on y supprime, parmi les p-hi qu'elle renferme, on retrouvera une combinaison php différente. Il en résulte évidemment que la même combinaison p-hi à 77 -h i reparaîtra, dans l'opération effectuée, de p-{-i manières différentes.

Le nombre exact des combinaisons de m objets pris/> + i à /) -h I est donc

200 ALGEBRE SUPÉRIEURE.

£n faisant successivement, dans cette relation,

on a

et —pi ^~'

PS pî 2!: 1