THÉORIE DES COMBINAISONS

Définitions.

213. Considérons m objets quelconques. Si l'on 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 diiïèrent donc au moins par l'ordre des objets qui les composent.

Si, parmi les arrangements obtenus, on ne conserve que ceux qui diffè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 an\ combinaisons le nom de produits différents.

Arrangements.

214. Pour fixer les idées, nous supposerons que les objets qu'on veut grouper soient représentés par les lettres de l'alpliabet a, b, c, d, . . ., h, k, l, . . ..

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

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

De c. — Cours. III. i3

adb.

adc;

bda.

bdc\

cda,

cdb;

dca,

dcb.

ÏÇ)\ ALGÈBRE SUPÉRIEURE.

ainsi

ab, ac, ad;

ba, bc, bd:

ca, cb, cd;

da, db, 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,

bac, bad, bca, bcd,

cab, cad, cba, cbd,

dab, dac, dba, dbc.

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

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

Nous indiquerons ce nombre par la notation A'^^, 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., 407); mais on peut aussi établir directement la loi qui lie les deux nombres A^^~^ et A"„ et en déduire la formule cherchée.

A"f ' 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 n à n, et d'après ce qui précède (214), d'écrire successivement, après chaque arrangement n — i à « — i, les m — {n — i) ou les m — « + i lettres qui n'y entrent pas.

En effet, on obtient bien de cette manière tous les arrangements n à n; car on peut toujours former un arrangement n à n désigné, en plaçant la «'^""^ 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 sonidistincts; car ceux qui correspondent à un même arrangement

ALGÈBRE SUPÉRIEURE. IqS

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

Cela posé, puisque chaque arrangement n — i à « — i donne naissance à m — n-\-\ arrangements n à n, on a

En faisant dans cette relation « = 2,3,4» •••,«, on obtient successivement

AL=A;„(/?^ — i),

K,^kl:'{m-n-^x).

Si l'on multiplie toutes ces égalités membre à membre, et si l'on 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 k.),^ par sa valeur évidente m,

Celte 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 «■«'"« qui est m — « -t- i.

Permutations.

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

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

Si l'on désigne leur nombre par P,„ et si l'on renverse l'ordre des facteurs du second membre, on a évidemment

Les facteurs du second membre forment la suite naturelle des nondjres entiers, depuis i jusf|u'à m. On voit que le nombre des permutations augmente très ra-

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

217. On rencontre très souvent en AnalNse 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 Ae factorielles, 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, h, c. On commence par écrire les permutations des deux premières lettres a et b. Il n'y en a évidemment que deux,

ab, ba.

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

abc, acb, cab, bac, bca, cba.

On continue de même pour quatre lettres, cinq lettres, . . ., m lettres, en se servant toujours des permutations de l'ordre 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 (lu'on connaisse le nombre des permutations de k objets ou Fa.

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'-hi, on aura toutes les permutations de y^ 4-1 objets, sans en oublier ni sans en répéter aucune. On peut donc écrire

ALGEBRE SUPÉUIEURE. IQ-

En faisant successivement A- = i, 2, 3, . . .,m — i, on a

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,

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 deujr à deux, en écrivant successivement, après chacune d'elles, les lettres qui la suivent dans Tordre naturel. Nous aurons

ae,

ah.

ac.

ad,

bc,

bd.

be,

cd.

ce,

de.

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

abc, abd, abe, acd, ace, ade,

bcd, bce, bde, ode.

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

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

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

198 ALGÈBRE SUPÉraEURE.

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

En effet, chaque permutation donne un arrangement n à n. Aucun arrangement n'est omis; car chaque combinaison correspond à un certain arrangement, en laissant de côté l'ordre des objets qui y entrent; et, en effectuant toutes les permutations de ces objets, on doit trouver l'arrangement 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, el 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,

Are — rn p

On en déduit (213, 216)

nn __ ■^'''» '" ('" "~" 0 ('" — 2) ("? — 3) . . . (/« — 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 — n+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 divisible par le produit des n premiers nombres entic l' s.

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 nml-

ALGEBRE SUPÉRIEURE. IQQ

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