OFFSET
1,5
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!(n-1)_k)), where (n)_k = n*(n-1)*...*(n-k+1).
Therefore, it is natural to conjecture that a(n) ~ e^(-2)*n!/(n-2)*(1 + Sum_{k>=1}(-1)^k/(k!(n-1)_k)).
REFERENCES
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, chs. 7, 8.
LINKS
Peter J. C. Moses, Seatings for 6 couples
I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
E. Lucas, Sur le problème des ménages, Théorie des nombres, Paris, 1891, 491-496.
Vladimir Shevelev, Peter J. C. Moses, The ménage problem with a known mathematician, arXiv:1101.5321 [math.CO], 2011, 2015.
Vladimir Shevelev and Peter J. C. Moses, Alice and Bob go to dinner: A variation on menage, INTEGERS, Vol. 16 (2016), #A72.
J. Touchard, Sur un problème de permutations, C.R. Acad. Sci. Paris, 198 (1934), 631-633.
FORMULA
a(n) = Sum_{0<=k<=n-1}(-1)^k*(n-k-1)! * Sum_{max(k-n+2, 0)<=j<=min(k,1)} binomial(2-j, j)*binomial(2*n-k+j-4, k-j).
MATHEMATICA
a[d_, n_]:=If[n<=#-1, 0, Sum[((-1)^k)*(n-k-1)!Sum[Binomial[2#-j-4, j]*Binomial[2(n-#)-k+j+2, k-j], {j, Max[#+k-n-1, 0], Min[k, #-2]}], {k, 0, n-1}]]&[(d+3)/2];
Map[a[3, #]&, Range[25]] (* Peter J. C. Moses, Jun 07 2015 *)
PROG
(PARI) a(n) = sum(k=0, n-1, (-1)^k*(n-k-1)!*sum(j=max(k-n+2, 0), min(k, 1), binomial(2-j, j)*binomial(2*n-k+j-4, k-j))); \\ Michel Marcus, Jun 26 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev and Peter J. C. Moses, Jun 07 2015
STATUS
approved