Annales de mathématiques pures et appliquées/Tome 03/Analise élémentaire, article 12

Recherche de quelques formules appartenant à la théorie des combinaisons ; par MM. le Grand et Rochat.

Annales de mathématiques pures et appliquées, 3, 1813 (p. 213-222).

QUESTIONS RÉSOLUES.

Recherches de quelques formules appartenant à la
théorie des combinaisons ;

En réponse à la dernière des deux questions proposées
à la page 104 de ce volume ;

Par MM. Le Grand et Rochat, professeurs de mathématiques
à St-Brieux.

≈≈≈≈≈≈≈≈≈

Des lettres $a,b,c,d,\ldots ,$ au nombre de $m,$ étant données ; on sait qu’en les prenant $n$ à $n,$ de toutes les manières possibles, elles donnent un nombre de produits différens exprimé par

${\frac {m}{1}}.{\frac {m-1}{2}}.{\frac {m-2}{3}}.\ldots {\frac {m-n+1}{n}}.\qquad$ (A)

Concevons qu’on ait formé tous ces différens produits et que, dans chacun d’eux, on ait disposé les facteurs suivant l’ordre alphabétique, du premier au dernier ; comme dans chacun d’eux il manquera $m-n$ des lettres $a,b,c,d,\ldots ,$ les lettres qui le composeront ne se succéderont pas toutes consécutivement, en sorte qu’un de ces produits, pris au hasard, pourra présenter d’abord un certain nombre de lettres consécutives ; puis un autre nombre de lettres aussi consécutives entre elles, mais non consécutives aux premières ; puis encore un autre nombre de lettres consécutives entre elles, mais non consécutives à celles qui composeront la seconde partie : et ainsi de suite. Soit par exemple, le produit

$abdefhikl,\qquad$en l’écrivant ainsi$\qquad ab.def.hikl,$

on voit qu’il est composé de trois facteurs, lesquels sont eux-mêmes des produits dont les facteurs sont consécutifs.

À l’avenir nous considérerons comme produits d’une même classe tous ceux qui, décomposés comme nous venons de le faire dans le précédent exemple, présenteront le même nombre de séries de facteurs consécutifs ; et un produit sera dit de première classe si tous ses facteurs sont consécutifs, de deuxième classe s’il est formé de plusieurs facteurs consécutifs, et de plusieurs autres facteurs aussi consécutifs entre eux, mais non consécutifs aux premiers ; un produit sera dit de troisième classe, s’il présente trois séries de facteurs consécutifs, dans chacune d’elles, mais non consécutifs d’une série à l’autre ; et ainsi de suite.

Nous diviserons ensuite les produits d’une même classe en genres, en appelant produits d’un même genre, ceux qui non seulement renfermeront un même nombre de séries de facteurs consécutifs, mais qui de plus seront tels que chaque série, dans l’un, aura autant de facteurs qu’une série de l’autre. Ainsi, d’après cette définition, les deux produits de même classe

$ab.def.hikl,\qquad abc.ef.hikl,$

sont du même genre, parce que, dans chacun d’eux, il y a une série de deux facteurs, une série de trois facteurs et une de quatre.

Enfin, deux produits d’un même genre seront dits de même espèce, si les diverses séries de facteurs consécutifs qui les composent, considérées uniquement par rapport au nombre de leurs facteurs, y sont rangées dans le même ordre ; tels sont, par exemple, les deux produits

$ab,defg.ik,\qquad bc.efgh.kl.$

À l’avenir, paur plus de clarté et de simplicité, nous indiquerons les produits dans lesquels il se trouvera des séries de $\alpha ,\beta ,\gamma ,\ldots$ facteurs consécutifs, en écrivant les lettres $\alpha ,\beta ,\gamma ,\ldots ,$ séparées par des virgules, entre des crochets, et les plaçant suivant le rang des séries, de la première à la dernière ; ainsi, par exemple, le symbole $[\gamma ,\alpha ,\theta ,\lambda ]$ désignera un produit de quatrième classe dans lequel la première série aura $\gamma$ facteurs, la seconde $\alpha ,$ la troisième $\theta$ et la quatrième $\lambda .$ On voit d’après cela, que les produits

