CHAPITRE IV

LE CALCUL GOHBINATOIRB

253. — Le calcul combinatoïre, bien qn'il ait pour objet certaines propriélés relatives aux nombres, oa plue eiactament à des assemblages de nombres, ne faitpoint partie intégraDtederArithmilique classique. C'est au xvi* siècle seulement qu'il prit figure, et il fallait élre déjl famtliansé avec les notations algébriques pour avoir l'idée d'en exprimer les règles par des formules symboliques comme nous le Taisons aujourd'hui. Cette idée fut celle des savants de la Renaissance Paciuolo ('), Tartaglia (*), Cardan ('). Elle fut reprise au xvii* siècle par Fermât ('), Pascal (*), Frànicle (*), Huygens (^), qui établirent sur des bases solides les principes du nouveau calcul.

254. — Les questions qui relèvent du calcul combinatoire sont de celles que nous avons jouraellement l'occasion de nous poser.

{*) Summa de arithmtUce, 149a, Part. I, Jitt. 3, IracL 5.

(1) Gena-at Trattalo, i&5a, tl, liv. I, p. 17.

(3) Exatrelon maOïematieorum, iSja, prop. 170. Opéra, t. IV, p, SSy. — On trouve également les piemièrcB formulea du calcul comltituitoire dani un ouvrage françaii publié à Lyon «d i55<), la Logiatiea guae tt arilhmetiee vuigo dicUar de Buteo (de son vrai nom : Bobrel), p. JoS-Sag [Bibl. N.,y. 19.83).

