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
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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jan 28 2001
STATUS
approved