$[\gamma ,\alpha ,\theta ,\lambda ],\qquad [\beta ,\lambda ,\delta ,\phi ],$

sont de même classe, sans être de même genre ; que les produits

$[\gamma ,\alpha ,\theta ,\lambda ],\qquad [\lambda ,\gamma ,\alpha ,\theta ],$

sont à la fois de même classe et de même genre ; qu’enfin tous les produits renfermés dans l’expression symbolique

$[\gamma ,\alpha ,\theta ,\lambda ],$

sont, à la fois de même classe, de même genre et de même espèce.

Ces préliminaires établis, l’objet que nous nous proposons ici est de déterminer, parmi tous les produits de $n$ facteurs qu’on peut faire avec $m$ lettres données, 1.^o combien il s’y en trouve d’une classe déterminée quelconque ; 2.^o combien, dans une même classe, il s’y en trouve d’un genre déterminé quelconque ; 3.^o enfin combien dans un même genre, il s’y en trouve d’une espèce déterminée quelconque.

Occupons-nous d’abord de la recherche du nombre des produits d’une même classe. Soit, en général, désigné par $C_{p}$ le nombre des produits de la classe $p$ ; c’est-à-dire, le nombre des produits dans lesquels il entre $p$ séries de facteurs consécutifs.

D’abord, pour les produits de première classe, ou de $n$ lettres consécutives, on voit que chacune des lettres $a,b,c,\ldots ,$ excepté les $n-1$ dernières, peut être combinée avec les $n-1$ lettres qui la suivent immédiatement ; en sorte qu’on doit avoir

$C_{1}={\frac {m-n+1}{1}}.$

Pour parvenir à l’expression de $C_{2},$ c’est-à-dire, du nombre des produits de la seconde classe, désignons-les par $[\alpha ,n-\alpha ]$ et cherchons d’abord ceux d’entre eux qui renferment la lettre $a.$ Pour les former, il faudra d’abord joindre à $a$ les $\alpha -1$ lettres qui la suivent consécutivement ; et, comme la lettre qui suivra immédiatement la dernière de ce produit ne pourra être employée, on ne pourra lui adjoindre que les produits de première clasie qu’il sera possible de former avec les $m-\alpha -1$ lettres restantes, en les prenant $n-\alpha$ à $n-\alpha$ ; le nombre de ces derniers produits, et conséquemment le nombre total des produits de deuxième classe qui doivent renfermer $a$ se trouvera donc, en changeant $m$ en $m-\alpha -1$ et $n$ en $n-\alpha ,$ dans la précédente formule ; ce qui donnera $m-n$ pour le nombre des produits de la forme $[\alpha ,n-\alpha ]$ où entre la lettre $a$ ; faisant donc successivement $\alpha =1,2,\ldots n-1,$, on aura évidemment, pour le nombre total des produits de seconde classe où, entre $a$

$(n-1)(m-n).$

Ayant fait ainsi de la lettre $a$ tout l’emploi que la nature de la question peut permettre, on déterminera le nombre des produits de seconde classe où elle n’entre pas, mais où entre $b,$ en cherchant combien on peut faire de produits de cette classe avec $m-1$ lettres ; ce qui donnera.

$(n-1)(m-n-1)\,;$

on trouvera pareillement que le nombre de ceux dans lesquels il n’entre ni $a$ ni $b,$ mais qui contiennent $c$ est

$(n-1)(m-n-2)\,;$

et ainsi de suite, en sorte qu’on aura, pour le nombre total des produits de la seconde classe,

$C_{2}=(n-1)\left[(m-n)+(m-n-1)+(m-n-2)\ldots +2+1\right]\,;$

c’est-à-dire,

$C_{1}={\frac {n-1}{1}}.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.$

