The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A258665 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 5 seats clockwise from his wife's chair. 8
0, 0, 0, 1, 5, 20, 116, 791, 6203, 55000, 543576, 5922813, 70518113, 910704988, 12678282940, 189251856883, 3015212009143, 51067548545968, 916175515710896, 17355891466436025, 346195661281979133, 7252651426282955236, 159210312386078554436, 3654549974493252076175 (list; graph; refs; listen; history; text; internal format)



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


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.


Table of n, a(n) for n=1..24.

Peter J. C. Moses, Seatings for 6 couples

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.


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


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


(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


Cf. A000179, A258664, A258666, A258667, A258673, A259212.

Sequence in context: A319489 A207972 A117736 * A028944 A332710 A054720

Adjacent sequences:  A258662 A258663 A258664 * A258666 A258667 A258668




Vladimir Shevelev and Peter J. C. Moses, Jun 07 2015



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 28 08:06 EST 2020. Contains 332321 sequences. (Running on oeis4.)