Problème des ménages

Problème des ménages
Page d'aide sur l'homonymie Ne doit pas être confondu avec Lemme des mariages.
Une table à dix couverts. D'après la solution au problème des ménages, il y a 3120 manières différentes, pour 5 couples, de s'asseoir en alternant hommes et femmes et sans qu'aucun convive soit assis à côté de son (ou sa) conjoint(e).

En mathématiques combinatoires, le problème des ménages est la question du nombre de façons différentes de placer un nombre donné de couples autour d'une table de façon à alterner hommes et femmes et à ne placer personne à côté de son (ou sa) conjoint(e). Ce problème fut formulé en 1891 par Édouard Lucas[1] et indépendamment, quelques années plus tôt, par Peter Guthrie Tait, en relation avec la théorie des nœuds[2]. Pour un nombre de couples égal à 3, 4, 5, ... le nombre de placements possibles est

12, 96, 3120, … (suite A059375 de l’OEIS).

Des formules et des relations de récurrence permettent de calculer cette suite d'entiers ainsi que d'autres suites liées à ce problème. Au-delà de leurs applications aux plans de table, ces nombres interviennent en théorie des nœuds et ont une interprétation en théorie des graphes : ce sont les nombres de couplages et de cycles hamiltoniens dans certaines familles de graphes.

Sommaire

Formule de Touchard

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

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 Mn une autre formule, qui met en jeu les polynômes de Tchebychev.

Nombres de ménages et solutions « les dames d'abord »

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

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

A3 = 1, A4 = 2, A5 = 13, …

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

A_n = n A_{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 A_n = n A_{n-1} + 2 A_{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].)

Interprétation en théorie des graphes

Graphes en couronne à 6, 8, et 10 sommets. Le cycle extérieur de chaque graphe forme un cycle hamiltonien, mais les graphes à 8 et 10 sommets en possèdent d'autres.

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 en couronne (en). Un graphe en couronne s'obtient en supprimant un couplage parfait dans un graphe biparti complet Kn,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 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 en couronne est égal au quotient par 2n du nombre de placements possibles[11], donc au produit par (n − 1)! du nombre de ménages An.

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].

Théorie des nœuds

La motivation de Tait pour étudier le problème des ménages est venue de sa recherche d'une liste complète des nœuds ayant un nombre de croisements (en) donné. Dans la notation de Dowker (en) pour les diagrammes de nœuds, dont une forme initiale a été utilisée par Tait, les 2n points des n croisements d'un nœud sont numérotés de 1 à 2n en suivant l'ordre de parcours sur le brin. Dans un diagramme réduit, les deux numéros correspondant à un croisement de peuvent pas être consécutifs, donc l'ensemble des n paires de numéros correspondant aux n croisements, qui est utilisé dans cette notation de Dowker (en) pour représenter le nœud, peut s'interpréter comme un couplage parfait dans un graphe : les sommets sont les nombres de 1 à 2n et deux sommets sont reliés par une arête lorsqu'ils sont de parités différentes et ne sont pas consécutifs (modulo 2n). Comme ce graphe s'obtient à partir d'un graphe biparti complet (reliant toutes les paires de nombres de parités différentes) en supprimant un cycle hamiltonien (les arêtes reliant des nombres consécutifs), son nombre de couplages est égal à un nombre de ménages. Si le nœud est alterné (en), ce couplage suffit à décrire son diagramme ; sinon, on spécifie en plus, pour chaque croisement, un signe + ou - pour déterminer lequel des deux brins passe par dessus l'autre.

Cependant, le problème de Tait comporte des symétries supplémentaires qui sont absentes du problème des ménages : deux notations de Dowker peuvent représenter le même diagramme, donc le même nœud, si elle ne diffèrent que par le croisement qu'on décide de numéroter en premier. C'est pourquoi deux couplages qui se déduisent l'un de l'autre par permutation circulaire doivent être considérés comme équivalents et comptés seulement une fois. Edgar Gilbert (en)[15] a résolu cette variante du problème d'énumération, en prouvant que le nombre de couplages à équivalence près est (en fonction du nombre de croisements n = 3, 4, 5, …) :

1, 2, 5, … (suite A002484 de l’OEIS).

Notes et références

