“Ménage problem”的意思、由来-开放百科全书

词条

Ménage problem

释义

Touchard's formula
Ménage numbers and ladies-first solutions
Graph-theoretical interpretations
Knot theory
See also
Notes
References
External links

In combinatorial mathematics, the ménage problem or problème des ménages^[1] asks for the number of different ways in which it is possible to seat a set of male-female couples at a 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.^[2] For a number of couples equal to 3, 4, 5, ... the number of seating arrangements is

12, 96, 3120, 115200, 5836320, 382072320, 31488549120, ... {{OEIS|id=A059375}}.

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.

Touchard's formula

Let M_n denote the number of seating arrangements for n couples. {{harvtxt|Touchard|1934}} derived the formula

Much subsequent work has gone into alternative proofs for this formula and into generalized versions of the problem that count seating arrangements in which some couples are permitted to sit next to each other. A different formula for M_n involving Chebyshev polynomials was given by {{harvtxt|Wyman|Moser|1958}}.

Ménage numbers and ladies-first solutions

Until the work of {{harvtxt|Bogart|Doyle|1986}}, solutions to the ménage problem took the form of first finding all seating arrangements for the women and then counting, for each of these partial seating arrangements, the number of ways of completing it by seating the men away from their partners. However, as Bogart and Doyle showed, Touchard's formula may be derived directly by considering all seating arrangements at once rather than by factoring out the participation of the women.^[3]

There are 2×n! ways of seating the women: there are two sets of seats that can be arranged for the women, and there are n! ways of seating them at a particular set of seats. For each seating arrangement for the women, there are

ways of seating the men; this formula simply omits the 2×n! factor from Touchard's formula. The resulting smaller numbers (again, starting from n = 3),

1, 2, 13, 80, 579, 4738, 43387, 439792, ... {{OEIS|id=A000179}}

are called the ménage numbers. They satisfy the recurrence relation^[4]

and the simpler four-term recurrence^[5]

from which the ménage numbers themselves can easily be calculated.

Graph-theoretical interpretations

Solutions to the ménage problem may be interpreted in graph-theoretic terms, as directed Hamiltonian cycles in crown graphs. A crown graph is formed by removing a perfect matching from a complete bipartite graph K_n,n; it has 2n vertices of two colors, and each vertex of one color is connected to all but one of the vertices of the other color. In the case of the ménage problem, the vertices of the graph represent men and women, and the edges represent pairs of men and women who are allowed to sit next to each other. This graph is formed by removing the perfect matching formed by the male-female couples from a complete bipartite graph that connects every man to every woman. Any valid seating arrangement can be described by the sequence of people in order around the table, which forms a Hamiltonian cycle in the graph. However, two Hamiltonian cycles are considered to be equivalent if they connect the same vertices in the same cyclic order regardless of the starting vertex, while in the ménage problem the starting position is considered significant: if, as in Alice's tea party, all the guests shift their positions by one seat, it is considered a different seating arrangement even though it is described by the same cycle. Therefore, the number of oriented Hamiltonian cycles in a crown graph is smaller by a factor of 2n than the number of seating arrangements,^[6] but larger by a factor of (n − 1)! than the ménage numbers. The sequence of numbers of cycles in these graphs (as before, starting at n = 3) is

2, 12, 312, 9600, 416880, 23879520, 1749363840, ... {{OEIS|id=A094047}}.

A second graph-theoretic description of the problem is also possible. Once the women have been seated, the possible seating arrangements for the remaining men can be described as perfect matchings in a graph formed by removing a single Hamiltonian cycle from a complete bipartite graph; the graph has edges connecting open seats to men, and the removal of the cycle corresponds to forbidding the men to sit in either of the open seats adjacent to their wives. The problem of counting matchings in a bipartite graph, and therefore a fortiori the problem of computing ménage numbers, can be solved using the permanents of certain 0-1 matrices. In the case of the ménage problem, the matrices arising from this view of the problem are circulant matrices.^[7]

Knot theory

Tait's motivation for studying the ménage problem came from trying to find a complete listing of mathematical knots with a given number of crossings, say n. In Dowker notation for knot diagrams, an early form of which was used by Tait, the 2n points where a knot crosses itself, in consecutive order along the knot, are labeled with the 2n numbers from 1 to 2n. In a reduced diagram, the two labels at a crossing cannot be consecutive, so the set of pairs of labels at each crossing, used in Dowker notation to represent the knot, can be interpreted as a perfect matching in a graph that has a vertex for every number in the range from 1 to 2n and an edge between every pair of numbers that has different parity and are non-consecutive modulo 2n. This graph is formed by removing a Hamiltonian cycle (connecting consecutive numbers) from a complete bipartite graph (connecting all pairs of numbers with different parity), and so it has a number of matchings equal to a ménage number. For alternating knots, this matching is enough to describe the knot diagram itself; for other knots, an additional positive or negative sign needs to be specified for each crossing pair to determine which of the two strands of the crossing lies above the other strand.

