A000179 -id:A000179 - cp's OEIS frontend

A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.

1, 0, 0, 0, 1, 3, 23, 177, 1553, 14963, 157931, 1814453, 22566237, 302267423, 4340478951, 66541218865, 1084982173641, 18752743351339, 342523093859011, 6593167693927885, 133408305489947029, 2831112931136162775, 62878579846490149375, 1458746608689369440265

Offset: 1

N. J. A. Sloane

Also number of ways of arranging the numbers 1..n in a circle so that adjacent numbers do not differ by 1 mod n. Reversing the direction around the circle does not count as a different solution (cf. A078603).
Also number of ways of seating n people around a circular table so that no one sits next to any of his neighbors in a previous seating order.
Suppose n people are seated at random around a circular table for two meals. Then p(n) = a(n)/((n-1)!/2) is the probability that no two people sit together at both meals.
Number of Hamiltonian cycles in the complement of C_n where C_n is the n-cycle graph. - Andrew Howroyd, Mar 15 2016

			a(6)=3: 135264, 136425, 142635.

P. Poulet, Reply to Query 4750, Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..100
B. Aspvall and F. M. Liang, The dinner table problem, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122-124.
Eric Weisstein's World of Mathematics, Cycle Complement Graph
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Index entries for sequences related to shoe lacings

Cf. A000179 (Ménage problem), A078603, A078630, A078631, A242522 (Hamiltonian cycles in complement of path), A006184, left column of A326411.

dinner := proc(n) local j,k,sum; sum := (n-1)!/2 + (-1)^n; for k from 1 to n-1 do for j from 1 to min(n-k,k) do sum := sum+(-1)^k*binomial(k-1,j-1)*binomial(n-k,j)*n/(n-k)*(n-k-1)!/2*2^j; od; od; end;

t = {1, 0, 0, 0, 1, 3, 23}; Do[AppendTo[t, ((n^3 - 8*n^2 + 18*n - 21) t[[-1]] + 4*n*(n - 5) t[[-2]] - 2*(n - 6) (n^2 - 5 n + 3) t[[-3]] + (n^2 - 7*n + 9)  t[[-4]] + (n - 5) (n^2 - 5*n + 3) t[[-5]])/(n^2 - 7*n + 9)], {n, 8, 25}]; t (* T. D. Noe, Jan 04 2012 *)
Join[{1, 0}, RecurrenceTable[{a[3] == 0, a[4] == 0, a[5] == 1, a[6] == 3, a[7] == 23, (n^2 - 7 n + 9) a[n] == (n^3 - 8 n^2 + 18 n - 21) a[n - 1] + 4 n (n - 5) a[n - 2] - 2 (n - 6) (n^2 - 5 n + 3) a[n - 3] + (n^2 - 7 n + 9) a[n - 4] + (n - 5) (n^2 - 5 n + 3) a[n - 5]}, a, {n, 3, 20}]] (* Eric W. Weisstein, Feb 26 2021 *)

D-finite with recurrence (n^2 - 7n + 9)a(n) = (n^3 - 8n^2 + 18n - 21)a(n - 1) + 4n(n - 5)a(n - 2) - 2(n - 6)(n^2 - 5n + 3)a(n - 3) + (n^2 - 7n + 9)a(n - 4) + (n - 5)(n^2 - 5n + 3)a(n - 5), for n >= 8. - Poulet.
p(n) = exp(-2)*(1 + O(1/n)). - Aspvall and Liang.
Asymptotic: a(n)/(n-1)! ~ 1/(2*e^2)*(1 - 4/n + 20/(3n^3) + 58/(3n^4) + 796/(15n^5) + 7858/(45n^6) + 40324/(63n^7) + 140194/(63n^8) + 2444744/(405n^9) + 40680494/(14175n^10) + ...). - Vaclav Kotesovec, Apr 10 2012

Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001

More terms from Sascha Kurz, Mar 22 2002

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.

Original entry on oeis.org

0, 0, 1, 1, 4, 20, 115, 787, 6184, 54888, 542805, 5916725, 70463900, 910167596, 12672415015, 189181881575, 3014307220880, 51054940726928, 915987174021609, 17352888926841897, 346144782915314740, 7251738265074465220, 159193007549552845339, 3654204694819144118651

