A259212 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.

0, 0, 0, 6, 72, 1920, 69120, 3402000, 218252160, 17708544000, 1773002649600, 214725759494400, 30941575378560000, 5231894853375590400, 1025881591718766182400, 230901375630648602880000, 59127083048250564931584000, 17091634972762948947148800000

Offset: 1

Author

Vladimir Shevelev, Jun 21 2015

Keywords

• nonn
• nice

Comments

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.

Also the number of Hamiltonian paths in the (n-1)-crown graph for n > 3. - Eric W. Weisstein, Mar 27 2018

Links

• Vladimir Shevelev and Peter J. C. Moses, Alice and Bob go to dinner: A variation on menage, INTEGERS, Vol. 16(2016), #A72.
• Eric Weisstein's World of Mathematics, Crown Graph.
• Eric Weisstein's World of Mathematics, Hamiltonian Path.

Crossrefs

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

Programs

Mathematica

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

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

Formula

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

From Vladimir Shevelev, Jul 07 2015: (Start)

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

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)

Extensions

More terms from Peter J. C. Moses, Jun 21 2015