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 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 aux combinaisons le nom de produits différents.
Arrangements.
2H. 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,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 chacune d'elles, les trois autres lettres. On aura
De C. — Cours. III. i3
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, aed, adb, ade;
bac, bad, bca, bed, bda, bdc]
cab, cad, eba, cbd, cda, cdb;
dab, dac, dba, dbc, dea, 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 n à /i.
Nous indiquerons ce nombre par la notation AJ,, 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., 4-07); mais on peut aussi établir directement la loi qui lie les deux nombres A^-1 et A"t, et en déduire la formule cherchée.
A*-1 représentant le nombre des arrangements des m objets ou des m lettres données prises n — 1 à n — 1, 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à n — i, les m— (n — 1) ou les m— n-hi lettres qui n'y entrent pas.
En effet, on obtient bien de cette manière tous les arrangements nk n; car on peut toujours former un arrangement n à n désigné, en plaçant la nièmo lettre considérée à la suite d'un certain arrangement des n — 1 autres lettres.
De plus, tous les arrangements n à n ainsi trouvés sont distincts; car ceux qui correspondent à un même arrangement
ALGEBRE SUPÉRIEURE. ig5
n — i à n — i diffèrent par leur dernière lettre, et ceux qui sont terminés par la même lettre correspondent à des arrangements n — i à n — i différents.
Cela posé, puisque chaque arrangement n — ikn — i donne naissance à m — n -+- 1 arrangements n à n, on a
Ai = Al-1 (*»-"-M).
En faisant dans cette relation n = 2,3,4, ...,/i, on obtient successivement
Aî, = AJUm — i),
Aï, = A?„(m-2), Aî, = AJ!t(m-3)f
Aï = Ai-|(ni-/n-i).
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 AJ, par sa valeur évidente m,
AJ, = m(m — 1) (m — 2) (m — 3)...(/ra — n-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 rièm* qui est m — n + 1.
Permutations.
216. Si l'on fait /i= m 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 l'on désigne leur nombre par P,» et si l'on renverse l'ordre des facteurs du second membre, on a évidemment
Pm = 1 . 2 . 3 . 4 . . . m.
Les facteurs du second membre forment la suite naturelle des nombres entiers, depuis 1 jusqu'à m.
On voit que le nombre des permutations augmente très ra-
ig6 ALGEBRE SUPÉRIEURE.
pidement avec le nombre des objets considérés. On a P10= 3628800.
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
Pm = m!
Les analystes ont donné aux produits de cette forme le nom de factorielleèy 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 ay b, c. On commence par écrire les permutations des deux premières lettres a et b. Il n'y en a évidemment que deux,
aby 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 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*.
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 k -+- 1, on aura toutes les permutations de k 4-1 objets, sans en oublier ni sans en répéter aucune. On peut donc écrire
En faisant successivement k = i, 2, 3, . . . , m — 1, on a
P^Pl2, P,= P,3, P^P34, .--, P,»=Pm-im.
En multipliant toutes ces égalités membre à membre, en supprimant les facteurs communs et en remarquant que Pi= 1, il vient, comme précédemment,
Pm = 1 . 2 . 3 . 4 • • • m = m\
Combinaisons.
220. Prenons, par exemple, cinq objets ou cinq lettres a, b9 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
ab, ac, ad, ae,
bc, bd, be,
cd, 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, abd, abe, acd, ace, ade,
bcd, bce, bde, cde.
On continuera de la même manière, quels que soient m et n, 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 à n, nombre représenté par CJ,.
Nous donnerons d'abord une démonstration indirecte, fondée sur les résultats précédents.
Supposons qu'on ait formé les combinaisons n à n de m objets, c'est-à-dire les arrangements n h 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 composent chacune d'elles, on obtient tous les arrangements n à n des m objets donnés.
En effet, chaque permutation donne un arrangement nk 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, 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 — f» p
On en déduit (215, 216)
A* m(m — i)(m — 2)(/w — 3)...(/w — n-hi)
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 — /14-1; les seconds vont en croissant depuis 1 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 entiers.
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-
ALGEBRE SUPÉRIEURE. IÇ9
tipliant ses deux termes par le produit i .a.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,
rn 1.2.3.4.. (m — 2) (m — i)m
m 1.2. 3. 4. .-nx 1.2.3.4. ..(/n — 1)
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 à n et de i à m— /i. On peut donc écrire, symboliquement (217),
Cn . ™!
224. 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 n9 pourvu qu'il soit moindre 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 p à p. En associant successivement à chacune d'elles les m — p objets qui n'y entrent pas, on formera des combinaisons de m objets pris/> -+- 1 à p -+- i, en nombre égal à
Aucune combinaison p -+- 1 à p -+- i ne peut ainsi échapper, puisqu'on emploie toutes les combinaisons p à 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/?-hi qu'elle renferme, on retrouvera une combinaison p à p différente. Il en résulte évidemment que la même combinaison p -+- 1 à p -+- i reparaîtra, dans l'opération effectuée, de p -+- 1 manières différentes.
Le nombre exact des combinaisons de m objets pris y? -+- i à/>-hi est donc
çp+i — çp m—P
En faisant successivement, dans cette relation, /? — 1,2, 3, .. .,n — i,
on a
f« — ft "»-'
En multipliant ces égalités membre à membre, en supprimant les facteurs communs et en remarquant que Ci,= m, on a, comme précédemment (221),
rn m (m — i) (m — 2) (m — 3). ..(m— /i-hi)
Nous allons maintenant démontrer, sur les combinaisons, quelques théorèmes utiles.
I. Les nombres de combinaisons dont les exposants sont complémentaires par rapport à l'indice commun sont égaux entre eux.
On dit que deux exposants sont complémentaires quand leur somme reproduit l'indice commun. Il faut, par conséquent, établir la formule
Cn pm—n
Ce théorème est, pour ainsi dire, évident; car, si Ton choisit, parmi les m objets considérés, une combinaison n à n, les m — n objets qui restent forment, à leur tour, une combinaison m — n à m — n. Les deux nombres de combinaisons sont donc nécessairement identiques.
La formule générale, sous la seconde forme indiquée (223), le prouve aussi immédiatement; car, si Ton y change n en m — n, on a
Et, en comparant l'expression de C™~* à celle de C* , on voit qu'elle ne présente pas d'autre changement que celui de l'ordre des deux produits i.a.3.4. . .net 1.2.3.4. . . (m — n) au dénominateur.
227. II. Si l'on considère les combinaisons n à n de m objets, le nombre de celles qui renferment p objets déterminés s'obtient en retranchant p de l'indice m et de l'exposant /1.
En effet, mettons à part ces p objets, il en restera m — p. Si l'on forme alors les combinaisons n — p h n — p de ces m—p objets, et si Ton range à la droite de chacune d'elles les p objets laissés de côté, on a évidemment toutes les combinaisons n à n qui renferment ces/? objets. Leur nombre est donc bien égal à
rn-p ^m—p*
228. III. Si l'on considère les combinaisons n à n de m objets, le nombre de celles qui ne renferment aucun objet choisi parmi p objets déterminés s'obtient en retranchant p de l'indice m.
En effet, si l'on met à part les p objets désignés, il n'en restera plus que m — p, qui entreront seuls dans les combinaisons nà n dont on cherche le nombre. Ce nombre est donc bien égal à
nn
229. Il en résulte que, si l'on considère les combinaisons n an de m objets, le nombre de celles qui renferment au moins un objet choisi parmi p objets déterminés est égal à
Cn nn
230. IV. Le nombre des combinaisons de m objets pris n à n est égal à la somme des nombres de combinaisons de m — 1 objets pris n — 1 an — 1 et n à n.
Cette proposition découle immédiatement des propositions établies aux n08 227 et 228, lorsqu'on suppose p = 1 .
On peut toujours, en effet, partager les combinaisons de m objets pris n à n en deux groupes : l'un composé des combinaisons qui renferment toutes un certain objet déterminé, l'autre composé de celles qui ne renferment pas cet objet.
On a ainsi la formule remarquable
rn — r> «-1 . nn
231. V. Le nombre des combinaisons de m objets pris nàn est égal à la somme des nombres de combinaisons n — i à n — i , de m — i , m — i, m — 3, ...,/i — i objets.
On peut, en effet, appliquer de proche en proche la formule précédente, en décomposant, toujours suivant la même règle, le dernier terme du second membre. On s'arrêtera nécessairement à l'égalité où, dans le premier membre, l'indice toujours décroissant sera devenu égal à l'exposant constant (cette dernière égalité se réduit évidemment à l'identité i = î). On aura donc successivement
Cn frt-i , pn m — Wt-i "T~ *-■/«- 1*
Cn — rn-l , f n rn — /v*-i . pn
Cn — pn-1
En ajoutant toutes ces relations membre à membre, et en remarquant que le dernier terme du second membre de chaque égalité n'est autre chose que le premier membre de l'égalité suivante, il vient, après simplification,
ci = c^+csi1,+cti*i+...+ct:î.-
Arrangements et permutations, avec répétition des objets considérés, supposés toujours distincts.
232. Nous avons supposé jusqu'à présent que les objets ou les lettres considérées ne pouvaient pas être répétées dans les arrangements formés.
En admettant cette répétition, on peut demander quel sera le nombre total des arrangements obtenus.
Ce nombre sera évidemment plus grand que lorsqu'il n'y a pas répétition. Si l'on veut, par exemple, obtenir les arrangements deux à deux des trois lettres a, b9 c, il faudra joindre aux arrangements ordinaires
ab9 ac, ba, bcy ca> cb>
les nouveaux arrangements
aa, bb9 ce.
Nous trouverons le résultat cherché en appliquant le même procédé qu'au n° 215.
Désignons par (AR)* le nombre des arrangements avec répétition de m objets pris nkn.
Supposons qu'on connaisse les arrangements avec répétition de m objets pris n — i à n — i. Pour passer aux arrangements n à n, il est évident qu'il suffit d'écrire successivement, après chaque arrangement /i — i à n — 1, les m lettres données, puisque leur répétition est acceptée.
Tous les arrangements n à n seront obtenus, car ils commencent tous par un certain arrangement n — i à n — i. Ils seront tous distincts, car ils diffèrent tous par l'arrangement n — i à n — i qui leur a donné naissance ou par leur dernière lettre. On peut donc écrire
(ÀR)i = (ÀR)Sr»xni.
En faisant dans cette relation n=m9 3, 4, . . ., n9 en multipliant les égalités correspondantes membre à membre, en simplifiant et en remarquant que ( AR)Jrt = m,ona
(ÀR)£=m».
233. Il en résulte immédiatement que le nombre (PR)m des permutations avec répétition est également
(PR)/n = *i'».
Combinaisons, avec répétition des objets considérés, supposés toujours distincts.
234. Nous avons supposé jusqu'à présent que les objets ou les lettres considérées ne pouvaient pas être répétées dans les combinaisons formées.
En admettant cette répétition, on peut demander quel sera le nombre total des combinaisons obtenues.
Ce nombre sera évidemment plus grand que lorsqu'il n'y a pas répétition. Prenons, par exemple, les quatre objets ou les quatre lettres a9 b, c, d9 et formons leurs combinaisons trois à trois avec répétition. Nous obtiendrons les combinaisons
ordinaires, plus celles où la même lettre peut entrer deux ou trois fois. Nous aurons ainsi les quatre combinaisons connues (220)
abc, abdy acd, bcd,
plus seize nouvelles combinaisons
aab, aaCy aady bba% bbc, bbdy cca, ccb, ccd, dda, ddb, ddc, aaa, bbb, ccc, ddd;
en tout, vingt au lieu de quatre.
235. Pour obtenir la formule générale des combinaisons avec répétition, nous ferons usage du principe suivant.
Désignons par (CR)* le nombre des combinaisons avec répétition de m objets pris n à n, et supposons formé le Tableau de toutes ces combinaisons.
Nous allons chercher, de deux manières différentes, combien de fois une certaine lettre désignée entre dans ce Tableau, et, en égalant les deux expressions correspondantes, nous aurons la formule cherchée.
Soit a la lettre désignée.
Dans chaque combinaison, il y a n lettres. Le nombre total des lettres du Tableau est donc
n(CR)t;
mais toutes les lettres entrant identiquement dans le Tableau., il suffît de diviser ce nombre total par m pour avoir le nombre de fois
£<CR)i
que la lettre a entre dans le Tableau. C'est là notre première expression.
Mettons maintenant de côté ou supprimons, mais une seule fois, la lettre désignée a dans toutes les combinaisons où elle entre. Les combinaisons ainsi modifiées seront alors les combinaisons avec répétition des m lettres données prises n — i à
n — i, et le nombre de ces combinaisons sera représenté par