Offset: 1

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

nonn

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.

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.

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

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

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

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

A000904 a(n) = (n+1)a(n-1) + (n+2)a(n-2) + a(n-3); a(1)=0, a(2)=3, a(3)=13.

Original entry on oeis.org

0, 3, 13, 83, 592, 4821, 43979, 444613, 4934720, 59661255, 780531033, 10987095719, 165586966816, 2660378564777, 45392022568023, 819716784789193, 15620010933562688, 313219935456042955, 6593238655510464741, 145364470356686267259, 3349976056859294611696

Offset: 1

N. J. A. Sloane

Numbers connected with the ménage problem (cf. A000179).

			G.f. = 3 x^2 + 13 x^3 + 83 x^4 + 592 x^5 + 4821 x^6 + 43979 x^7 + 444613 x^8 + ...

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..100
E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1, p. 495.
E. Lucas, Théorie des Nombres, Gauthier-Villars, Paris, 1891, Vol. 1. [Annotated scan of pages 488-499 only]

Cf. A000179, A000271.

a000904_list = 0 : 3 : 13 : zipWith (+) a000904_list
   (zipWith (+) (zipWith (*) [6..] $ drop 1 a000904_list)
                (zipWith (*) [5..] $ drop 2 a000904_list))
-- Reinhard Zumkeller, Nov 22 2011

max = 19; f[x_] = 1/(x+x^2)^2 * Sum[ n!*(x/(1+x)^2)^n, {n, 0, max+2}]; Series[ f[x]+1/x-1/x^2, {x, 0, max}] // CoefficientList[#, x]& // Rest (* Jean-François Alcover, May 16 2013, after Vladeta Jovovic *)
RecurrenceTable[{a[1]==0,a[2]==3,a[3]==13,a[n]==(n+1)a[n-1]+(n+2)a[n-2]+a[n-3]},a,{n,20}] (* Harvey P. Dale, Aug 03 2016 *)

G.f.: (1/(x+x^2)^2)*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 29 2007
G.f.: (1/E(0)-1+x-x^2)/x^2 where E(k) = (1+x)^2 + k*x - (k+1)*x*(1+x)^2/E(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 17 2012
From Vladimir Shevelev, Jun 29 - Jul 22 2015: (Start)
Using formulas in [Lucas], we have
(i) a(1)=0, a(2)=3, for n>=3, a(n) = (n+2)*a(n-1) + a(n-2) + 2*(-1)^n
(Note that (i) yields a(3)=13 and, for n>=4,
a(n-1) = (n+1)*a(n-2) + a(n-3) - 2*(-1)^n. Summing this with (i), we see that (i) defines A000904);
(ii) for n>=1, a(n) = (A000179(n+3) + 2*(-1)^n)/(n+3);
(iii) for n>=3, a(n) = a(n-2) + A000179(n+2);
(iii)*  if n is even, then a(n) = Sum_{i=0..(n+2)/2} A000179(2*i);
(iii)** if n is odd, then a(n) = Sum_{i=2..(n+1)/2} A000179(2*i+1).
Also
(iv)  a(n+1) = A000271(n+3) - a(n);
(iv)*  a(n) = Sum_{i=0..n+2}(-1)^i*A000271(n-i+2);
(v) a(n-2) = Sum_{i=0..n}(-1)^i*binomial(2*n-i+1, i)*(n-i)!, n>=3.
Note that Lucas considered this sequence with other initials. His formulas (i) - (iii), which he proved on pp. 491-495 of his book [Lucas], we wrote for the current initials.
The other 5 formulas, including the explicit formula 5), are new and we give their proofs:
(iii)*,(iii)**. Formulas (iii)* and (iii)** are obtained by the direct summation of (iii) over even and odd values respectively, taking into account the initials.
(iv). To obtain (iv), write (iii) in the form
a(j+1) - a(j) = -(a(j) - a(j-1)) +  A000179(j+3), j>=2.
Summing Sum_{j=2..n}, we have
a(n+1) - a(2) = -a(n) + a(1) + Sum_{j=2..n}A000179(j+3). Since a(1)=0, a(2)=3, we find
a(n+1)-3 = -a(n) + Sum_{i=5..n+3}A000179(i). But A000179(3)=1, A000179(4)=2. Therefore, we have
a(n+1) = -a(n) + Sum_{i=3..n+3}A000179(i).
It is left to note that, by the definition,
A000271(n) = Sum{i=3..n}A000179(i). So
a(n+1) = A000271(n+3) - a(n).
(iv)*. In view of the first four initials 1,0,0,1 of A000271, we have
Sum_{i=0..n+2}(-1)^i*A000271(n-i+2) = Sum_{i=0..n-2}(-1)^i*A000271(n-i+2) and, by (iv), the last sum equals
Sum_{i=0..n-2}(-1)^i(a(n-i)+a(n-i-1)) = a(n) + (-1)^(n-2)*a(1) = a(n).
(v). We use induction for n>=3. In case n=3 (v) gives 6-6*2+10-4=0 = a(1). Set n:=n+2.
Suppose for some (now n>=1) we have
a(n) = Sum_{i=0..n+2} (-1)^i*binomial(2*n-i+5, i)*(n+2-i)! (*)
Further we use (iv). In A259212 we proved an explicit formula for A000271(n-1) such that we have
A000271(n+3) = Sum_{j=0..n+3}(-1)^j * binomial(2*n-j+6,j)*(n-j+3)!, n>3.
Now, by (iv) and (*) with changing summing j=i+1, we have
a(n+1) = Sum_{j=0..n+3} (-1)^j*binomial(2*n-j+6,j)*(n-j+3)! + Sum_{j=1..n+3} (-1)^j*binomial(2*n-j+6, j-1)*(n+3-j)!
Since binomial(n,-1)=0, then in the second sum the summing could begin with j=0.
So, we have
a(n+1) = Sum_{j=0..n+3} (-1)^j*binomial(2*n-j+7, j)*(n+3-j)! = Sum_{j=0..n+3} (-1)^j*binomial(2*(n+1)-j+5,j)*((n+1)+2-j)!
Thus this expression formally is obtained from (*) by replacing n with n+1.
QED (End)
a(n) ~ n! * n^2 / exp(2). - Vaclav Kotesovec, Jul 04 2015

