login
Number of seating arrangements for the ménage problem.
8

%I #55 Nov 06 2022 23:58:27

%S 1,0,0,12,96,3120,115200,5836320,382072320,31488549120,3191834419200,

%T 390445460697600,56729732529254400,9659308746908620800,

%U 1905270127543015833600,431026303509734220288000,110865322076320374571008000,32172949121885378686623744000

%N Number of seating arrangements for the ménage problem.

%C 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

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 184, mu*(n).

%D H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 32. equation (2.3).

%H Seiichi Manyama, <a href="/A059375/b059375.txt">Table of n, a(n) for n = 0..253</a>

%H M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:<a href="http://doi.org/10.1007/978-3-319-44543-4_12">10.1007/978-3-319-44543-4_12</a> arXiv:<a href="http://arxiv.org/abs/1510.07926">1510.07926</a>

%H V. Baltic, On the number of certain types of strongly restricted permutations, Appl. An. Disc. Math. 4 (2010), 119-135. doi:<a href="http://doi.org/10.2298/AADM1000008B">10.2298/AADM1000008B</a>

%H K. P. Bogart and P. G. Doyle, <a href="https://math.dartmouth.edu/~doyle/docs/menage/menage/menage.html">Nonsexist solution of the menage problem</a>, Amer. Math. Monthly 93:7 (1986), 514-519.

%H A. Guterman, <a href="http://www.law05.si/law14/presentations/Guterman.pdf">Pólya permanent problem: 100 years after</a>, 2014.

%H Vladimir Shevelev, Peter J. C. Moses, <a href="http://arxiv.org/abs/1101.5321">The ménage problem with a known mathematician</a>, arXiv:1101.5321 [math.CO], 2011, 2015.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/M%C3%A9nage_problem">Menage Problem</a>

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

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

%e 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

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

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

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

%K nonn

%O 0,4

%A _N. J. A. Sloane_, Jan 28 2001