https://en.wikipedia.org/wiki/M%C3%A9nage_problem

Menage problem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Assignment problem in combinatorial mathematics
[240px-Wedding_Banquet_setting]
 
A table with ten place settings. There are 3120 different ways in
which five male-female couples can sit at this table such that men
and women alternate and nobody sits next to their partner.

In combinatorial mathematics, the menage problem or probleme des
menages^[1] 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 Edouard 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, ...
    (sequence A059375 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.

[ ]

Contents

  * 1 Touchard's formula
  * 2 Menage numbers and ladies-first solutions
  * 3 Graph-theoretical interpretations
  * 4 Knot theory
  * 5 See also
  * 6 Notes
  * 7 References
  * 8 External links

Touchard's formula[edit]

Let M[n] denote the number of seating arrangements for n couples.
Touchard (1934) derived the formula

    M n = 2 [?] n ! [?] k = 0 n ( - 1 ) k 2 n 2 n - k ( 2 n - k k ) ( n -
    k ) ! . {\displaystyle M_{n}=2\cdot n!\sum _{k=0}^{n}(-1)^{k}{\
    frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.} M_{n}=2\cdot n!\sum _{{k
    =0}}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!.

Much subsequent work has gone into alternative proofs for this
formula and into various generalized versions of the problem.

A different umbral formula for M[n] involving Chebyshev polynomials
of first kind was given by Wyman & Moser (1958).

Menage numbers and ladies-first solutions[edit]

There are 2xn! 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

    A n = [?] k = 0 n ( - 1 ) k 2 n 2 n - k ( 2 n - k k ) ( n - k ) !
    {\displaystyle A_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}
    {2n-k \choose k}(n-k)!} A_{n}=\sum _{{k=0}}^{n}(-1)^{k}{\frac
    {2n}{2n-k}}{2n-k \choose k}(n-k)!

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

    1, 2, 13, 80, 579, 4738, 43387, 439792, ... (sequence A000179 in
    the OEIS)

are called the menage numbers. The factor 2 n 2 n - k ( 2 n - k k )
{\displaystyle {\frac {2n}{2n-k}}{2n-k \choose k}} {\displaystyle {\
frac {2n}{2n-k}}{2n-k \choose k}} is the number of ways of forming k
non-overlapping pairs of adjacent seats or, equivalently, the number
of matchings of k edges in a cycle graph of 2n vertices. The
expression for A[n] is the immediate result of applying the principle
of inclusion-exclusion to arrangements in which the people seated at
the endpoints of each edge of a matching are required to be a couple.

Until the work of Bogart & Doyle (1986), solutions to the menage
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. Bogart and Doyle argued that 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] However, Kirousis & Kontogeorgiou (2018) found the
even more straightforward ladies-first solution described above by
making use of a few of Bogart and Doyle's ideas (although they took
care to recast the argument in non-gendered language).

The menage numbers satisfy the recurrence relation^[4]

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

and the simpler four-term recurrence^[5]

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

from which the menage numbers themselves can easily be calculated.

Graph-theoretical interpretations[edit]

[300px-Crown_graphs]
 
Crown graphs with six, eight, and ten vertices. The outer cycle of
each graph forms a Hamiltonian cycle; the eight and ten-vertex graphs
also have other Hamiltonian cycles.

Solutions to the menage 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 menage 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 menage 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 menage numbers. The sequence of numbers of cycles in
these graphs (as before, starting at n = 3) is

    2, 12, 312, 9600, 416880, 23879520, 1749363840, ... (sequence 
    A094047 in the OEIS).

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 menage numbers, can be solved using the
permanents of certain 0-1 matrices. In the case of the menage
problem, the matrix arising from this view of the problem is the
circulant matrix in which all but two adjacent elements of the
generating row equal 1.^[7]

Knot theory[edit]

Tait's motivation for studying the menage 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 2
n. 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 menage 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 menage 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. Gilbert (1956) solved this modified
enumeration problem, showing that the number of different matchings
is

    1, 2, 5, 20, 87, 616, 4843, 44128, 444621, ... (sequence A002484
    in the OEIS).

See also[edit]

  * Oberwolfach problem, a different mathematical problem involving
    the arrangement of diners at tables
  * Probleme des rencontres, a similar problem involving partial
    derangements

Notes[edit]

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