More terms from Larry Reeves (larryr(AT)acm.org), Nov 27 2001

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.

Original entry on oeis.org

0, 0, 0, 1, 5, 20, 116, 791, 6203, 55000, 543576, 5922813, 70518113, 910704988, 12678282940, 189251856883, 3015212009143, 51067548545968, 916175515710896, 17355891466436025, 346195661281979133, 7252651426282955236, 159210312386078554436, 3654549974493252076175

Offset: 1

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

nonn

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.

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.

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

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

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

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

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.

Original entry on oeis.org

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

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

nonn

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.

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.

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

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

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

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

A258667 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 9 seats clockwise from his wife's chair.

Original entry on oeis.org

0, 0, 0, 0, 0, 20, 116, 791, 6205, 55004, 543596, 5922929, 70518903, 910711188, 12678337924, 189252400363, 3015217931281, 51067619058668, 916176426367084, 17355904144230373, 346195850528456683, 7252654441430368404, 159210363452786908116, 3654550890657000160319

Offset: 1

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

nonn

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.

I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
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.

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

a[n_] := If[n<6, 0, Sum[(-1)^k (n-k-1)! Sum[Binomial[8-j, j] Binomial[2n-k+j-10, k-j], {j, Max[k-n+5, 0], Min[k, 4]}], {k, 0, n-1}]];
Array[a, 24] (* Jean-François Alcover, Sep 19 2018 *)

a(n) = if (n<=5, 0, sum(k=0, n-1, (-1)^k*(n-k-1)!*sum(j=max(k-n+5, 0), min(k,4), binomial(8-j, j)*binomial(2*n-k+j-10, k-j)))); \\ Michel Marcus, Jun 26 2015

For n <= 5, a(n)=0; otherwise a(n) = Sum_{0<=k<=n-1}(-1)^k*(n-k-1)! Sum_{max(k-n+5, 0)<=j<=min(k,4)} binomial(8-j, j)*binomial(2*n-k+j-10, k-j).