Passons aux produits de troisième classe. Désignons toujours par $\alpha$ le nombre des facteurs qui composent la première série, et cherchons d’abord ceux de ces produits qui renferment le facteur $a.$ Il faudra comme ci-dessus, écrire d’abord à la droite de cette lettre les $\alpha -1$ lettres qui la suivent consécutivement, supprimer la $(\alpha +1)^{me}$ lettre et faire tous les produits de seconde classe que peuvent fournir les $m-\alpha -1$ lettres restantes, prises $n-\alpha$ à $n-\alpha$ ; changeant donc $m$ en $m-\alpha -1$ et $n$ en $n-\alpha$ dans l’expression de $C_{2},$ il viendra pour le nombre des produits de troisième classe où entre $a$ et où la première série contient $\alpha$ facteurs,

${\frac {m-n}{1}}.{\frac {m-n-1}{2}}.(n-\alpha -1)$

faisant donc successivement $\alpha =1,2,3\ldots n-2,$ on aura, pour la totalité de ceux des produits de la troisième classe dont fait partie

${\frac {m-n}{1}}.{\frac {m-n-1}{2}}.\left[(n-2)+(n-3)+(n-3)\ldots +2+1\right]$

$={\frac {n-1}{1}}.{\frac {n-2}{2}}.{\frac {m-n}{1}}.{\frac {m-n-1}{2}}.$

On en conclura le nombre de ceux qui, ne renfermant pas $a,$ renferment $b$ ; le nombre de ceux qui, ne renfermant ni $a$ ni $b,$ renferment $c,$ et ainsi de suite, en y changeant successivement $m$ en $m-1,m-2,\ldots n+2,$ ce qui donnera

$C_{3}={\tfrac {n-1}{1}}.{\tfrac {n-2}{2}}.{\tfrac {1}{2}}\left[(m-n)(m-n-1)+(m-n-1)(m-n-2)+\ldots 3.2+2.1\right],$

ou en sommant la série,^[1]

$C_{3}={\frac {n-1}{1}}.{\frac {n-2}{2}}.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{3}}.$

On aperçoit déjà facilement la loi de ces résultats, et l’induction conduit à poser généralement

$C_{p}={\frac {n-1}{1}}.{\frac {n-2}{2}}.\ldots {\frac {n-p+1}{p-1}}.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.\ldots {\tfrac {m-n-p+2}{p}}.$

cette induction se vérifie d’ailleurs par un raisonnement très-familîer aux analistes, et sur lequel, pour cette raison, nous croyons superflu d’insister.

Il est clair que le nombre total des produits $n$ à $n$ que peuvent fournir les $m$ lettres $a,b,c,\ldots$ est égal à la somme des nombres qui expriment combien il y en a de chaque classe ; en sorte qu’on doit avoir

${\tfrac {m}{1}}.{\tfrac {m-1}{2}}.{\tfrac {m-2}{3}}.\ldots {\tfrac {m-n+1}{n}}=C_{1}+C_{2}+C_{3}+\ldots +C_{p}+\ldots +C_{n}\,;$

mettant, dans cette équation, pour $C_{1},C_{2},C_{3},\ldots C_{p},\ldots C_{n}$ leurs valeurs, on parviendra à ce résultat qui, indépendamment de la théorie des combinaisons, présente un fait analitique assez remarquable

$\quad {\frac {m}{1}}.{\frac {m-1}{2}}.{\frac {m-2}{3}}.\ldots {\frac {m-n+1}{n}}$

$={\frac {m-n+1}{1}}$

$+{\frac {n-1}{1}}.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}$

$+{\frac {n-1}{1}}.{\frac {n-2}{2}}.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{3}}$

$+\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$

$+{\frac {n-1}{1}}.{\frac {n-2}{2}}\ldots {\frac {n-p+1}{p-1}}.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\tfrac {m-n-1}{3}}\ldots {\tfrac {m-n-p+2}{p}}$

$+\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$

$+{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{3}}\ldots {\frac {m-2n+2}{n}}.$

Nous observerons, en passant, que le dernier terme du second membre de cette équation exprimant combien, parmi les produits $n$ à $n,$ il s’en trouve qui ne contiennent point de lettres consécutives, résout conséquemment la question énoncée à la page 60 de ce volume.

Examinons présentement combien il peut y avoir, dans chaque classe, de produits de chaque genre et de chaque espèce.

