

A114939


Number of essentially different seating arrangements for n couples around a circular table with 2n seats avoiding spouses being neighbors and avoiding clusters of 3 persons with equal gender.


5



0, 1, 7, 216, 10956, 803400, 83003040, 11579823360, 2080493573760, 469031859192960, 129727461014726400, 43176116371928601600, 17025803126147196057600, 7850538273249476117913600
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Arrangements that differ only by rotation or reflection are excluded by the following conditions: Seat number 1 is assigned to person (a). Person (a)'s spouse (A) can only take seats with numbers <=(n+1). If (A) gets seat n+1 (i.e. sits exactly opposite to her/his spouse) then person (B) can only take seats with numbers <= n.


LINKS

Table of n, a(n) for n=1..14.
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151162. doi:10.1007/9783319445434_12; arXiv:1510.07926 [math.CO], 20152016.


FORMULA

See Alekseyev (2016) and the PARI code for the formula.
a(n) = A258338(n) / (4*n).


EXAMPLE

a(2)=1 because the only valid arrangement is aBAb.
a(3)=7 because the only valid arrangements under the given conditions are: abAcBC, aBAcbC, aBcAbC, aBcACb, acAbCB, acBAbC, aCAbcB.


MATHEMATICA

a[1] = 0;
a[n_] := (n1)!/4 Sum[(1)^j(nj)! SeriesCoefficient[ SeriesCoefficient[Tr[ MatrixPower[{{0, 1, 0, y^2, 0, 0}, {z y^2, 0, 1, 0, y^2, 0}, {z y^2, 0, 0, 0, y^2, 0}, {0, 1, 0, 0, 0, z}, {0, 1, 0, y^2, 0, z}, {0, 0, 1, 0, y^2, 0}}, 2n]], {y, 0, 2n}] , {z, 0, j}], {j, 0, n}];
Array[a, 14] (* JeanFrançois Alcover, Dec 03 2018, from PARI *)


PROG

(PARI) { a(n) = if(n<=1, 0, (1)^n*(n1)!*2^(n1) + n! * polcoeff( polcoeff( [0, 2*y*z^3 + z^2, 3*y*z^5  4*z^4 + ((2*y^2  1)/y)*z^3, 6*y*z^7 + (4*y^2 + 11)*z^6 + ((8*y^2 + 4)/y)*z^5 + 3*z^4] * sum(j=0, n1, j! * [0, 0, 0, z^6 + z^4; 1, 0, 0, ((y^2 + 1)/y)*z^5  2*z^4 + ((y^2  1)/y)*z^3; 0, 1, 0, ((2*y^2 + 2)/y)*z^3 + z^2; 0, 0, 1, 2*z^2]^(n+j) ) * [1, 0, 0, 0]~, 2*n, z), 0, y) / 2 ); }


CROSSREFS

Cf. A114938, A137729, A137730, A137737, A137749, A258338.
Sequence in context: A193836 A193877 A193186 * A193224 A319538 A290974
Adjacent sequences: A114936 A114937 A114938 * A114940 A114941 A114942


KEYWORD

nonn,nice


AUTHOR

Hugo Pfoertner, Jan 08 2006


EXTENSIONS

a(4)a(7) corrected, formula and further term provided by Max Alekseyev, Feb 15 2008


STATUS

approved