A000425 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 0, 0, 8, 30, 192, 1344, 10800, 97434, 976000, 10749024, 129103992, 1679495350, 23525384064, 353028802560, 5650370001120, 96082828074162, 1729886440780800, 32874134679574208, 657589108734075240, 13811277748363437006, 303884178002526338624

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

A diagonal of A058087. Cf. A000179.

p[n_] := Sum[2*n/(2*n-k)*Binomial[2*n-k, k]*(n-k)!*(x-1)^k, {k, 0, n}] // CoefficientList[#, x]&; Array[p, 25][[All, 2]] (* Jean-François Alcover, Feb 08 2016 *)

It appears that a(n) = round(4*n*exp(-2)*(BesselK(n-1,2)+BesselK(n,2))) when n >= 10. - Mark van Hoeij, Oct 25 2011
Conjecture: (n-1)*(n-3)*a(n) -n*(n-2)*(n-3)*a(n-1) -n*(n-1)*(n-3)*a(n-2) -n *(n-1)*a(n-3)=0. - R. J. Mathar, Nov 02 2015
Conjecture: a(n) = 2*n*A000271(n). - R. J. Mathar, Nov 02 2015

A059375 Number of seating arrangements for the ménage problem.

Original entry on oeis.org

1, 0, 0, 12, 96, 3120, 115200, 5836320, 382072320, 31488549120, 3191834419200, 390445460697600, 56729732529254400, 9659308746908620800, 1905270127543015833600, 431026303509734220288000, 110865322076320374571008000, 32172949121885378686623744000

Offset: 0

N. J. A. Sloane, Jan 28 2001

nonn

The "probleme des menages" asks for the number of gender-alternating seating arrangements for n couples around a circular table with the condition that no two spouses are seated adjacently. - Paul C. Kainen and Michael Somos, Mar 11 2011

			a(3) = 12 because there is a unique seating arrangement up to circular and clockwise / counterclockwise symmetry. - _Paul C. Kainen_ and _Michael Somos_, Mar 11 2011

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 184, mu*(n).
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 32. equation (2.3).

Seiichi Manyama, Table of n, a(n) for n = 0..253
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12 arXiv:1510.07926
V. Baltic, On the number of certain types of strongly restricted permutations, Appl. An. Disc. Math. 4 (2010), 119-135. doi:10.2298/AADM1000008B
K. P. Bogart and P. G. Doyle, Nonsexist solution of the menage problem, Amer. Math. Monthly 93:7 (1986), 514-519.
A. Guterman, Pólya permanent problem: 100 years after, 2014.
Vladimir Shevelev, Peter J. C. Moses, The ménage problem with a known mathematician, arXiv:1101.5321 [math.CO], 2011, 2015.
Wikipedia, Menage Problem

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

a[0] = 1; a[1] = 0; a[n_] := 4n n! Sum[(-1)^k Binomial[2n-k, k] (n-k)! / (2n-k), {k, 0, n}]; Table[a[n], {n, 0, 17}] (* Jean-François Alcover, Jun 19 2017, from 1st formula *)

{a(n) = local(A); if( n<3, n==0, A = vector(n); A[3] = 1; for(k=4, n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); 2 * n! * A[n])} /* Michael Somos, Mar 11 2011 */

a(n) = A000179(n) * 2 * n!.

a(n) = A094047(n) * 2 * n.

A258673 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 11 seats clockwise from his wife's chair.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 115, 791, 6204, 55004, 543597, 5922929, 70518904, 910711192, 12678337943, 189252400475, 3015217932052, 51067619064756, 916176426421297, 17355904144767765, 346195850534324608, 7252654441500343712, 159210363453691696379, 3654550890669607979359

Offset: 1

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

nonn

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)).
In the general case, M chooses a chair at an odd distance d >= 3 clockwise from his wife. See the corresponding general formula below.

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.

I. Kaplansky and J. Riordan, The problème des ménages, Scripta Math. 12, (1946), 113-124. [Scan of annotated copy]
Peter J. C. Moses, Seatings for 7 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.

