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

1, 0, 0, 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, 3191834419200, 390445460697600, 56729732529254400, 9659308746908620800, 1905270127543015833600, 431026303509734220288000, 110865322076320374571008000, 32172949121885378686623744000

Offset: 0

Author

N. J. A. Sloane, Jan 28 2001

Keywords

• nonn

Comments

The "probleme des menages" asks for the number of gender-alternating seating arrangements for n couples around a circular table with the condition that no two spouses are seated adjacently. - Paul C. Kainen and Michael Somos, Mar 11 2011

Examples

			a(3) = 12 because there is a unique seating arrangement up to circular and clockwise / counterclockwise symmetry. - _Paul C. Kainen_ and _Michael Somos_, Mar 11 2011
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 184, mu*(n).
• H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 32. equation (2.3).

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..253
• M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12 arXiv:1510.07926
• V. Baltic, On the number of certain types of strongly restricted permutations, Appl. An. Disc. Math. 4 (2010), 119-135. doi:10.2298/AADM1000008B
• K. P. Bogart and P. G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
• A. Guterman, Pólya permanent problem: 100 years after, 2014.
• Vladimir Shevelev, Peter J. C. Moses, The ménage problem with a known mathematician, arXiv:1101.5321 [math.CO], 2011, 2015.
• Wikipedia, Menage Problem

Crossrefs

Cf. A000179, A258338, A258664, A258665, A258666, A258667, A258673, A259212.

Programs

Mathematica

a[0] = 1; a[1] = 0; a[n_] := 4n n! Sum[(-1)^k Binomial[2n-k, k] (n-k)! / (2n-k), {k, 0, n}]; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Jun 19 2017, from 1st formula *)

PARI

{a(n) = local(A); if( n<3, n==0, A = vector(n); A[3] = 1; for(k=4, n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); 2 * n! * A[n])} /* Michael Somos, Mar 11 2011 */

Formula

a(n) = A000179(n) * 2 * n!.

a(n) = A094047(n) * 2 * n.