Ménage problem (original) (raw)
In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits next to his or her partner. This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory. For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sequence in the OEIS).
| Property | Value |
|---|---|
| dbo:abstract | In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits next to his or her partner. This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory. For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sequence in the OEIS). Mathematicians have developed formulas and recurrence equations for computing these numbers and related sequences of numbers. Along with their applications to etiquette and knot theory, these numbers also have a graph theoretic interpretation: they count the numbers of matchings and Hamiltonian cycles in certain families of graphs. (en) 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 hétérosexuels monogames 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 et indépendamment, quelques années plus tôt, par Peter Guthrie Tait, en relation avec la théorie des nœuds. Pour un nombre de couples égal à 3, 4, 5, ... le nombre de placements possibles est 12, 96, 3120, … (suite 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. (fr) В комбинаторике задача о супружеских парах или задача о гостях (англ. ménage problem, фр. problème des ménages) спрашивает, сколькими различными способами можно рассадить супружеские пары за круглым столом так, чтобы лица одного пола не сидели рядом, а также никакая пара супругов не сидела на соседних местах. Задача сформулирована в 1891 году Эдуардом Люка и рассматривалась независимо несколькими годами раньше Питером Тэтом в связи с теорией узлов. Для количества пар 3, 4, 5, … искомое число способов рассаживания равно 12, 96, 3120, 115 200, 5 836 320, 382 072 320, 31 488 549 120, … (последовательность в OEIS). Для количества способов рассаживания найдены явные и рекуррентные формулы. Кроме применения в этикете и теории узлов, эти числа имеют также интерпретацию в теории графов — они дают число паросочетаний и гамильтоновых циклов в некоторых семействах графов. (ru) В комбінаториці задача про подружні пари, задача про гостей, або задача Люка (англ. Ménage problem, фр. Problème des ménages) запитує, скількома різними способами можна розсадити подружні пари за круглим столом так, щоб особи однієї статі не сиділи поруч, а також щоб ніяка подружня пара не сиділа на сусідніх місцях. Завдання сформульоване в 1891 року Едуардом Люка і розглядалося незалежно кількома роками раніше Пітером Тетом у зв'язку з теорією вузлів. Для кількості пар 3, 4, 5, … шукане число способів розсаджування дорівнює 12, 96, 3120, 115 200, 5 836 320, 382 072 320, 31 488 549 120, … (послідовність в OEIS). Для кількості способів розсаджування знайдені явні і рекурентні формули. Крім застосування в етикеті і теорії вузлів, ці числа мають також інтерпретацію в теорії графів — вони дають число парувань і гамільтонових циклів в деяких родинах графів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Wedding_Banquet_setting.jpeg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.dartmouth.edu/~doyle/docs/menage/menage/menage.html http://www.numdam.org/item%3Fid=BSMF_1891__19__93_1 https://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html https://gallica.bnf.fr/ark:/12148/bpt6k31506/f631.item https://query.nytimes.com/gst/fullpage.html%3Fsec=health&res=9A0DEEDB153BF93BA15753C1A960948260 https://zenodo.org/record/1603269 |
| dbo:wikiPageID | 21068755 (xsd:integer) |
| dbo:wikiPageLength | 17204 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122563223 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Perfect_matching dbr:The_Mathematical_Intelligencer dbr:Peter_Guthrie_Tait dbc:Permutations dbr:Complete_bipartite_graph dbr:Crown_graph dbr:Matching_(graph_theory) dbr:Matrix_(mathematics) dbr:Crossing_number_(knot_theory) dbr:Combinatorics dbr:Édouard_Lucas dbr:Permanent_(mathematics) dbr:Alice's_Adventures_in_Wonderland dbr:American_Mathematical_Monthly dbc:Integer_sequences dbc:Recurrence_relations dbr:Cycle_graph dbr:Cyclic_permutation dbr:Dowker_notation dbr:Alternating_knot dbr:Directed_graph dbr:Discrete_Mathematics_(journal) dbr:Graph_theory dbr:Knot_theory dbr:Recurrence_relation dbc:Knot_theory dbr:Arthur_Cayley dbr:Chebyshev_polynomials dbr:Bulletin_of_the_American_Mathematical_Society dbr:Circulant_matrix dbr:Inclusion–exclusion_principle dbr:Knot_(mathematics) dbr:New_York_Times dbr:Canadian_Journal_of_Mathematics dbr:Canadian_Mathematical_Bulletin dbr:Recurrence_equation dbr:Umbral_calculus dbr:Scripta_Mathematica dbr:Comptes_rendus_de_l'Académie_des_sciences dbr:Oberwolfach_problem dbr:Séminaire_Lotharingien_de_Combinatoire dbr:Hamiltonian_cycle dbr:Problème_des_rencontres dbr:File:Crown_graphs.svg dbr:File:Wedding_Banquet_setting.jpeg |
| dbp:title | Laisant's Recurrence Formula (en) Married Couples Problem (en) |
| dbp:urlname | LaisantsRecurrenceFormula (en) MarriedCouplesProblem (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harvtxt dbt:Math dbt:Mathworld dbt:OEIS dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Permutations dbc:Integer_sequences dbc:Recurrence_relations dbc:Knot_theory |
| rdf:type | yago:Abstraction100002137 yago:Arrangement107938773 yago:Change107296428 yago:Event100029378 yago:Group100031264 yago:Happening107283608 yago:Ordering108456993 yago:PsychologicalFeature100023100 yago:WikicatIntegerSequences yago:YagoPermanentlyLocatedEntity yago:Sequence108459252 yago:Series108457976 yago:Substitution107443761 yago:Variation107337390 yago:WikicatPermutations |
| rdfs:comment | In combinatorial mathematics, the ménage problem or problème des ménages asks for the number of different ways in which it is possible to seat a set of male-female couples at a round dining table so that men and women alternate and nobody sits next to his or her partner. This problem was formulated in 1891 by Édouard Lucas and independently, a few years earlier, by Peter Guthrie Tait in connection with knot theory. For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... (sequence in the OEIS). (en) 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 hétérosexuels monogames 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 et indépendamment, quelques années plus tôt, par Peter Guthrie Tait, en relation avec la théorie des nœuds. Pour un nombre de couples égal à 3, 4, 5, ... le nombre de placements possibles est 12, 96, 3120, … (suite de l'OEIS). (fr) В комбінаториці задача про подружні пари, задача про гостей, або задача Люка (англ. Ménage problem, фр. Problème des ménages) запитує, скількома різними способами можна розсадити подружні пари за круглим столом так, щоб особи однієї статі не сиділи поруч, а також щоб ніяка подружня пара не сиділа на сусідніх місцях. Завдання сформульоване в 1891 року Едуардом Люка і розглядалося незалежно кількома роками раніше Пітером Тетом у зв'язку з теорією вузлів. Для кількості пар 3, 4, 5, … шукане число способів розсаджування дорівнює (uk) В комбинаторике задача о супружеских парах или задача о гостях (англ. ménage problem, фр. problème des ménages) спрашивает, сколькими различными способами можно рассадить супружеские пары за круглым столом так, чтобы лица одного пола не сидели рядом, а также никакая пара супругов не сидела на соседних местах. Задача сформулирована в 1891 году Эдуардом Люка и рассматривалась независимо несколькими годами раньше Питером Тэтом в связи с теорией узлов. Для количества пар 3, 4, 5, … искомое число способов рассаживания равно (ru) |
| rdfs:label | Problema del menaje (es) Problème des ménages (fr) Ménage problem (en) Задача о супружеских парах (ru) Задача Люка (uk) |
| owl:sameAs | freebase:Ménage problem wikidata:Ménage problem dbpedia-es:Ménage problem dbpedia-fr:Ménage problem dbpedia-ru:Ménage problem dbpedia-uk:Ménage problem https://global.dbpedia.org/id/38x3F |
| prov:wasDerivedFrom | wikipedia-en:Ménage_problem?oldid=1122563223&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Crown_graphs.svg wiki-commons:Special:FilePath/Wedding_Banquet_setting.jpeg |
| foaf:isPrimaryTopicOf | wikipedia-en:Ménage_problem |
| is dbo:knownFor of | dbr:Peter_Tait_(physicist) dbr:Édouard_Lucas |
| is dbo:wikiPageDisambiguates of | dbr:Ménage_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Menage_problem dbr:Problème_des_ménages dbr:Laisant's_recurrence_formula dbr:Laisant's_Recurrence_Formula dbr:Ménage_Number dbr:Ménage_number dbr:Married_Couples_Problem dbr:Married_couples_problem |
| is dbo:wikiPageWikiLink of | dbr:Ménage_(disambiguation) dbr:Peter_Tait_(physicist) dbr:Derangement dbr:Dowker–Thistlethwaite_notation dbr:Jacques_Touchard dbr:List_of_permutation_topics dbr:Crown_graph dbr:Menage_problem dbr:1891_in_science dbr:Problème_des_ménages dbr:Édouard_Lucas dbr:Permanent_(mathematics) dbr:Laisant's_recurrence_formula dbr:Laisant's_Recurrence_Formula dbr:Oberwolfach_problem dbr:Ménage_Number dbr:Ménage_number dbr:Married_Couples_Problem dbr:Married_couples_problem |
| is dbp:knownFor of | dbr:Peter_Tait_(physicist) dbr:Édouard_Lucas |
| is foaf:primaryTopic of | wikipedia-en:Ménage_problem |