However, the knot listing problem has some additional symmetries not present in the ménage problem: one obtains different Dowker notations for the same knot diagram if one begins the labeling at a different crossing point, and these different notations should all be counted as representing the same diagram. For this reason, two matchings that differ from each other by a cyclic permutation should be treated as equivalent and counted only once. {{harvtxt|Gilbert|1956}} solved this modified enumeration problem, showing that the number of different matchings is

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... {{OEIS|id=A002484}}.

Notes

1. ^"Ménage" is the French word for "household" (referring here to a male-female couple).
2. ^{{harvtxt|Dutka|1986}}.
3. ^{{harvtxt|Gleick|1986}}.
4. ^{{harvtxt|Muir|1882}}; {{harvtxt|Laisant|1891}}. More complicated recurrences had been described previously by Cayley and {{harvtxt|Muir|1878}}.
5. ^{{harvtxt|Muir|1882}}; {{harvtxt|Canfield|Wormald|1987}}.
6. ^{{harvtxt|Passmore|2005}}.
7. ^{{harvtxt|Muir|1878}}; {{harvtxt|Eades|Praeger|Seberry|1983}}; {{harvtxt|Kräuter|1984}}; {{harvtxt|Henderson|1975}}.

References

{{citation

| doi = 10.2307/2323022
| last1 = Bogart | first1 = Kenneth P.
| last2 = Doyle | first2 = Peter G.
| issue = 7
| journal = American Mathematical Monthly
| mr = 0856291
| pages = 514–519
| title = Non-sexist solution of the ménage problem
| url = http://www.math.dartmouth.edu/~doyle/docs/menage/menage/menage.html
| volume = 93
| year = 1986
| jstor = 2323022}}.

{{citation

| last = Bong | first = Nguyen-Huu
| doi = 10.1080/0020739980290502
| issue = 5
| journal = International Journal of Mathematical Education in Science and Technology
| mr = 1649926
| pages = 647–661
| title = Lucas numbers and the menage problem
| volume = 29
| year = 1998}}.

{{citation

| last1 = Canfield | first1 = E. Rodney
| last2 = Wormald | first2 = Nicholas C.
| doi = 10.1016/0012-365X(87)90002-1
| issue = 2–3
| journal = Discrete Mathematics
| mr = 0885491
| pages = 117–129
| title = Ménage numbers, bijections and P-recursiveness
| volume = 63
| year = 1987}}.

{{citation

| last = Dörrie | first = Heinrich
| contribution = Lucas' Problem of the Married Couples
| isbn = 978-0-486-61348-2
| pages = 27–33
| publisher = Dover
| title = 100 Great Problems of Elementary Mathematics
| year = 1965}}. Translated by David Antin.

{{citation

| doi = 10.1007/BF03025785
| last = Dutka | first = Jacques
| journal = The Mathematical Intelligencer
| mr = 0846991
| pages = 18–33
| title = On the problème des ménages
| issue = 3
| volume = 8
| year = 1986}}.

{{citation

| last1 = Eades | first1 = Peter | author1-link = Peter Eades
| last2 = Praeger | first2 = Cheryl E. | author2-link = Cheryl Praeger
| last3 = Seberry | first3 = Jennifer R. | author3-link = Jennifer Seberry
| journal = Utilitas Mathematica
| mr = 0703136
| pages = 145–159
| title = Some remarks on the permanents of circulant (0,1) matrices
| volume = 23
| year = 1983}}.

{{citation

| last = Gilbert | first = E. N. | authorlink = Edgar Gilbert
| journal = Scripta Mathematica
| mr = 0090568
| pages = 228–233
| title = Knots and classes of ménage permutations
| volume = 22
| year = 1956}}.