Convenons de désigner généralement par $G_{p}$ le nombre des produits d’un genre donné qui se trouvent dans la classe $p,$ et par $E_{p}$ le nombre de ceux d’une espèce donnée qui se trouvent dans un genre donné, appartenant à la même classe $p.$

Il est d’abord évident que tous les produits de la première classe sont, à la fois, de même genre et de même espèce, en sorte qu’on a

$G_{1}={\frac {m-n+1}{1}},\qquad E_{1}={\frac {m-n+1}{1}}.$

Passons aux produits de la seconde classe ; considérons en particulier ceux de l’espèce $[\alpha ,n-\alpha ],$ et voyons d’abord combien il y a de ces produits qui renferment la lettre $a.$ Cette lettre, suivie des $\alpha -1$ qui lui succèdent dans l’ordre alphabétique, devant être combinée avec les produits de première classe que fournissent les $m-\alpha -1$ dernières lettres, prises $n-\alpha$ à $n-\alpha$ ; il faudra, pour avoir le nombre des produits de cette espèce, changer, dans $C_{1},G_{1}$ ou $E_{1},$ $m$ en $m-\alpha -1$ et $n$ en $n-\alpha ,$ ce qui donnera $m-n$ pour le nombre des produits de l’espèce $[\alpha ,n-\alpha ]$ qui renferment la lettre $a$ ; changeant successivement $m$ en $m-1,m-2,\ldots n+1$ et sommant la série, on trouvera

$E_{2}={\frac {m-n+1}{1}}.{\frac {m-n}{2}}.$

Pour passer de là au genre $G_{2},$ on remarquera qu’en général le nombre des produits de ce genre est égal au nombre des arrangemens différens dont $\alpha$ et $n-\alpha$ sont susceptibles ; c’est-à-dire, égal à $1.2$ : on aura donc

$G_{2}=1.2.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.$

Considérons ensuite les produits de la troisième classe, et voyons combien il s’en trouve, dans cette classe, de l’espèce $[\alpha ,\beta ,n-\alpha -\beta ]\,;$ ne considérons d’abord que ceux d’entre eux qui renferment la lettre $a$ ; cette lettre doit y être suivie des $\alpha -1$ lettres qui lui sont consécutives, dans l’ordre alphabétique, et cette première série doit être combinée, avec tous les produits de seconde classe et de l’espèce $[\beta ,n-\alpha -\beta ]\,;$ que peuvent fournir les $m-\alpha -1$ dernières lettres, prises $n-\alpha$ à $n-\alpha$ ; changeant donc, dans $E_{2},$ $m$ et $n$ en $m-\alpha -1$ et $n-\alpha ,$ on aura, pour le nombre des produits de cette espèce qui renferment la lettre $a,$

${\frac {m-n}{1}}.{\frac {m-n-1}{2}}\,;$

changeant successivement $m$ en $m-1,m-2,\ldots n+2,$ dans cette formule, et sommant la série résultante, il viendra

$E_{1}={\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{3}}.$

Quant à $G_{1},$ il est clair qu’il sera égal à $E_{3}$ multiplié par le nombre des arrangemens dont $\alpha ,\beta ,n-\alpha -\beta$ sont susceptibles ; et, puisqu’en général le nombre de ces arrangemens est $1.2.3,$ on aura

$G_{3}=1.2.3.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{1}}.$

On pourrait facilement poursuivre de cette manière ; mais il est déjà facile d’apercevoir, et il est aisé de se convaincre, par un raisonnement rigoureux, qu’on doit avoir en général

$E_{p}={\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{3}}\ldots {\frac {m-n-p+2}{p}}.$

$G_{p}=1.2.3.\ldots p.{\frac {m-n+1}{1}}.{\frac {m-n}{2}}.{\frac {m-n-1}{3}}\ldots {\frac {m-n-p+2}{p}}.$

Mais il est essentiel de remarquer que cette dernière formule n’est exacte qu’autant que les nombres $\alpha ,\beta ,\gamma ,\ldots$ sont tous inégaux ; dans le cas où quelques-uns d’entre eux sont égaux, il arrive, en effet, que le nombre des arrangemens dont ils sont susceptibles se trouve diminué. Supposons donc que l’on ait $\alpha '$ nombres égaux à $\alpha ,$ $\beta '$ nombres égaux à $\beta ,$ $\gamma '$ nombres égaux à $\gamma ,$ et ainsi de suite ; ce qui donnera

