Annales de mathématiques pures et appliquées/Tome 07/Combinaisons, article 1

Recherche du nombre des permutations dont plusieurs choses sont susceptibles, lorsqu’elles sont disposées circulairement, et qu’elles ne sont pas toutes dissemblables ; par M. J. B. Durrande.

Annales de mathématiques pures et appliquées, 7, 1817 (p. 334-344).

QUESTIONS RÉSOLUES.

Solution pratique du problème de combinaison proposé
à la page 188 de ce volume ;

Par M. J. B. Durrande.

≈≈≈≈≈≈≈≈≈

I. Il est bien connu, depuis long-temps, que des lettres $\mathrm {P,Q,R} ,\ldots$ toutes différentes les unes des autres, et au nombre de $m,$ peuvent être disposées, en ligne droite, les unes à la suite des autres, d’un nombre de manières exprimé par $m!$^[1].

2. Si l’on veut savoir de combien de manières différentes ces mêmes lettres peuvent être disposées, circulairement, les unes à la suite des autres ; on considérera qu’un arrangement circulaire quelconque étant donné ; on peut le rompre en $m$ points différens pour l’étendre en ligne droite ; que par conséquent chaque arrangement circulaire fournit $m$ arrangemens rectilignes différens ; et qu’ainsi le nombre des arrangemens circulaires est $m$ fois moindre que celui des arrangemens rectilignes ; d’où il suit (1) que le nombre total des arrangemens circulaires doit être simplement ${\frac {m!}{m}}$ ou $(m-1)!.$

3. On peut confirmer ce résultat par un raisonnement inverse du précédent. Concevons que, dans un arrangement rectiligne quelconque on fasse passer $\mathrm {m} -1$ fois consécutivement la première lettre à la dernière place, sans intervertir aucunement l’ordre des autres ; on obtiendra ainsi $m$ arrangemens rectilignes différens, que l’on ne ferait que reproduire sans cesse, si l’on voulait pousser plus loin l’application du procédé. Il suit de là évidemment que les $m$ arrangemens rectilignes différens que nos $m$ lettres sont susceptibles de fournir, peuvent être répartis en $m$ groupes de ${\frac {m!}{m}}$ ou $(m-1)!$ arrangemens tels que les arrangemens de chaque groupe seront ainsi déduits les uns des autres par le passage continuel de la première lettre à la dernière place. Or, il est clair que les divers arrangemens rectilignes d’un même groupe ployés en cercle donneront toujours le même arrangement circulaire ; d’où il suit que le nombre des arrangemens circulaires différens sera uniquement égal au nombre des groupes ; c’est-à-dire, qu’il sera-ou ${\frac {m!}{m}}$ ou $(m-1)!,$ comme nous l’avons déjà trouvé ci-dessus.

4. Voilà ce qui arrive, lorsque les lettres $\mathrm {P,Q,R} ,\ldots$ sont toutes différentes les unes des autres, ou, ce qui revient au même, lorsqu’il n’y en a qu’une seule de chaque sorte. Mais, on peut supposer que, dans la totalité de $m$ lettres dont il s’agit, il se trouve $p$ lettres pareilles à $P,\ q$ lettres pareilles à $Q,\ r$ lettres à $R,$ et ainsi des autres ; de sorte qu’on ait $p+q+r+\ldots =m.$ Il est connu qu’alors^[2] le nombre des arrangemens rectilignes différens dont nos $m$ lettres seront susceptibles ; ou, ce qui revient au même, le nombre des manières différentes dont elles pourront être disposées en ligne droite les unes à côté des autres, sera exprimé par la formule

${\frac {m!}{p!q!r!\ldots }}.$

5. On peut demander présentement, comme nous l’avons fait dans le premier cas, de combien d’arrangement circulaires, réellement différens, ces mêmes lettres pourront être susceptibles ; et il semblerait, au premier abord, que les raisonnemens que nous avons faits alors (2, 3) doivent conserver ici toute leur force, et qu’ainsi la formule qui répond à la question proposée doit être

${\frac {m!}{m(p!q!r!\ldots )}},$ ou ${\frac {(m-1)!}{p!q!r!\ldots }}.$

Cette formule est, en effet, celle qui résout la question, dans le cas particulier où les nombres $p,q,r,\ldots ,$ sont premiers entre eux ; c’est-à-dire, dans le cas où il ne se trouve d’autres diviseurs que l’unité qui leur soient communs à tous.