(*j Correspondance avec Pascal, i6i>4. (Œuv. de Patcal, t. III, p. 367 «qq.}.

{') Ibid. et dans le Traité duTriangle Arilhmitîgue omc quelques autret petit» traité» »w la mime matière, écrit par Pascal en idh^ {Œuv. III, p. 43^^ sqq.)-

(') Abrégé des eombinai»ona imprimé en i6g3, ap. Divers ouvr.de Math, et de Phys. par Messieurs de l'Ac. Royale de» Sciences.

Ci De ralioeiniis in ludo aléas, 1637, imprimé à la fin de Exercitalione» tnathtmalicae de Fbançois Schootem [Bihl. N., V. CaSg).

îbO LE CALCrt COMBI.IATOinE

Déjà, a'ii faut en croire Plutarque, le pliilosoplie Xénocratc se demaDdait, au iv' siècle av. J.-C, combien de syllabes on peut composer avec les lettres de t'alphabel. Plus précisément, cherchons combien il peut exister de mois composés de trois ou de quatre lettres (étant admis ou n'étant pas admis que la même lettre peut figurer plusieurs fois dans le même mot) ; demandons-nous de combien de manières diCTéren tes peuvent être placés douze convives autour d'une table ; proposons-nous de trouver les diverses combinaisons de chiffres que peut amener un joueur avec deux, ou trois, ou quatre dés ; cherchons le nombre de boulets sphériques que l'on peut placer dans une pile de forme pyrnniidale. Ce sont là des problèmes qui se résolvent tous au moyen des mêmes formules, — formules simples, claires, et dont l'application se fait pour ainsi dire mécaniquement.

Etant donné ces qualités, il n'est point surprenant que le calcul combinatoire ait été considéré, dès son origine, comme l'un des plus précieux instruments de la science mathématique. Quelles ne furent pas les espérances suscitées par lui I N'est-ce point le calcul combinatoire qui inspire au Père Mersenne ce rave insensé de déterminer mathématiquement les plus belles des mélodies ?

Mersenne est frappé de ce fait que toute mélodie est une combinaison de sons ou d'intervalles, de même qu'un discours est une combinaison de mots composés eux-mêmes avec les vingt-quatre lettres de l'alphabet. Ne pourrait -on, dès lors, formera l'avance toutes les combinaisons fournies parles notes de la gamme? On construirait ainsi mécaniquement la totalité des mélodies possibles, et parmi ces mélodies on recueillerait les plus belles. C'est ainsi que Mersenne est conduit à écrire un chapitre intitulé : Dans let/ael il est Irailé des beaux airs et des beaux chants et montré s'il est possible de faire un chant sur un sujet donné qui soit le plus beau de tous ceux qui puissent être faits sur le même sujet ('),

255. — Passant du domaine de l'utopie à celui de la fantaisie, nous trouvons le calcul combinatoire k la base des problèmes de société auxquels on donne souvent le nom de récréations mathé-

{') La Virili de» Sciences contre les sceptique» et pyrrhonieTU, [625, chap. X [fiiU. A'., R. t)G68).

LE CALCUL COHBIKATOinE 96l

maliques. Un recueil en fut Tait au xvii* siècle, qui fut complété par Mydorge et Henrion ('). Des recueils plus étendus, tels que celui d'Ozanam, parurent au xtiii* et xix* siècle [le dernier en date est celui de Rouse-Ball et Filz- Patrick {')].

Ozanain nous propose par exemple les problèmes suivants (') : Six personnes devant dîner ensemble, il s'élève entre elles un combat de politesse (') ; enfin, quelqu'un, voulant terminer In contestation, propose de se mettre à table comme ton se trouve sauf à diner ensemble le lendemain et les jours suivants jusqu'à ce que Ton ait épuisé tous tes arrangements (^) possibles. On demande combien de dîners devront être donnés pour cet effet. — Et plus loin : De combien de manières peut-on, en conservant la mesure, varier ce vers : Toi libi sunt dotes virgo quoi sidcra cœlo ?

256. — Mais ce ne sont là qu'amusements et curiosités. L'intérât véritable du calcul combinaloire tient aux services éminents qu'il a rendus à l'alf^èbre et au calcul des probabilités. 11 sera question des premiers dans notre Deuxième livre, et des seconds nous dirons un mot à la fin du présent parsgrapbe. Il nous faut auparavant faire connaître et démontrer les formules combinatoires fondamentales.

367. Pemrotatioiis. — Considérons trois objets distincts que nous pouvons désigner par une même lettre a affectée des indices I, a, 3 — c'est-à-dire par les symboles Oi. fli. «a-

Ecrivons ces 3 symboles (je tes appellerai « lettres » pour simplifier le langage) à côté les uns des autres dans des ordres divers : je puis écrire :

ù,ata, ou a,aiai ou a^aiai ou ataja, ou a^ajH, ou a^atHi-

{') 5* et demièTB éd. en 1670 [Bibi. N., V. tSàtfi).

|i) RicriaU malhim. (irad. Iranç., chez llermann, 3 vol., 3° édit., 1907-01)].

1') Récréât. nuUliém., a» éd., t. I, Pari», 1778, p. 901 et suiv, {Bibl. N., V. i83i6).

(♦) • C'eat probablement — remarque Ozan&u en note — dans quelque ville de province éloignée de la capitale •.

(') Le mot E arrangement n. eat pris par Ozanah dans le sens de c combinaison i.

LE CALCUL COUBINl.TOimB

Ces divers groupements des trois lettres a,, a,, a, écrites dans des ordres diSfêrenta sont appelés permalations (') des trois lettres ; ce qui veut dire tpi'oa passe d'un groupement à un autre en permutant, ou échangeant entre ellas, les lettres a,, a,, a, : ainsi, pour passer du groupement a,ataa au groupement OxOta^, je fais passer la lettre a, à la place qu'occupait a, et inversentent.

Il est Tacile de vérifier qu'il n'existe point d'autre ordre possible poOT les lettres a„ a„ a, que Us six ordres indiqués ci-dessus; d'où je conclus que les trois lettres a,, Oj, a^ comportent six permalations.

On peut démontrer ce fait a priori en déterminant plus généralement le nombre des permufalions de lettres en nombre quelconque.

Considérons m objets désignés par des lettres affectées d'indices

Nous appelleroDs permulalioiit de ces m lettres tous les groupements que l'on peut former en plaçant ces m lettres à la suite les unes des autres dont des ordres différenit. Ainsi, les groupements

oïd, ... a„^,a„, atOtOi ..■ <iM^,a«, etc.

sont des permutations des m lettres. — Cela posé, nous allons démontrer le théorème suivant :

258. Théorème. — Le nombre des permutations de m lettres est égal au produit des m premiers nombres, c'est-à-dire au produit I X 2 X 3 ... X m.

Pour démontrer ce théorème, nous emploierons la méthode dite récurrente ('), qui est devenue depuis Pascal l'une des plus importantes méthodes mathématiques ; nous montrerons que si le théorème est vrai pour une certaine valeur de m, il est vrai pour la suivante (or il est vrai pour m = i ; donc il est vrai quel que soit m).

(') Le mot permuîatio a été employé pour la première fois par Jacques BEitHOUii.Li, Ar» Conjectandi op. poatiiumum, Bàle, 1713, a' part., ch. i

(p- T-il-

I*) Le mathématicien «icilieii Mauhulyco (i494~i^7''>] avait déjà employé cette méthode.

ut CALCiiL oojiai.NA'nHRE a63

2M. -~ Supposons dooc qu'il ait été déjJt démoatri que le nombre des permutations de m — i lettres est i x 3 ■-• X (m -^ i) et désignons, pour abréger, ce nombre par ?„,,. Nous avons à établir que le nombre — soit Pm — des permutations de m lettres est égal à m.P„,.

Or on obtiendra évidemment toutes les permutations des lettres ai, .... um eo procédant de la manière suivante :

Plaçons la lettre a, en tète, et à ta suite les (m — i) lettres Oi, .... Oh-i, a„ dans tous les ordres possibles. Nous obtiendrons ainsi autant de permutations (de nos m lettres) qu'il y a de manières de disposer les ni — i lettres oi, .... a„, c'esl^-dire P«,. Ce sont là toutes les permutations des m lettres données où <i, occupe la première place.

Considérons encore toutes les permutations des m — i lettres O), .... a, et dans chacune intercalons a, à la seconde place (après la première lettre h gauche). Nous obtenons ainsi Pn i nouvelles permutations des m lettres : ce sont toutes les permutations où a, occupe la seconde place.

Nous aurons de même Pu>-i permutations des m lettres, où ai occupe la troisième place, el ainsi de suite; finalement Ph-i permutations où a, occupe la /n"™ (dernière place).

Les diverses permutations ainsi obtenues sont au nombre de m fois P,.i : elles constituent la totalité des permutations des m lettres. Donc

comme nous l'avions annoncé. Cette formule est valable pour toutes les valeurs de l'entier m.

Mais une lettre n'a évidemment qu'une permutation, donc Pi = I. La Formule (i) nous donne alors

d'où

d'Où