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+3, 0)<=j<=min(k,2)} binomial(4-j, j)*binomial(2*n-k+j-6, k-j).
MATHEMATICA
enumerateSeatings[pairs_, d_]:=If[d==1||d>=2pairs-1||EvenQ[d], {},
Map[#[[1]]&, DeleteCases[Map[{#, Differences[#]}&[Riffle[Range[pairs], #]]&, Map[Insert[#, 1, (d+1)/2]&, Permutations[#, {Length[#]}]&[Rest[Range[pairs]]]]], {{___}, {___, 0, ___}}]]];
enumerateSeatings[6, 5]
a[pairs_, d_]:=If[pairs<=#-1||EvenQ[d]||d==1, 0, Sum[((-1)^k)*(pairs-k-1)!Sum[Binomial[2#-j-4, j]*Binomial[2(pairs-#)-k+j+2, k-j], {j, Max[#+k-pairs-1, 0], Min[k, #-2]}], {k, 0, pairs-1}]]&[(d+3)/2];
Table[a[n, 5], {n, 15}] (* Peter J. C. Moses, Jun 13 2015 *)
PROG
(PARI) a(n) = sum(k=0, n-1, (-1)^k*(n-k-1)! * sum(j=max(k-n+3, 0), min(k, 2), binomial(4-j, j)*binomial(2*n-k+j-6, k-j))); \\ Michel Marcus, Jun 13 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Shevelev and Peter J. C. Moses, Jun 07 2015
STATUS
approved