OFFSET

1,4

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.

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)

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

PROG

(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

CROSSREFS

KEYWORD

nonn,nice

AUTHOR

Vladimir Shevelev, Jun 21 2015

EXTENSIONS

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

STATUS

approved