I. — Sur la partition des polygones (n

D'après une communication qui nous a été adressée par M. Cayley, le ihéorcme énoncé à la page 93 doit être attribué à Kirkma>'N, qui l'a démontré dans son Mémoire : On the k-partitions of the r-goncj publié dans les Philosophical Transactions (t. CXLVïï; Londres, iSdj).

D'autre pari, nous avons reçu de M. Élie Perrin, professeur à l'École J.-B. Say, les remarques suivantes: Soit ABG...HKL un polygone de (/i H- i) côtés; choisissons AB pour base principale, et désignons par «i, aj, aj, . . . , a» les côtés BC, CD, DE, . . . , KA. Si, par exemple, le triangle ABG fait partie d'une décomposition, le sommet G décompose le périmètre BCD...GHK en deu\ polygones ayant pour bases principales BG et AG, qui remplacent AB ; de même, si le triangle BGE fait partie d'une décomposition, il sépare le polygone BCDEG en deux autres, et ainsi de suite; on classe ainsi, die ho fornique ment y les (/i — i) sommets du polygone, autres que A et B.

Plaçons, sur une ligne horizontale, les côtés

ai, «1, û5j, . . . , ûi/i,

et supposons, pour fixer les idées, que n est égal à 8. Si le point G fait partie de la décomposition, il sépare aj de a^ et nous représenterons cette première décomposition par

(ai, aj, as, a*, aj), (ae, a?, a%)\

puis, si BGE fait partie de la décomposition, nous séparerons ai, . . . , as en deux par

(^lai, aj, as), (a^, as)), (ag, a?, ag),

et ainsi de suite. Par conséquent, si l'on considère la décomposition du polygone de 9 côtés, dans laquelle on a tracé les diagonales GK, GA, GB, GE, BE, CE, on peut représenter cette décomposition par le symbole

(((ai\ (aj, a,)\ (a^, as)), ((a^, a-), (as)), ou

ai, aj, as, a^, aj, ae, a?, ag.

ty/ 50T£? ET A»»I7I->^*.

f^'iT* n . a^ n . a*, c-ir r. — : a i.:l:L-»ti«:i* i-* i-Mi. fi.t-tarr. en

«fft'.tiiat *-ï;**At »'■■,.• ir-ï -i-t^ i-.'i-:»?*- «tî .3.î-:r*-Mn';aî. Par : ■x?** ^icaî :

a^. au. moyen d^ a — i muf^-fl^^atù^tu d^ d^uj' •'i^r-V^r*. y-rtf

dafLî t ^^rdre det i a di-^ et. ett è^'ti a'i ftofnhre des de^.i mf< s t •;.-. nj d 'Jf^ poir/ron^ ron^ere de n — î rOr^i ^.i frûjnzUâ. f<tr du di^isonales qui ne te roupent pa.t *i l intérieur du f^jlyz'jne.

On et% A^-A'vW f^ril^m^tal •.rX iu'fr tri----rrine : £.-? nf^mbre du manières d'effectuer le produit de n facteur t. au moyen de n — i multip(i<nti/>ns de deux /acteur t pris dam un ordre quelconque, est èsal au pn:duit du nombre des décompositions du polygone de n — i e*%t*t '^n triançlet. f^ar le nombre n\ de% permutations des n facteurs.

¥iz. 7*

La figure ci-jointe nous montre encore que le nombre deâ manières d'interpréter une fraction élagée de n termes « n' Si. Ex. II} est égal au nombre des décompositions d'un polv^one de <'/i — 1 1 côtés en triangles.

Kt ain<>i le nombre des classement*, par voie dichotomique, de n objets rangés dan« un certain ordre, est égal au nombre des décompositions d'un poIv((one de C/i — i; côtés en triangles, par ( /i — i) diagonales qui ne se coupent pas à l'intérieur du polygone.

n. Sur le problème des rencontres (n** 1*23).

Le nombre Q« des permutations de n lettre.»', où aucune lettre n'occupe la place que lui assigne son rang dans l'alphabet, est égal au nombre des <>iibstitutions irréductibles de n lettres.

Cette même qucî^tion a été traitée par Laplace et généralisée, au moyen de la théorie des fonctions génératrices, dans la Théorie analytique des l'rohahilités {(JE livres, t. VII, p. 'i^i).

De la formule

NOTES ET ADDITIONS. îgi