6. Mais, dans le cas contraire, c’est-à-dire, dans le cas où quelque nombre, autre que l’unité, divise à la fois tous les nombres $p,q,r,\ldots$ et par conséquent le nombre $m,$ notre raisonnement cesse d’être applicable ; et la formule se trouve tout-à-fait en défaut. Elle offre même souvent alors un préservatif contre les applications inconsidérées qu'on prétendrait en faire, en donnant, pour le nombre des arrangemens cherché, un nombre essentiellement fractionnaire ; ce qui, dans une question de ce genre, est un signe manifeste d’absurdité. C’est, en particulier, ce qui arrive, lorsqu’on suppose toutes les $m$ lettres égales entre elles et à $\mathrm {P} .$ La formule se réduit alors, en effet, à ${\frac {1}{m}}$ qui, excepté le seul cas où $m=1,$ est nécessairement fractionnaire.

7. Il est très-aisé de concevoir pourquoi, dans le cas dont nous parlons, la formule ne saurait être applicable. Lorsqu’en effet les nombres $p,q,r,\ldots$ ont un ou plusieurs diviseurs autres que l’unité qui leur sont communs à tous ; parmi les arrangemens circulaires dont nos lettres sont susceptibles, il doit nécessairement s’en trouver de périodiques ; or, ce qui est vrai des premiers cesse de l’être pour ceux-ci, c’est-à-dire, qu’en les rompant successivement en deux points différens, pour les étendre en ligne droite, on ne forme pas toujours deux arrangemens rectilignes distincts : cela n’a lieu en effet, que lorsque les deux points de rupture ne sont pas des points semblablement placés dans deux périodes différentes, des points homologues de ces périodes.

8. Il y a donc lieu à proposer la question suivante dont nous ne nous proposons de donner ici, pour le présent, que la solution pratique ; nous réservant de développer les raisonnemens qui nous y ont conduit dans un prochain numéro.

9. PROBLÈME. On a $\mathrm {m}$ lettres, parmi lesquelles il se trouve des $\mathrm {P}$ en nombre $\mathrm {p} ,$ des $\mathrm {Q}$ en nombre $\mathrm {q} ,$ des $\mathrm {R}$ en nombre $\mathrm {r} ,$ et ainsi des autres ; en sorte qu’on a $\mathrm {p+q+r} +\ldots =\mathrm {m} .$ De combien de manières ces $\mathrm {m}$ lettres peuvent-elles être disposées circulairement les unes à côté des autres ?

10. Solution. I. Soit $D$ le plus grand commun diviseur des nombres $p,q,r,\ldots ,$ et soit

$D=a^{\alpha }b^{\beta }c^{\gamma }\ldots \,;$

$a,b,c,\ldots$ étant des nombres premiers essentiellement différens.

II. Soit formé le produit

$\left(1+a+a^{2}+\ldots +a^{\alpha }\right)\left(1+b+b^{2}+\ldots +b^{\beta }\right)\left(1+c+c^{2}+\ldots +c^{\gamma }\right)\ldots ,$

dont les termes, au nombre de $(\alpha +1)(\beta +1)(\gamma +1)\ldots ,$ sont, comme l’on sait, tous les diviseurs de $D,$ pris une seule fois chacun.

III. Soit désignée par $f$ une fonction d’un nombre quelconque $k,$ dont la définition soit

$f(k)={\frac {\left({\frac {m}{k}}\right)!}{\left({\frac {p}{k}}\right)!\left({\frac {q}{k}}\right)!\left({\frac {r}{k}}\right)!\ldots }},\quad$d’où$\quad f(1)={\frac {m!}{p!q!r!\ldots }}.$

IV. Soit enfin

