Ménage problem

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

The [binary] ménage problem is concerned with the enumeration of seating arrangements of 

n

opposite-sex couples around a circular table [with 

2n

seats], such that

• no pair of adjacent people are of the same sex (FM and MF is allowed; FF and MM is forbidden),
• no spouses sit next to each other,

and where the couples and seats are all labeled.

The [binary] ménage problem can be restated thus: enumeration of arrangements of integers 

0

to 

2n  −  1

, such that

• no pair of adjacent numbers may have the same parity,
•  

  2k  +  1

  neither precedes nor succeeds 

  2k, 0   ≤   k   ≤   n  −  1

  .

Number of seating arrangements for the ménage problem

The number of seating arrangements 

Sn

for the ménage problem is

Sn = Ln Mn = (2 n!) Mn ,

where 

Ln = 2 n!

is the number of ways of sitting the 

n

ladies first, and 

Mn

is the number of ways of sitting the 

n

gentlemen thereafter.

A059375 Number of seating arrangements for the ménage problem. [For 

n

opposite-sex couples around a circular table with 

2n

seats.] [For 

n ≥ 0

.]

 

{1, 0, 0, 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, 3191834419200, 390445460697600, 56729732529254400, 9659308746908620800, 1905270127543015833600, ...}

A094047 Number of seating arrangements of 

n

couples around a circular table (up to rotations) so that each person sits between two people of the opposite sex and no couple is seated together. [For 

n ≥ 1

.]
[[[Category:Pages using the math template without the tex argument|Ménage problem]] 

A094047(n) = A059375(n) / (2n)

]

 

{0, 0, 2, 12, 312, 9600, 416880, 23879520, 1749363840, 159591720960, 17747520940800, 2363738855385600, 371511874881100800, 68045361697964851200, 14367543450324474009600, ...}

Ménage numbers

The ménage numbers 

Mn

are the number of ways of sitting the 

n

men after sitting the 

n

ladies. (The ladies can sit in 

Ln = 2 n!

ways.)

A000179 Ménage numbers: number of permutations 

s

of 

[0, ..., n  −  1]

such that 

s(i)   ≠   i

and 

s(i)   ≡/   i + 1 (mod n)

for all 

i

. [For 

n ≥ 0

.] [[[Category:Pages using the math template without the tex argument|Ménage problem]] 

A000179(n) = A059375(n) / (2 n!)

]

 

{1, 0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, ...}

A249510 Ménage primes.

 

{2, 13, 775596313, 567525075138663383127158192994765939404930668817780601409606090331861, ...}

Ternary ménage problem

The ternary ménage problem is concerned with the enumeration of seating arrangements of 

n

opposite-sex couples around a circular table [with 

2n

seats], such that

• no triple of adjacent people are all of the same sex (FFM, FMF, FMM, MFF, MFM, MMF is allowed; FFF and MMM is forbidden),
• no spouses sit next to each other,

and where the couples and seats are all labeled.

The ternary ménage problem can be restated thus: enumeration of arrangements of integers 

0

to 

2n  −  1

, such that

• no triple of adjacent numbers may all have the same parity,
•  

  2k  +  1

  neither precedes nor succeeds 

  2k, 0   ≤   k   ≤   n  −  1

  .

Number of seating arrangements for the ternary ménage problem

A258338 Ternary ménage problem: number of seating arrangements for 

n

opposite-sex couples around a circular table such that no spouses and no triples of the same sex sit next to each other.
Seats are labeled. [For 

n ≥ 1

.]

 

{0, 8, 84, 3456, 219120, 19281600, 2324085120, 370554347520, 74897768655360, 18761274367718400, 5708008284647961600, 2072453585852572876800, ...}

A114939 Number of essentially different [up to rotations and reflections] seating arrangements for 

n

couples around a circular table with 

2n

seats avoiding spouses being neighbors and avoiding clusters of 3 persons with equal gender. [For 

n ≥ 1

.] [[[Category:Pages using the math template without the tex argument|Ménage problem]] 

A114939(n) = A258338(n) / (4n)

]

 

{0, 1, 7, 216, 10956, 803400, 83003040, 11579823360, 2080493573760, 469031859192960, 129727461014726400, 43176116371928601600, 17025803126147196057600, ...}

Ternary ménage numbers

(...)

Generalized ménage problems

(...)

External links

• Max Alekseyev, On enumeration of seating arrangements of couples around a circular table, Automatic Sequences Workshop, 2015.
• Vladimir Shevelev, The menage problem with a known mathematician, arXiv:1101.5321, 2011.
• D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv:1401.1089, 2014.