login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A258664 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 3 seats clockwise from his wife's chair. 8
0, 0, 1, 1, 4, 20, 115, 787, 6184, 54888, 542805, 5916725, 70463900, 910167596, 12672415015, 189181881575, 3014307220880, 51054940726928, 915987174021609, 17352888926841897, 346144782915314740, 7251738265074465220, 159193007549552845339, 3654204694819144118651 (list; graph; refs; listen; history; text; internal format)
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.

E. Lucas, Théorie des nombres, Paris, 1891, 491-496.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, chs. 7, 8.

J. Touchard, Sur un problème de permutations, C. R. Acad. Sci. Paris, 198 (1934), 631-633.

LINKS

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

Peter J. C. Moses, Seatings for 6 couples

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.

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

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

Sequence in context: A171802 A100034 A192924 * A231539 A106567 A077445

Adjacent sequences:  A258661 A258662 A258663 * A258665 A258666 A258667

KEYWORD

nonn

AUTHOR

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 01:24 EDT 2018. Contains 316518 sequences. (Running on oeis4.)