$\alpha '+\beta '+\gamma '+\ldots =p\,;$

la valeur de $G_{p}$ deviendra alors^[2]

$G_{p}={\frac {1.2.3\ldots p}{1.2..\alpha '\times 1.2..\beta '\times 1.2..\gamma '\times \ldots }}.{\tfrac {m-n+1}{1}}.{\tfrac {m-n}{2}}\ldots {\tfrac {m-n-p+2}{p}}.$

En résumé, on voit qu’après avoir, décomposé la formule (A) en $n$ parties, dont chacune exprime combien il y a de produits qui répondent à une classe donnée, nous avons assigné le moyen de décomposer chacune de ces parties en plusieurs autres, dont chacune indique combien il existe, dans une classe déterminée, de produits d’un même genre ; et qu’enfin la formule qui exprime ce dernier nombre ; en y supprimant le coefficient, fait connaître le nombre des produits de chaque espèce dont chaque genre est composé. Ainsi on a

$C_{p}={\frac {n-1}{1}}.{\frac {n-2}{2}}.{\frac {n-3}{3}}\ldots {\tfrac {n-p+1}{p}}.{\tfrac {m-n+1}{1}}.{\tfrac {m-n}{2}}\ldots {\tfrac {m-n-p+2}{p}},$

$G_{p}={\frac {1.2.3\ldots p}{1.2..\alpha '\times 1.2..\beta '\times 1.2..\gamma '\times \ldots }}.{\tfrac {m-n+1}{1}}.{\tfrac {m-n}{2}}\ldots {\tfrac {m-n-p+2}{p}},$

$E_{p}=\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots .{\tfrac {m-n+1}{1}}.{\tfrac {m-n}{2}}\ldots {\tfrac {m-n-p+2}{p}}.$

Ces formules peuvent servir à résoudre les problèmes de probabilité que voici :

Étant donnés $m$ numéros $1,2,3,\ldots m,$ formant une loterie dont on extrait n numéros à chaque tirage ; déterminer,

1.^o Quelle est la probabilité que les n numéros d’un tirage formeront p séries de nombres consécutifs de la suite naturelle ?

2.^o Quelle est la probabilité que, parmi ces séries, il s’en trouvera $\alpha$ composées d’un nombre déterminé de numéros, $\beta$ composées d’un autre nombre déterminé de numéros, $\gamma$ d’un troisième nombre déterminé des numéros ; et ainsi de suite ?

3.^o Quelle est enfin la probabilité que ces diverses séries, considérées seulement par rapport au nombre des termes qui les composent, auront un ordre déterminé, parmi les nombres de la suite naturelle ?

Ces questions se résolvent, comme l’on sait, en divisant le nombre des tirages qui satisfont à leurs conditions, lequel nombre est l’une des formules ci-dessus, par le nombre total des tirages possibles.

On pourrait aussi demander quelle est la probabilité que les numéros propres à former un tirage d’une classe, d’un genre ou d’une espèce déterminés, sortiront dans un ordre déterminé. On résoudra cette question, en multipliant la probabilité que les numéros qui sortiront satisferont à la première condition, par la probabilité que ces numéros y satisfaisant, auront un ordre de sortie conforme à la seconde.

Nous n’étendrons pas plus loin ces considérations qui seraient susceptibles de bien d’autres développemens et applications, et nous terminerons par une réflexion qui, bien qu’elle ait déjà été faite plusieurs fois, ne paraîtra peut-être pas déplacée ici : c’est que, dans l’impossibilité où l’on est de prévoir les applications qu’on en pourra faire un jour, il ne faut pas être trop prompt à condamner les recherches purement spéculatives. Elles ont d’ailleurs l’avantage d’exercer utilement l’esprit et de le préparer ainsi à des recherches plus importantes.

1. Voyez, pour la sommation de cette série, la page 60 de ce volume.
2. Voyez le tome II des Annales, page 204.