on déduit, en remplaçant n successivement par i, u, .. .. /i, et en faisant la somme des égalités obtenues,

Q„+., = S/iQ„-i-const.,

la constante étant égale à o ou à i, suivant que n est pair ou impair.

On peut obtenir diverses propriétés arithmétiques des nombres Q^. On remarque d*abord que deux nombres consécutifs sont premiers entre eu\, par suite de la formule {-x) du n** J23. De plus, Q,i-ki est divisible par /î, comme cela résulte de la première formule de la page ai 3. De la formule symbolique

on déduit la formule générale

/(P-f-:r)çA,/(Q-t-:r-f-i), et, par exemple, en supposant

il vient

et pour X = o

F'-(P — i/çA-QjfQ-Hi)'-.

Si Ton remplace r par un nombre premier/?, en observant que F'^ est divisible par /?, pour /i ^/?, et en tenant compte des restes du triangle arithmétique, il vient

Q/>+5 "" — Q.< < mod./?); on en tire, plus généralement,

Qa/>+^ =3 ( — I y* Q, ( mod . p ), et ainsi les restes de Q» par/? se repro<luisent périodiquement.

m. — Sur le problème des ménages (n*> 123).

Nous désignerons par F et H, avec les indices de i à /i, les n femmes et leurs maris respectifs; puis, par

\n 1^ nombre des permutations des n ménages qui sont conformes à

l'énoncé; fi,4 » qui présentent le seul défaut de finir

par I ;

v,| le nombre des permutations qui présentent un seul défaut, à re\-

ception de commencer ou de finir par I, ou de finir par n\

p„ » qui se terminent par i et présentent un

seul autre défaut.

Supposons que les n ménages soient assis autour de la table dans Tune des X;, dispositions cherchées et que survienne un ménage que nous désignerons par F;,+i et Il/i+i ; alors les convives se serrent de manière à ouvrir deux nouvelles places formant un intervalle que nous pouvons imaginer situé immédiatement à gauche de Ft. Alors F«+i se place dans cet intervalle, et si son mari sV plaçait, la permutation serait fautive; mais le mari Un-hi peut changer de place avec les n maris, à Texception de deux. Hi et celui qui est à la gauche de Fi. Par conséquent, par cette intercalalion, nous obtenons (n — a)/./» dispositions. Mais on peut encore obtenir d'autres permutations, conformes à l'énoncé, en commençant par les permutations fautives de n ménages, que nous avons désignées par {X|,,

i" Supposons que, dans la permutation qui précède l'arrivée des nouveaux venus, le mari IIi soit à la gauche de sa femme Fi ; dans ce cas, le ménage d'indice (n-r-i) peut se placer à la gauche de Fii mais le mari 11/,+.! doit échanger sa place avec l'un quelconque des maris, à l'exception de Hj; on obtient ainsi (n — Ol'^n permutations des ménages.

2" Supposons que la permutation qui précède l'arrivée des nouveaux venus soit une de celles que nous avons désignées parv„, alors le ménage d'indice (n -j- i), se plaçant à la gauche de Fi, la permutation est fautive; mais on ne peut la rendre conforme à l'énoncé que par l'échange de H«+i avec le mari qui se trouvait à côté de sa femme; on a ainsi v,, permutations des (n -^ i) ménages, distinctes des précédentes.

3" Si la permutation qui précède l'arrivée du (/i-Hi)'^' ménage est une de celles que nous avons désignées par p„, le premier défaut se trouve corrigé par rintercalalion de l^n-^-i à la gauche de Fj, et le second défaut par ^'/i-i-i> <]"» remplace le mari qui se trouvait à côté de sa femme, tandis que celui-ci vient se placer entre F| et F„^.| ; par suite, pn permutations distinctes des précédentes.

Inversement, si l'on considère une permutation quelconque X^+i de ( /i — i ) ménages, conforme aux conditions de l'énonce, le départ du ménage ( n -h i) conduit à l'une des quatre dispositions que nous avons désignées par X,|, [1,1, v„ et p,,. On a donc la formule

(»,> '^n+i = (n — 2)XnH-(n — l)flrt-T-V;,-hp;,.

Pour obtenir d'autres formules, nous reprendrons la figuration sur un échiquier de /i* cases (p. '215), en désignant par a, 6, c, d, c, les cases que nous aurons à considérer plus spécialement {Jig. 77). Les permuta-

lions sans défaut (X«) sont celles qui correspondent au problème des n tours placées sur les cases de l'échiquier, ù l'exception des ca>es de la diagonale ac, des cases situées imniédiatenient au-dessus, et de la case ù. Nous supposerons toutes les cases blancheSy à l'exception de celles que nous venons d'indiquer et que nous considérerons comme noires.

Les dispositions dans les({uellcs une tour occupe la case a, et les {n — i) autres tours sont sur des cases blanches, ont été désignées par \l„\ celles dans lesquelles une seule tour occupe une case noire autre que a, b^ e, sont des V;,; enfin, celles où une tour occupe une case noire autre que a. \ 6, c et où, en outre, une tour occupe la case a, constituent la catégorie p„.

Si nous considérons Tune des j)ermutations (jl/j et si nous supprimons par la pensée la ligne et la colonne renfermant la case a, il reste un échiquier de (/i — i)* cases sur lequel les (w — i) autres tours forment une

l-'ig- 77-

i*roblcn)c de» ménages.

certaine permutation. Si la case e n'est pas occupée, cette permutation rentre dans la catégorie X,i-ii et si la case e est occupée, elle rentre dans la catégorie |JL,||. On a donc

[A/i " f^n-\ -+- H-rt— !•

Si nous considérons l'une des permutations v,i, elle présente cette circonstance que l'une des cases noires, autre que a, h ou c, est occupée par une tour. Or, par des permutations circulaires des colonnes, puis des lignes do l'échii^uier, on peut amener cette tour à occuper la position a et former ainsi l'une des permutations \i.n\ mais il y a sur l'échiquier {111 — i) cases noires autres que a, 6, c; on a donc

Vrt = {in 3)Urt.

Knfin, dans une permutation p^t 'a case a est toujours occupée. Si la case d est occupée, la permutation figurée qui reste lorsque l'on supprime

4î)4 NOTES ET ADDITIONS.

la li<:ne et la colonne contenant a, appartient à la catégorie pn-ij comme on le reconnaît facilement en tournant Téchiquier d'un demi-tour autour de son centre. Si la case d n'est pas occupée, on peut toujours amener la case fautive à occuper cette place extrême par des permutations convenables des lignes et des colonnes, ce qui donne une permutation fin-i« mais comme il y a (in — 3) cases noires que l'on peut amener en d, on en conclut la formule

(1) p„ = ( a/i — J) fi/,-1 -t- pn-i.

Des formules (i) et (3), on déduit (3) ^/i-Hl = (« — 2)Xn4-(3/e— Dk/iH- ?«.

Au moyen des diverses relations qui précèdent, et des valeurs initiales ^3=1. J Ks — o, lv,= o, lp, = i,

on peut former le Tableau des valeurs de X;,, jji;,, V;,, p;, pour les premières valeurs de n; les différences des X et des p vérifient les formules (a) et (4), que l'on peut écrire

. Ap/î-i

En donnant à n des valeurs successives, on déduit les formules

(()) {n — i)X„+i = C/iî- a -f-i)('X«-f- X„,)-f- /iX„-s,

où n'entrent plus que des X. Enfin, il y a lieu de noter la formule

(8) I-l«+î= /l(fl«+j-h [Xn) -1- [1,1-1-

Les formules et les démonstrations précédentes ont été obtenues, pour la première fois, par M. Laisant. D'un autre côté, M. C. Moreau, colonel d'arlillerie, qui est parvenu aux mêmes résultats, a encore indiqué les formules suivantes. On peut écrire la relation (6) sous la forme

{/i — i)X«^.,— {n -M)(/i — i)X„— (/i-f-i)X«i = — [{n — 2)\„— n{n -- 2)X«,— nln-i]\

on peut donc poser

(n — 2)X„— /è(/i — •2)X„,— nln-t— K(— i)«-».

en désignant par K une cunslante que Ton trouve égale à 4- Ainsi

L'observation du Tableau qui contient les premières valeurs de X conduit ù poser

(lO)

Xfl— a(— 1)'»= /le».

et réquation précédente donne

La formule fii) permet de calculer rapidement les valeurs de 6/1; on a ensuite celles de X» par la formule

on trouve ainsi, pour les premières valeurs de /i,

44îOi3

78o5 3io33

i6 5j8r>9C68ir)

I5 02OOI 09335 O2688