|
|
A059375
|
|
Number of seating arrangements for the ménage problem.
|
|
8
|
|
|
1, 0, 0, 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, 3191834419200, 390445460697600, 56729732529254400, 9659308746908620800, 1905270127543015833600, 431026303509734220288000, 110865322076320374571008000, 32172949121885378686623744000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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
|
|
FORMULA
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|