Cf. A000179, A258664, A258665, A258666, A258667, A259673.

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[11,#]&,Range[20]] (* Peter J. C. Moses, Jun 07 2015 *)

For n <= 6, a(n)=0; otherwise a(n) = Sum_{k=0..n-1} (-1)^k*(n-k-1)! * Sum_{j=max(k-n+6, 0)..min(k,5)} binomial(10-j, j)*binomial(2*n-k+j-12, k-j).
In the general case (see comment), let r=(d+3)/2 and denote the solution by A(r,n). Then A(r,n) is given by the formula
A(r,n)=0 for n <= (d+1)/2; otherwise A(r,n) = Sum_{k=0..n-1} ((-1)^k)*(n-k-1)! * Sum_{j=max(r+k-n-1, 0)..min(k,r-2)} binomial(2r-j-4, j)*binomial(2(n-r) - k + j + 2, k-j).
Note that, if n is even, then 2*Sum_{r=3..(n+2)/2} A(r,n) = A000179(n); if n is odd, then 2*Sum_{r=3..(n+1)/2} A(r,n) + A((n+3)/2, n) = A000179(n).

A259212 A total of n married couples, including a mathematician M and his wife W, are to be seated at the 2n chairs around a circular table. M and W are the first couple allowed to choose chairs, and they choose two chairs next to each other. The sequence gives the number of ways of seating the remaining couples so that women and men are in alternate chairs but M and W are the only couple seated next to each other.

Original entry on oeis.org

0, 0, 0, 6, 72, 1920, 69120, 3402000, 218252160, 17708544000, 1773002649600, 214725759494400, 30941575378560000, 5231894853375590400, 1025881591718766182400, 230901375630648602880000, 59127083048250564931584000, 17091634972762948947148800000

Offset: 1

Vladimir Shevelev, Jun 21 2015

After M and W are seated at neighboring chairs, the problem of enumerating the ways of seating the remaining n-1 married couples is equivalent to the following problem: find the number of ways of seating n-1 married couples at 2*(n-1) chairs in a straight line, men and women in alternate chairs, so that no husband is next to his wife. According to our comment in A000271, this problem has a solution 2*(n-1)!*A000271(n-1), n >= 2. Here the coefficient 2 should be replaced by 1, since the place of the first woman W, by the condition, is already fixed.

Also the number of Hamiltonian paths in the (n-1)-crown graph for n > 3. - Eric W. Weisstein, Mar 27 2018

Vladimir Shevelev and Peter J. C. Moses, Alice and Bob go to dinner: A variation on menage, INTEGERS, Vol. 16(2016), #A72.
Eric Weisstein's World of Mathematics, Crown Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Path.

Cf. A000179, A000271, A258664, A258665, A258666, A258667, A258673.

a[n_] := (n-1)! Sum[(-1)^(n-k+1) k! Binomial[n+k-1, 2k], {k, 0, n}]; a[1] = 0; Array[a, 18] (* Jean-François Alcover, Sep 03 2016 *)
Join[{0}, Table[-(-1)^n (n - 1)! HypergeometricPFQ[{1, 1 - n, n}, {1/2}, 1/4], {n, 2, 20}]] (* Eric W. Weisstein, Mar 27 2018 *)

a(n) = if (n==1, 0, my(m=n-1); m!*sum(k=0, m, binomial(2*m-k,k)*(m-k)!*(-1)^k)); \\ Michel Marcus, Jun 26 2015

a(n) = (n-1)!*A000271(n-1), for n > 1.
From Vladimir Shevelev, Jul 07 2015: (Start)
Consider the general formula for solution A(r,n) in A258673 without the restriction A(r,n)=0 for n <= (d+1)/2 in case d=2*n-1. The case when M and W sit at neighboring chairs corresponds to d=1, r=2 or d=2*n-1, r=n+1. In both cases, from this formula we have
A(r,n) = a(n)/(n-1)! = Sum_{j=0..n-1} (-1)^j * binomial(2*n-j-2,j)*(n-j-1)!, n > 1. (End)

More terms from Peter J. C. Moses, Jun 21 2015

cp's OEIS Frontend

A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A000904 a(n) = (n+1)*a(n-1) + (n+2)*a(n-2) + a(n-3); a(1)=0, a(2)=3, a(3)=13.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A000425 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Crossrefs

Programs

A000904 a(n) = (n+1)a(n-1) + (n+2)a(n-2) + a(n-3); a(1)=0, a(2)=3, a(3)=13.