login
A total of n married couples, including a mathematician M and his wife W, are to be seated at the 2n chairs around a circular table. M and W are the first couple allowed to choose chairs, and they choose two chairs next to each other. The sequence gives the number of ways of seating the remaining couples so that women and men are in alternate chairs but M and W are the only couple seated next to each other.
8

%I #44 Sep 03 2023 23:39:51

%S 0,0,0,6,72,1920,69120,3402000,218252160,17708544000,1773002649600,

%T 214725759494400,30941575378560000,5231894853375590400,

%U 1025881591718766182400,230901375630648602880000,59127083048250564931584000,17091634972762948947148800000

%N A total of n married couples, including a mathematician M and his wife W, are to be seated at the 2n chairs around a circular table. M and W are the first couple allowed to choose chairs, and they choose two chairs next to each other. The sequence gives the number of ways of seating the remaining couples so that women and men are in alternate chairs but M and W are the only couple seated next to each other.

%C After M and W are seated at neighboring chairs, the problem of enumerating the ways of seating the remaining n-1 married couples is equivalent to the following problem: find the number of ways of seating n-1 married couples at 2*(n-1) chairs in a straight line, men and women in alternate chairs, so that no husband is next to his wife. According to our comment in A000271, this problem has a solution 2*(n-1)!*A000271(n-1), n >= 2. Here the coefficient 2 should be replaced by 1, since the place of the first woman W, by the condition, is already fixed.

%C Also the number of Hamiltonian paths in the (n-1)-crown graph for n > 3. - _Eric W. Weisstein_, Mar 27 2018

%H Vladimir Shevelev and Peter J. C. Moses, <a href="http://www.emis.de/journals/INTEGERS/papers/q72/q72.Abstract.html">Alice and Bob go to dinner: A variation on menage</a>, INTEGERS, Vol. 16(2016), #A72.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CrownGraph.html">Crown Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>.

%F a(n) = (n-1)!*A000271(n-1), for n > 1.

%F From _Vladimir Shevelev_, Jul 07 2015: (Start)

%F Consider the general formula for solution A(r,n) in A258673 without the restriction A(r,n)=0 for n <= (d+1)/2 in case d=2*n-1. The case when M and W sit at neighboring chairs corresponds to d=1, r=2 or d=2*n-1, r=n+1. In both cases, from this formula we have

%F A(r,n) = a(n)/(n-1)! = Sum_{j=0..n-1} (-1)^j * binomial(2*n-j-2,j)*(n-j-1)!, n > 1. (End)

%t a[n_] := (n-1)! Sum[(-1)^(n-k+1) k! Binomial[n+k-1, 2k], {k, 0, n}]; a[1] = 0; Array[a, 18] (* _Jean-François Alcover_, Sep 03 2016 *)

%t Join[{0}, Table[-(-1)^n (n - 1)! HypergeometricPFQ[{1, 1 - n, n}, {1/2}, 1/4], {n, 2, 20}]] (* _Eric W. Weisstein_, Mar 27 2018 *)

%o (PARI) a(n) = if (n==1, 0, my(m=n-1); m!*sum(k=0, m, binomial(2*m-k,k)*(m-k)!*(-1)^k)); \\ _Michel Marcus_, Jun 26 2015

%Y Cf. A000179, A000271, A258664, A258665, A258666, A258667, A258673.

%K nonn,nice

%O 1,4

%A _Vladimir Shevelev_, Jun 21 2015

%E More terms from _Peter J. C. Moses_, Jun 21 2015