login
A258666
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 7 seats clockwise from his wife's chair.
9
0, 0, 0, 0, 4, 20, 117, 791, 6204, 55004, 543595, 5922925, 70518884, 910711076, 12678337153, 189252394275, 3015217877068, 51067618521276, 916176420499159, 17355904074255065, 346195849623668420, 7252654428822549364, 159210363264445218829, 3654550887654460566191
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 5 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)=0 for n <= 4; for n >= 5, a(n) = Sum_{k=0..n-1} (-1)^k*(n-k-1)! Sum_{j=max(k-n+4, 0)..min(k,3)} binomial(6-j, j)*binomial(2*n-k+j-8, k-j).
MATHEMATICA
a[n_] := If[n<5, 0, Sum[(-1)^k (n-k-1)! Sum[Binomial[6-j, j] Binomial[2n-k+j-8, k-j], {j, Max[k-n+4, 0], Min[k, 3]}], {k, 0, n-1}]];
Array[a, 24] (* Jean-François Alcover, Sep 19 2018 *)
PROG
(PARI) vector(30, n, if (n<=4, 0, sum(k=0, n-1, (-1)^k*(n-k-1)!*sum(j=max(k-n+4, 0), min(k, 3), binomial(6-j, j)*binomial(2*n-k+j-8, k-j))))) \\ Michel Marcus, Jun 17 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved