

A258673


A total of n married couples, including a mathematician M and his wife, are to be seated at the 2n chairs around a circular table, with no man seated next to his wife. After the ladies are seated at every other chair, M is the first man allowed to choose one of the remaining chairs. The sequence gives the number of ways of seating the other men, with no man seated next to his wife, if M chooses the chair that is 11 seats clockwise from his wife's chair.


8



0, 0, 0, 0, 0, 0, 115, 791, 6204, 55004, 543597, 5922929, 70518904, 910711192, 12678337943, 189252400475, 3015217932052, 51067619064756, 916176426421297, 17355904144767765, 346195850534324608, 7252654441500343712, 159210363453691696379, 3654550890669607979359
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,7


COMMENTS

This is a variation of the classic ménage problem (cf. A000179).
It is known [Riordan, ch. 8, ex. 7(b)] that, after the ladies are seated at every other chair, the number U_n of ways of seating the men in the ménage problem has asymptotic expansion U_n ~ e^(2)*n!*(1 + Sum_{k>=1} (1)^k/(k!(n1)_k)), where (n)_k = n*(n1)*...*(nk+1).
Therefore, it is natural to conjecture that a(n) ~ e^(2)*n!/(n2)*(1 + Sum_{k>=1} (1)^k/(k!(n1)_k)).
In the general case, M chooses a chair at an odd distance d >= 3 clockwise from his wife. See the corresponding general formula below.


REFERENCES

I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113124.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, chs. 7, 8.


LINKS



FORMULA

For n <= 6, a(n)=0; otherwise a(n) = Sum_{k=0..n1} (1)^k*(nk1)! * Sum_{j=max(kn+6, 0)..min(k,5)} binomial(10j, j)*binomial(2*nk+j12, kj).
In the general case (see comment), let r=(d+3)/2 and denote the solution by A(r,n). Then A(r,n) is given by the formula
A(r,n)=0 for n <= (d+1)/2; otherwise A(r,n) = Sum_{k=0..n1} ((1)^k)*(nk1)! * Sum_{j=max(r+kn1, 0)..min(k,r2)} binomial(2rj4, j)*binomial(2(nr)  k + j + 2, kj).
Note that, if n is even, then 2*Sum_{r=3..(n+2)/2} A(r,n) = A000179(n); if n is odd, then 2*Sum_{r=3..(n+1)/2} A(r,n) + A((n+3)/2, n) = A000179(n).


MATHEMATICA

a[d_, n_]:=If[n<=#1, 0, Sum[((1)^k)*(nk1)!Sum[Binomial[2#j4, j]*Binomial[2(n#)k+j+2, kj], {j, Max[#+kn1, 0], Min[k, #2]}], {k, 0, n1}]]&[(d+3)/2];


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