{{citation

| last = Gleick | first = James | author-link = James Gleick
| date = October 28, 1986
| journal = New York Times
| title = Math + Sexism: A Problem
| url = https://query.nytimes.com/gst/fullpage.html?sec=health&res=9A0DEEDB153BF93BA15753C1A960948260}}.

{{citation

| doi = 10.4153/CMB-1975-064-6
| last = Henderson | first = J. R.
| issue = 3
| journal = Canadian Mathematical Bulletin
| mr = 0399127
| pages = 353–358
| title = Permanents of (0,1)-matrices having at most two zeros per line
| volume = 18
| year = 1975}}.

{{citation

| last = Holst | first = Lars
| doi = 10.1016/0167-7152(91)90147-J
| issue = 3
| journal = Statistics and Probability Letters
| mr = 1097978
| pages = 225–231
| title = On the ‘problème des ménages’ from a probabilistic viewpoint
| volume = 11
| year = 1991}}.

{{citation

| last = Kaplansky | first = Irving | authorlink = Irving Kaplansky
| doi = 10.1090/S0002-9904-1943-08035-4
| journal = Bulletin of the American Mathematical Society
| mr = 0009006
| pages = 784–785
| title = Solution of the problème des ménages
| issue = 10
| volume = 49
| year = 1943}}.

{{citation

| last1 = Kaplansky | first1 = Irving | author1-link = Irving Kaplansky
| last2 = Riordan | first2 = J. | author2-link = John Riordan (mathematician)
| journal = Scripta Mathematica
| mr = 0019074
| pages = 113–124
| title = The problème des ménages
| volume = 12
| year = 1946}}.

{{citation

| last = Kräuter | first = Arnold Richard
| journal = Séminaire Lotharingien de Combinatoire
| language = German
| title = Über die Permanente gewisser zirkulanter Matrizen und damit zusammenhängender Toeplitz-Matrizen
| url = http://www.mat.univie.ac.at/~slc/opapers/s11kraeu.html
| volume = B11b
| year = 1984}}.

{{citation

| last = Laisant | first = Charles-Ange | author-link = Charles-Ange Laisant
| journal = Bulletin de la Société Mathématique de France
| language = French
| pages = 105–108
| title = Sur deux problèmes de permutations
| department = Vie de la société
| url = http://www.numdam.org/item?id=BSMF_1891__19__93_1
| volume = 19
| year = 1891}}.

{{citation

| last = Lucas | first = Édouard | author-link = Édouard Lucas
| location = Paris
| pages = 491–495
| publisher = Gauthier-Villars
| title = Théorie des Nombres
| year = 1891}}.

{{citation

| last = Muir | first = Thomas | author-link = Thomas Muir (mathematician)
| journal = Proceedings of the Royal Society of Edinburgh
| pages = 382–391
| title = On Professor Tait's problem of arrangement
| volume = 9
| year = 1878}}. Includes (pp. 388–391) an addition by Arthur Cayley.

{{citation

| last = Muir | first = Thomas | author-link = Thomas Muir (mathematician)
| journal = Proceedings of the Royal Society of Edinburgh
| pages = 187–190
| title = Additional note on a problem of arrangement
| volume = 11
| year = 1882}}.

{{citation

| last = Passmore | first = Amanda F.
| title = An elementary solution to the ménage problem
| year = 2005
|citeseerx= 10.1.1.96.8324}}.

{{citation

| last = Riordan | first = John | authorlink = John Riordan (mathematician)
| doi = 10.1215/S0012-7094-52-01904-2
| journal = Duke Mathematical Journal
| mr = 0045680
| pages = 27–30
| title = The arithmetic of ménage numbers
| issue = 1
| volume = 19
| year = 1952}}.

{{citation

| last = Takács | first = Lajos | authorlink = Lajos Takács
| doi = 10.1016/S0012-365X(81)80024-6
| issue = 3
| journal = Discrete Mathematics
| mr = 0675360
| pages = 289–297
| title = On the "problème des ménages"
| volume = 36
| year = 1981}}.

{{citation

| last = Touchard | first = J. | authorlink = Jacques Touchard
| issue = 631–633
| journal = C. R. Acad. Sci. Paris
| title = Sur un problème de permutations
| volume = 198
| year = 1934}}.

{{citation

| last1 = Wyman | first1 = Max
| last2 = Moser | first2 = Leo | author2-link = Leo Moser
| issue = 3
| journal = Canadian Journal of Mathematics
| mr = 0095127
| pages = 468–480
| title = On the problème des ménages
| volume = 10
| year = 1958 | doi=10.4153/cjm-1958-045-6}}.{{refend}}

External links

{{mathworld|title=Married Couples Problem|urlname=MarriedCouplesProblem}}
{{mathworld|title=Laisant's Recurrence Formula|urlname=LaisantsRecurrenceFormula}}

4 : Permutations|Integer sequences|Recurrence relations|Knot theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。