Notes

  1. ↑ Édouard Lucas, Théorie des Nombres, Gauthier-Villars, 1891, p. 491–495 
  2. ↑ (en) Jacques Dutka, « On the problème des ménages », dans The Mathematical Intelligencer, vol. 8, 1986, p. 18–33 [texte intégral, lien DOI (pages consultées le 25/12/2010)] 
  3. ↑ Jacques Touchard, « Sur un problème de permutations », dans CRAS, vol. 198, 1934, p. 631–633 
  4. ↑ (en) Max Wyman et Leo Moser, « On the problème des ménages », dans Canadian Journal of Mathematics (en), vol. 10, no 3, 1958, p. 468–480 
  5. ↑ (en) Kenneth P. Bogart et Peter G. Doyle, « Non-sexist solution of the ménage problem », dans American Mathematical Monthly, vol. 93, no 7, 1986, p. 514–519 [texte intégral, lien DOI (pages consultées le 25/12/2010)] 
  6. ↑ (en) James Gleick, « Math + Sexism: A Problem », dans New York Times, 28 octobre 1986 [texte intégral (page consultée le 25/12/2010)] 
  7. ↑ a et b (en) Thomas Muir, « Additional note on a problem of arrangement », dans Proceedings of the Royal Society of Edinburgh, vol. 11, 1882, p. 187–190 
  8. ↑ Charles-Ange Laisant, « Sur deux problèmes de permutations », dans Bulletin de la Société mathématique de France, vol. 19, 1891, p. 105–108 [texte intégral (page consultée le 26/12/2010)] 
  9. ↑ (en) E. Rodney Canfield et Nicholas C. Wormald, « Ménage numbers, bijections and P-recursiveness », dans Discrete Mathematics (en), vol. 63, no 2–3, 1987, p. 117–129 [lien DOI] 
  10. ↑ a et b (en) Thomas Muir, « On Professor Tait's problem of arrangement », dans Proceedings of the Royal Society of Edinburgh, vol. 9, 1878, p. 382–391 , incluant (p. 388–391) un ajout de Arthur Cayley.
  11. ↑ (en) Amanda F. Passmore, « An elementary solution to the ménage problem », 2005. Consulté le 25/12/2010
  12. ↑ (en) Peter Eades, Cheryl Praeger (en) et Jennifer R. Seberry, « Some remarks on the permanents of circulant (0,1) matrices », dans Utilitas Math., vol. 23, 1983, p. 145–159 [texte intégral (page consultée le 26/12/2010)] 
  13. ↑ (de) Arnold Richard Kräuter, « Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen », dans Séminaire Lotharingien de Combinatoire, vol. B11b, 1984 [texte intégral (page consultée le 26/12/2010)] 
  14. ↑ (en) J. R. Henderson, « Permanents of (0,1)-matrices having at most two zeros per line », dans Canad. Math. Bull., vol. 18, no 3, 1975, p. 353–358 [texte intégral (page consultée le 26/12/2010)] 
  15. ↑ (en) E. N. Gilbert, « Knots and classes of ménage permutations », dans Scripta Mathematica (en), vol. 22, 1956, p. 228–233 

Références

  • (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ménage problem » (voir la liste des auteurs)
  • (en) Nguyen-Huu Bong, « Lucas numbers and the menage problem », dans International Journal of Mathematical Education in Science and Technology, vol. 29, no 5, 1998, p. 647–661 [lien DOI] 
  • (en) Heinrich Dörrie (trad. David Antin), 100 Great Problems of Elementary Mathematics, Dover, 1965 (ISBN 9780486613482), chap. VIII (« Lucas' Problem of the Married Couples »), p. 27–33 
  • (en) Lars Holst, « On the “problème des ménages” from a probabilistic viewpoint », dans Statistics and Probability Letters, vol. 11, no 3, 1991, p. 225–231 [lien DOI] 
  • (en) Irving Kaplansky (en), « Solution of the problème des ménages », dans Bulletin of the American Mathematical Society (en), vol. 49, no 10, 1943, p. 784–785 [texte intégral, lien DOI (pages consultées le 25/12/2010)] 
  • (en) Irving Kaplansky et John Riordan (en), « The problème des ménages », dans Scripta Mathematica, vol. 12, 1946, p. 113–124 
  • (en) John Riordan, « The arithmetic of ménage numbers », dans Duke Mathematical Journal (en), vol. 19, 1952, p. 27–30 [lien DOI] 
  • (en) Lajos Takács (en), « On the “problème des ménages” », dans Discrete Mathematics, vol. 36, no 3, 1981, p. 289–297 [lien DOI] 

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème des ménages de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Des Moines (Iowa) — Pour les articles homonymes, voir Des Moines (homonymie). Des Moines …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Inégalité des revenus en France — Inégalités de revenu en France Les inégalités de revenu en France sont constituées par la répartition inégale des ressources économiques perçues par la population vivant en France. Elles ne doivent pas être confondues avec les inégalités de… …   Wikipédia en Français

  • EUROPE DE L’EST - Les économies des anciens pays socialistes — L’Europe de l’Est en «transition» comprend, au début de 1993, neuf États postcommunistes, que l’on désignera par le sigle P.E.C.O. (pays d’Europe centrale et orientale). Sur ces neuf États, sept sont les anciens États socialistes (Albanie,… …   Encyclopédie Universelle

  • Dette des États-Unis — Dette publique La dette publique est, dans le domaine des finances publiques, l ensemble des engagements financiers pris sous formes d emprunts par l État, les collectivités publiques et les organismes qui en dépendent directement (certaines… …   Wikipédia en Français

  • Hausse des prix — Inflation Pour les articles homonymes, voir Inflation (homonymie). L inflation est la hausse du niveau général des prix, entraînant une baisse durable du pouvoir d achat de la monnaie[1][2]. Elle est généralement évaluée au moyen de l …   Wikipédia en Français

  • SCIENCES SOCIALES (PRÉHISTOIRE DES) — Les sciences sociales sont fréquemment aujourd’hui l’objet d’un double discours. Tantôt, devant le relatif échec de la croissance quantitative, on se préoccupe de revenir de la Lune pour enfin mieux aménager la Terre, et on se tourne avec un… …   Encyclopédie Universelle

  • Projet:Économie/Liste des articles — Le but de cette page est de lister les articles de Wikipédia relatifs à l économie. Ainsi, ceux et celles intéressés par le sujet peuvent suivre les changements en cliquant « Suivi des liens ». Sommaire 1 Articles 1.1 0 9 1.2 A 1.3 B …   Wikipédia en Français

  • Liste des maires de Mantes — Mantes la Jolie Pour les articles homonymes, voir Mantes. Mantes la Jolie La place de la République et l hôtel de ville …   Wikipédia en Français

  • Assimilation des Canadiens français — Histoire du Québec …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”