$a^{\alpha '}b^{\beta '}c^{\gamma '}\ldots$

le terme général de la suite que forment les diviseurs de $D$ ; de sorte qu’on puisse en déduire tous ces diviseurs, en donnant successivement à chacun des exposans $\alpha ',\beta ',\gamma ',\ldots$ toutes les valeurs entières, positives ou nulles, que permettront les conditions

$\alpha '<\alpha +1,\quad \beta '<\beta +1,\quad \gamma '<\gamma +1,\ldots$

V. Alors le nombre d’arrangemens circulaires cherché sera la somme des termes d’une suite de $(\alpha +1)(\beta +1)(\gamma +1)\ldots$ termes, dont le terme général sera

${\frac {a^{\alpha '-1}b^{\beta '-1}c^{\gamma '-1}\ldots (a-1)(b-1)(c-1)}{m}}f(a^{\alpha '}b^{\beta '}c^{\gamma '}\ldots ).$

et qui devra conséquemment renfermer tous les termes de cette forme qui pourront être formés sous les conditions ci-dessus énoncées.

11. Remarque I. Si le plus grand commun diviseur $D$ des nombres $p,q,r,\ldots$ était simplement le produit $abc\ldots$ de plusieurs nombres premiers, inégaux, le terme général de la suite deviendrait simplement

${\frac {(a-1)(b-1)(c-1)}{m}}f(abc\ldots )$

dans lequel on devrait successivement admettre et rejeter une ou plusieurs des lettres $a,b,c,\ldots \,;$ en sorte que le nombre cherché serait de la forme

${\begin{alignedat}{2}{\frac {1}{m}}f(1)+&{\frac {a-1}{m}}f(a)+&{\frac {(a-1)(b-1)}{m}}f(ab)+&\ldots \\+&{\frac {b-1}{m}}f(b)+&{\frac {(a-1)(c-1)}{m}}f(ac)+&\ldots \\+&{\frac {c-1}{m}}f(c)+&{\frac {(b-1)(c-1)}{m}}f(bc)+&\ldots \\+&\ldots \ldots \ldots +&\ldots \ldots \ldots \ldots \ldots \ldots +&\ldots \end{alignedat}}$

12. Remarque II. Si le plus grand commun diviseur $D$ des nombres $p,q,r,\ldots$ était simplement une puissance $a^{\alpha }$ d’un nombre premier $a,$ le terme général de la suite deviendrait

${\frac {a^{\alpha '-1}(a-1)}{m}}f\left(a^{\alpha '}\right)\,;$

cette suite serait donc

${\tfrac {1}{m}}f(1)+{\tfrac {a-1}{m}}f(a)+{\tfrac {a(a-1)}{m}}f(a^{2})+{\tfrac {a^{2}(a-1)}{m}}f(a^{3})+\ldots +{\tfrac {a^{\alpha -1}(a-1)}{m}}f(a^{\alpha })$

13. Remarque III. Si le plus gçand commun $D$ des nombres $p,q,r,\ldots$ était l’unité, c’est-à-dire, si ces nombres étaient premiers entre eux, alors $\alpha ,\beta ,\gamma ,\ldots$ seraient nuls ; et la formule se réduirait à son premier terme

${\frac {1}{m}}f(1)\quad$ou$\quad {\frac {m!}{m(p!q!r!\ldots )}},$

ainsi que cela doit être (5).

14. Remarque IV. Si enfin les $m$ lettres données étaient toutes égales entre elles et à $P$ ; on aurait $p=m,$ et les nombres $q,r,\ldots$ n’existeraient pas ; on aurait donc

$f(k)={\frac {\left({\frac {m}{k}}\right)!}{\left({\frac {m}{k}}\right)!}}=1\,;$

toutes les fonctions désignées par f se réduiraient donc à l’unité ; et, comme, dans ce cas, le nombre cherché doit évidemment être l’unité ; il s’ensuit que, si l’on a un nombre $m,$ tel que $m=a^{\alpha }b^{\beta }c^{\gamma }\ldots \,;\ a,b,c\ldots$ étant des nombres premiers inégaux, la suite dont le terme général sera égal à

$a^{\alpha '-1}b^{\beta '-1}c^{\gamma '-1}\ldots (a-1)(b-1)(c-1)\ldots \,;$

dans laquelle on admettra successivement pour $\alpha ',\beta ',\gamma ',\ldots$ toutes les valeurs entières, positives ou nulles qui n’excèderont pas respectivement $\alpha ,\beta ,\gamma ,\ldots ,$ sera égale au nombre $m$ lui-même.

15. Exemple. Soit $\mathrm {D} =a^{2}b.$

Les diviseurs de $\mathrm {D}$ seront, dans ce cas, les termes du développement du produit

$(1+a+a^{2})(1+b),$

c’est-à-dire,

$1,\quad a,\quad a^{2},\quad a^{2}b.$

$b,\quad ab$

En représentant donc par $x$ le nombre cherché, on aura

${\begin{aligned}x={\frac {1}{m}}f(1)&+{\frac {a-1}{m}}f(a)+{\frac {a(a-1)}{m}}f(a^{2})+{\frac {a(a-1)(b-1)}{m}}f(a^{2}b)\\&+{\frac {b-1}{m}}f(b)+{\frac {(a-1)(b-1)}{m}}f(a^{2}b)\\\end{aligned}}$

c’est-à-dire,

${\begin{aligned}x={\frac {1}{m}}.{\frac {m!}{p!q!r!\ldots }}&+{\frac {a-1}{m}}.{\frac {\left({\frac {m}{a}}\right)!}{\left({\frac {p}{a}}\right)!\left({\frac {q}{a}}\right)!\left({\frac {r}{a}}\right)!\ldots }}\\&+{\frac {b-1}{m}}.{\frac {\left({\frac {m}{b}}\right)!}{\left({\frac {p}{b}}\right)!\left({\frac {q}{b}}\right)!\left({\frac {r}{b}}\right)!\ldots }}\\\end{aligned}}$

$+{\tfrac {a(a-1)}{m}}.{\frac {\left({\frac {m}{a^{2}}}\right)!}{\left({\frac {p}{a^{2}}}\right)!\left({\frac {q}{a^{2}}}\right)!\left({\frac {r}{a^{2}}}\right)!\ldots }}+{\tfrac {a(a-1)(b-1)}{m}}.{\frac {\left({\frac {m}{a^{2}b}}\right)!}{\left({\frac {p}{a^{2}b}}\right)!\left({\frac {q}{a^{2}b}}\right)!\left({\frac {r}{a^{2}b}}\right)!\ldots }}$

$+{\tfrac {(a-1)(b-1)}{m}}.{\frac {\left({\frac {m}{ab}}\right)!}{\left({\frac {p}{ab}}\right)!\left({\frac {q}{ab}}\right)!\left({\frac {r}{ab}}\right)!\ldots }}$

16. Application. On demande de combien de manières différentes on peut arranger autour d’une table ronde $36$ assiettes dont $12$ de vermeil et $24$ de porcelaine ?

On a ici $m=36,\ p=24,\ q=12\,;$ d’où $\mathrm {D} =12=2^{2}.3$ ; donc $a=2,\ b=3,\ \alpha =2,\ \beta =1.$ En conséquence, la précédente formule deviendra

$x={\frac {1}{36}}.{\frac {36!}{24!12!}}+{\frac {1}{36}}.{\frac {18!}{12!6!}}+{\frac {2}{36}}.{\frac {9!}{6!3!}}+{\frac {4}{36}}.{\frac {3!}{2!1!}}$

$+{\frac {2}{36}}.{\frac {12!}{8!4!}}+{\frac {2}{36}}.{\frac {6!}{4!2!}}$

Le premier terme revient à

${\frac {25.26.27.28.29.30.31.32.33.34.35}{2.3.4.5.6.7.8.9.10.11.12}}=7.13.17.25.29.31.$

Le second revient à

${\frac {1}{2}}.{\frac {13.14.15.16.17}{2.3.4.5.6}}={\frac {7.13.17}{3}}.$

Le troisième revient à

${\frac {2}{3}}.{\frac {9.10.11}{2.3.4}}={\frac {5.11}{2}}.$

Le quatrième revient à

${\frac {1}{2}}.{\frac {7.8}{2.3}}={\frac {2.7}{3}}.$

Le cinquième revient à

${\frac {1}{3}}.{\frac {5}{2}}={\frac {5}{2.3}}.$

Enfin, le sixième revient à

${\frac {1}{3}}.1={\frac {1}{3}}.$

La somme des termes fractionnaires revient à $549,$ et comme d’ailleurs le terme entier est $34768755$ ; on a définitivement

$x=34769304.$

17. Nous placerons ici tous les résultats que l’on obtient jusqu’à $m=6,$ pour les divers assemblages de lettres qu’on peut former sans excéder cette limite ; ce sont aussi les résultats les plus usuels : nous y ajoutons en regard, sous la dénomination de $y,$ le nombre des arrangement rectilignes correspondans.

${\begin{alignedat}{4}&{\text{Pour P seul}}\ldots \ldots &&x=&1,&\ \ y=&1,&\\&{\text{Pour PQ}}\ldots \ldots &&x=&1,&\ \ y=&2,&\\&{\text{Pour PPP}}\ldots \ldots &&x=&1,&\ \ y=&1,&\\&{\text{Pour PPQR}}\ldots \ldots &&x=&2,&\ \ y=&6,&\\&{\text{Pour PPPQ}}\ldots \ldots &&x=&1,&\ \ y=&3,&\\&{\text{Pour PPPP}}\ldots \ldots &&x=&1,&\ \ y=&1,&\\&{\text{Pour PPQRS}}\ldots \ldots &&x=&6,&\ \ y=&24,&\\&{\text{Pour PPPQR}}\ldots \ldots &&x=&3,&\ \ y=&12,&\\&{\text{Pour PPPQQ}}\ldots \ldots &&x=&2,&\ \ y=&6,&\\&{\text{Pour PPPPQ}}\ldots \ldots &&x=&1,&\ \ y=&4,&\\&{\text{Pour PPPPP}}\ldots \ldots &&x=&1,&\ \ y=&1,&\\&{\text{Pour PPQRST}}\ldots \ldots &&x=&\ \ 24,&\ \ y=&120,&\\&{\text{Pour PPPQRS}}\ldots \ldots &&x=&12,&\ \ y=&60,&\\&{\text{Pour PPPQQR}}\ldots \ldots &&x=&6,&\ \ y=&30,&\\&{\text{Pour PPPPQR}}\ldots \ldots &&x=&4,&\ \ y=&20,&\\&{\text{Pour PPPPQQ}}\ldots \ldots &&x=&2,&\ \ y=&10,&\\\end{alignedat}}$

${\begin{alignedat}{4}&{\text{Pour PPPPQ}}\ldots \ldots &&x=&1,&\ \ y=&5,&\\&{\text{Pour PPPPP}}\ldots \ldots &&x=&1,&\ \ y=&1,&\\&{\text{Pour PQRSTU}}\ldots \ldots &&x=&120,&\ \ y=&720,&\\&{\text{Pour PPQRST}}\ldots \ldots &&x=&60,&\ \ y=&360,&\\&{\text{Pour PPQQRS}}\ldots \ldots &&x=&30,&\ \ y=&180,&\\&{\text{Pour PPPQRS}}\ldots \ldots &&x=&20,&\ \ y=&120,&\\&{\text{Pour PPQQRR}}\ldots \ldots &&x=&16,&\ \ y=&90,&\\&{\text{Pour PPPQQR}}\ldots \ldots &&x=&10,&\ \ y=&60,&\\&{\text{Pour PPPPQR}}\ldots \ldots &&x=&5,&\ \ y=&30,&\\&{\text{Pour PPPQQQ}}\ldots \ldots &&x=&4,&\ \ y=&20,&\\&{\text{Pour PPPPQQ}}\ldots \ldots &&x=&3,&\ \ y=&15,&\\&{\text{Pour PPPPPQ}}\ldots \ldots &&x=&1,&\ \ y=&6,&\\&{\text{Pour PPPPPP}}\ldots \ldots &&x=&1,&\ \ y=&1.&\\\end{alignedat}}$

Il est essentiel de remarquer qu’ici nous regardons et devons regarder, en effet, comme arrangemens distincts deux arrangemens inverses l’un de l’autre ; deux arrangemens dont l’un devient l’autre, en le renversant le dessus en dessous ; deux arrangemens, en un mot, formés d’un même arrangement rectiligne qu’on aurait successivement ployé en cercle, en le courbant dans deux sens opposés.

18. Si, par exemple, on voulait savoir de combien de manières différentes trois hommes et trois femmes, sans distinction d’individu à individu, dans le même sexe, peuvent être placés autour d’une table ronde ? Cette question se rapporterait au cas $\mathrm {PPPQQQ}$ de notre tableau, et conséquemment le nombre des arrangement possibles serait $4.$

19. Le premier terme de notre formule générale étant le nombre des arrangemens circulaires qui auraient lieu dans le cas où les périodes seraient impossibles, et les termes qui suivent celui-là étant tous positifs ; il en résulte cette conséquence, pour ainsi dire paradoxale, que l’existence possible des périodes, loin de diminuer le nombre total des arrangemens, comme il semblerait résulter de ce que nous avons dit (7), le rend au contraire plus grand.

20. Ceux qui penseraient que la complication de nos méthodes n’est point suffisamment rachetée par l’utilité des résultats qu’on en obtient, montreraient par là qu’ils ignorent que tout problème de combinaison est en même temps un problème de probabilité ; et que, dans ceux du genre de celui-ci, le calcul intégral aux différences ne paraît pas pouvoir être d’un utile secours.

Les problèmes de combinaison sont d’ailleurs un sujet d’exercice d’autant plus utile, que rien n’est plus aisé que de commettre des paralogismes en essayant de les résoudre.

1. J’emploie ici $m!,$ avec M. Kramp, comme abréviation de $1.2.3\ldots m\,;$ et j’en userai de même dans toute la suite de cet article. On a lieu d’être surpris qu’une notation si simple, et conséquemment si utile, ne soit point encore universellement adoptée.
2. Voyez, en particulier, la page 201 du tome II.^e de ce recueil.