Problème des ménages

Jacques Touchard a donné en 1934^[3] la première formule explicite pour le nombre M_n de façons de disposer n couples :

${\displaystyle M_{n}=2(n!)\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!}$ .

À sa suite, de nombreux mathématiciens ont fourni diverses preuves de cette formule et des versions généralisées du problème, où l'on autorise certains conjoints à être côte à côte. Wyman et Moser, en 1958^[4], ont découvert pour M_n une autre formule, qui met en jeu les polynômes de Tchebychev.

Les premières solutions au problème des ménages consistaient à placer d'abord les femmes puis à compter, pour chacun de ces placements partiels, le nombre de façon de placer les hommes sans qu'aucun soit à côté de son épouse. Cependant, en 1986, Bogart et Doyle^[5] ont donné une preuve plus directe de la formule de Touchard^[6].

Il y a 2(n !) façons de placer les femmes, puisqu'il y a deux choix possibles pour l'ensemble des sièges destinés aux femmes et, pour chacun des deux, n! façons de répartir les femmes sur ces n sièges. Pour chacun de ces 2(n !) placements des femmes, le nombre de façons de placer les hommes est

${\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!}$ ;

c'est la même formule que celle de Touchard, au facteur 2(n !) près. La suite A000179 de l'OEIS de ces entiers plus petits, appelés nombres de ménages commence par

A₃ = 1, A₄ = 2, A₅ = 13, …

Ils satisfont la relation de récurrence^[7],[8]

${\displaystyle A_{n}=nA_{n-1}+{\frac {n}{n-2}}A_{n-2}+{\frac {4(-1)^{n-1}}{n-2}}}$

et la récurrence d'ordre 4 plus simple^[7],[9]

${\displaystyle \displaystyle A_{n}=nA_{n-1}+2A_{n-2}-(n-4)A_{n-3}-A_{n-4}}$ ,

qui permettent de les calculer facilement. (Des relations de récurrence plus compliquées ont été décrites auparavant par Cayley et Muir^[10].)

Les solutions du problème des ménages peuvent s'interpréter en termes de théorie des graphes, comme les cycles hamiltoniens orientés de graphes couronnes. Un graphe couronne s'obtient en supprimant un couplage parfait dans un graphe biparti complet K_n,n ; il a 2n sommets, dont n d'une couleur et n d'une autre, et chaque sommet d'une couleur est relié (par une arête) à tous les sommets sauf un de l'autre couleur. Dans le cas du problème des ménages, les sommets du graphe représentent les hommes et les femmes, et les arêtes représentent les paires constituées d'un homme et d'une femme autorisés à s'asseoir côte à côte. Ce graphe est formé à partir du graphe biparti complet qui connecte chaque homme à chaque femme, en supprimant le couplage parfait des arêtes joignant chaque homme à son épouse. À tout placement valide correspond un ordre des convives autour de la table, qui forme un cycle hamiltonien du graphe. Mais deux placements peuvent donner le même ordre circulaire (en) donc le même cycle hamiltonien, s'ils ne diffèrent que d'un décalage autour de la table. Par conséquent, le nombre de cycles hamiltoniens orientés du graphe couronne est égal au quotient par 2n du nombre de placements possibles^[11], donc au produit par (n − 1)! du nombre de ménages A_n.

La suite A094047 de l'OEIS de ces nombres de cycles dans ces graphes (en débutant, comme dans les deux suites précédentes, à n = 3) commence par

2, 12, 312, …

Il existe une deuxième description de ce problème en termes de théorie des graphes. Une fois les femmes assises, les placements possibles pour les hommes correspondent aux couplages parfaits d'un graphe obtenu à partir d'un graphe biparti complet en supprimant un cycle hamiltonien : le graphe biparti complet est constitué des hommes et des chaises libres, et on enlève les arêtes joignant chaque homme aux deux chaises qui sont de part et d'autre de son épouse. Le problème de compter les couplages dans un graphe biparti, et a fortiori celui de calculer les nombres de ménages, peut se résoudre en faisant intervenir les permanents de certaines matrices constituées de 0 et de 1. Dans le cas du problème des ménages, ce sont des matrices circulantes^{[10],[12],[13],[14]}.