References[edit]

  * Bogart, Kenneth P.; Doyle, Peter G. (1986), "Non-sexist solution
    of the menage problem", American Mathematical Monthly, 93 (7):
    514-519, doi:10.2307/2323022, JSTOR 2323022, MR 0856291.
  * Bong, Nguyen-Huu (1998), "Lucas numbers and the menage problem",
    International Journal of Mathematical Education in Science and
    Technology, 29 (5): 647-661, doi:10.1080/0020739980290502, MR 
    1649926.
  * Canfield, E. Rodney; Wormald, Nicholas C. (1987), "Menage
    numbers, bijections and P-recursiveness", Discrete Mathematics,
    63 (2-3): 117-129, doi:10.1016/0012-365X(87)90002-1, MR 0885491.
  * Dorrie, Heinrich (1965), "Lucas' Problem of the Married Couples",
    100 Great Problems of Elementary Mathematics, Dover, pp. 27-33,
    ISBN 978-0-486-61348-2. Translated by David Antin.
  * Dutka, Jacques (1986), "On the probleme des menages", The
    Mathematical Intelligencer, 8 (3): 18-33, doi:10.1007/BF03025785,
    MR 0846991, S2CID 116433056.
  * Eades, Peter; Praeger, Cheryl E.; Seberry, Jennifer R. (1983),
    "Some remarks on the permanents of circulant (0,1) matrices",
    Utilitas Mathematica, 23: 145-159, MR 0703136.
  * Gilbert, E. N. (1956), "Knots and classes of menage
    permutations", Scripta Mathematica, 22: 228-233, MR 0090568.
  * Gleick, James (October 28, 1986), "Math + Sexism: A Problem", New
    York Times.
  * Henderson, J. R. (1975), "Permanents of (0,1)-matrices having at
    most two zeros per line", Canadian Mathematical Bulletin, 18 (3):
    353-358, doi:10.4153/CMB-1975-064-6, MR 0399127.
  * Holst, Lars (1991), "On the 'probleme des menages' from a
    probabilistic viewpoint", Statistics and Probability Letters, 11
    (3): 225-231, doi:10.1016/0167-7152(91)90147-J, MR 1097978.
  * Kaplansky, Irving (1943), "Solution of the probleme des menages",
    Bulletin of the American Mathematical Society, 49 (10): 784-785,
    doi:10.1090/S0002-9904-1943-08035-4, MR 0009006.
  * Kaplansky, Irving; Riordan, J. (1946), "The probleme des
    menages", Scripta Mathematica, 12: 113-124, MR 0019074.
  * Kirousis, L.; Kontogeorgiou, G. (2018), "102.18 The probleme des
    menages revisited", The Mathematical Gazette, 102 (553): 147-149,
    arXiv:1607.04115, doi:10.1017/mag.2018.27, S2CID 126036427.
  * Krauter, Arnold Richard (1984), "Uber die Permanente gewisser
    zirkulanter Matrizen und damit zusammenhangender
    Toeplitz-Matrizen", Seminaire Lotharingien de Combinatoire (in
    German), B11b.
  * Laisant, Charles-Ange (1891), "Sur deux problemes de
    permutations", Vie de la societe, Bulletin de la Societe
    Mathematique de France (in French), 19: 105-108.
  * Lucas, Edouard (1891), Theorie des Nombres, Paris:
    Gauthier-Villars, pp. 491-495.
  * Muir, Thomas (1878), "On Professor Tait's problem of arrangement"
    , Proceedings of the Royal Society of Edinburgh, 9: 382-391, doi:
    10.1017/S0370164600032557. Includes (pp. 388-391) an addition by
    Arthur Cayley.
  * Muir, Thomas (1882), "Additional note on a problem of
    arrangement", Proceedings of the Royal Society of Edinburgh, 11:
    187-190.
  * Passmore, Amanda F. (2005), An elementary solution to the menage
    problem, CiteSeerX 10.1.1.96.8324.
  * Riordan, John (1952), "The arithmetic of menage numbers", Duke
    Mathematical Journal, 19 (1): 27-30, doi:10.1215/
    S0012-7094-52-01904-2, MR 0045680.
  * Takacs, Lajos (1981), "On the "probleme des menages"", Discrete
    Mathematics, 36 (3): 289-297, doi:10.1016/S0012-365X(81)80024-6,
    MR 0675360.
  * Touchard, J. (1934), "Sur un probleme de permutations", C. R.
    Acad. Sci. Paris, 198 (631-633).
  * Wyman, Max; Moser, Leo (1958), "On the probleme des menages",
    Canadian Journal of Mathematics, 10 (3): 468-480, doi:10.4153/
    cjm-1958-045-6, MR 0095127.

External links[edit]

  * Weisstein, Eric W. "Married Couples Problem". MathWorld.
  * Weisstein, Eric W. "Laisant's Recurrence Formula". MathWorld.

*
Retrieved from "https://en.wikipedia.org/w/index.php?title=
Menage_problem&oldid=1122563223"
Categories:

  * Permutations
  * Integer sequences
  * Recurrence relations
  * Knot theory

Hidden categories:

  * Articles with short description
  * Short description matches Wikidata
  * CS1 German-language sources (de)
  * CS1 French-language sources (fr)

Navigation menu

Personal tools

  * Not logged in
  * Talk
  * Contributions
  * Create account
  * Log in

Namespaces

  * Article
  * Talk

[ ] English

Views

  * Read
  * Edit
  * View history

[ ] More

[                    ] [Search] [Go]
 

Navigation

  * Main page
  * Contents
  * Current events
  * Random article
  * About Wikipedia
  * Contact us
  * Donate

Contribute

  * Help
  * Learn to edit
  * Community portal
  * Recent changes
  * Upload file

Tools

  * What links here
  * Related changes
  * Upload file
  * Special pages
  * Permanent link
  * Page information
  * Cite this page
  * Wikidata item

Print/export

  * Download as PDF
  * Printable version

Languages

  * Espanol
  * Francais
  * Russkii
  * Ukrayins'ka

Edit links

  * This page was last edited on 18 November 2022, at 06:50 (UTC).
  * Text is available under the Creative Commons
    Attribution-ShareAlike License 3.0 ; additional terms may apply.
    By using this site, you agree to the Terms of Use and Privacy
    Policy. Wikipedia(r) is a registered trademark of the Wikimedia
    Foundation, Inc., a non-profit organization.

  * Privacy policy
  * About Wikipedia
  * Disclaimers
  * Contact Wikipedia
  * Mobile view
  * Developers
  * Statistics
  * Cookie statement

  * Wikimedia Foundation
  * Powered by MediaWiki