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,4

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

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

Formula

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

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

Example

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

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 *)

Prog

(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 */

Crossrefs

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

Sequence in context: A155620 A219438 A219139 * A251430 A027255 A121791

Adjacent sequences: A059372 A059373 A059374 * A059376 A059377 A059378

Keyword

nonn

Author

N. J. A. Sloane, Jan 28 2001

Status

approved