A078631 -id:A078631 - 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

A089222 Number of ways of seating n people around a table for the second time without anyone sitting next to the same person as they did the first time.

Original entry on oeis.org

1, 0, 0, 0, 0, 10, 36, 322, 2832, 27954, 299260, 3474482, 43546872, 586722162, 8463487844, 130214368530, 2129319003680, 36889393903794, 675098760648204, 13015877566642418, 263726707757115400, 5603148830577775218, 124568968969991162100, 2892414672938546871250

Offset: 0

Udi Hadad (somebody(AT)netvision.net.il), Dec 22 2003

A078603 counts these arrangements up to circular symmetry (i.e., two arrangements are the same if one can be rotated to give the other). A002816 counts them up to dihedral symmetry (i.e., two arrangements are the same if one can be rotated or reflected to give the other). - Joel B. Lewis, Jan 28 2010

			a(4)=0 because trying to arrange 1,2,3,4 around a table will always give a couple who is sitting next to each other and differ by 1.

J. Snell, Introduction to Probability, e-book, pp. 101 Q. 20.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Art of Problem Solving forum, Random neighbors. - _Joel B. Lewis_, Jan 28 2010
B. Aspvall and F. M. Liang, The dinner table problem, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.
Charles M. Grinstead and J. Laurie Snell, Introduction to Probability.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 626.
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. Note that in this paper a(1) = 1. See Column 2 in the table on page 3.

Cf. A002464, A002816, A078603, A078630, A078631.

Same[cperm_, n_] := ( For[same = False; i = 2, (i <= n) && ! same, i++, same = ((Mod[cperm[[i - 1]], n] + 1) == cperm[[i]]) || ((Mod[cperm[[ i]], n] + 1) == cperm[[i - 1]])]; same = same || ((Mod[cperm[[n]], n] + 1) == cperm[[1]]) || ((Mod[ cperm[[1]], n] + 1) == cperm[[n]]); Return[same]); CntSame[n_] := (allPerms = Permutations[Range[n]]; count = 0; For[j = 1, j <= n!, j++, perm = allPerms[[j]]; If[ ! Same[perm, n], count++ ]]; Return[count]);
(* or direct computation of terms *)
Table[If[n<3, 0, n! + (-1)^n*2n + Sum[(-1)^r*(n/(n-r))^2 * (n-r)! * Sum[2^c * Binomial[r-1,c-1] * Binomial[n-r,c], {c,1,r}], {r,1,n-1}]], {n,1,25}] (* Vaclav Kotesovec, Apr 06 2012 *)

Inclusion-exclusion gives that for n > 2, we have a(n) = n! + 2*n*(-1)^n + Sum_{1 <= k <= m < n} (-1)^m * (n/k) * binomial(n-m-1, k-1) * binomial(m-1, k-1) * 2^k * n * (n-m-1)!. - Joel B. Lewis, Jan 28 2010
a(n) = (3*n-30)*a(n-11) + (6*n-45)*a(n-10) + (5*n+18)*a(n-9) - (8*n-139)*a(n-8) - (26*n-204)*a(n-7) - (4*n-30)*a(n-6) + (26*n-148)*a(n-5) + (8*n-74)*a(n-4) - (9*n-18)*a(n-3) - (2*n-15)*a(n-2) + (n+2)*a(n-1), n >= 14. - Vaclav Kotesovec, Apr 13 2010
The asymptotic expansion from article by Aspvall and Liang (also cited in article by Tauraso) is wrong. Bad terms are 736/(15*n^5) + 8428/(45*n^6) + 40174/(63*n^7). Right asymptotic formula is a(n) ~ (n!/e^2)*(1 - 4/n + 20/(3*n^3) + 58/(3*n^4) + 796/(15*n^5) + 7858/(45*n^6) + 40324/(63*n^7) + 140194/(63*n^8) + ...). Verified also numerically. For example, for n=200, exact/asymptotic results are 1.0000000000125542243 (Aspvall + Liang), 1.0000000000000008990 (Kotesovec 7 terms) or 1.0000000000000000121 (Kotesovec 8 terms). - Vaclav Kotesovec, Apr 06 2012
a(n) = 2*n*A002816(n) for n > 1. - Martin Renner, Apr 01 2022

Tauraso reference from Parthasarathy Nambi, Dec 21 2006
More terms from Vladeta Jovovic, Nov 29 2009
a(0)=1 prepended by Alois P. Heinz, Jul 31 2019

A078630 Numerators of coefficients of asymptotic expansion of probability p(n) (see A002816) in powers of 1/n.

Original entry on oeis.org

1, -4, 0, 20, 58, 796, 7858, 40324, 140194, 2444744, 40680494, -7117319032, -149539443124, -223750776484, -4960419494993024, -46146161037854692, -689434674121075448, -132496988938839119444, -9686633414582239854958, -442788087926096759821484

Offset: 0

N. J. A. Sloane, Dec 13 2002

sign

			p(n) = exp(-2)*(1 - 4/n + 20/(3n^3) + 58/(3n^4) + ...).

Vaclav Kotesovec, Table of n, a(n) for n = 0..50
B. Aspvall and F. M. Liang, The dinner table problem, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.

Cf. A078631, A089222.

t = 15;
y[n_]:=(1+Sum[Subscript[p,k]/n^k,{k,1,t}]);
mul=1;start=9; If[t>9,mul=n^(t-9);start=t];
w=Apart[Expand[mul*Simplify[
y[n]*n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7)*(n-8)*(n-9)*(n-10)
-((3*n-30)*y[n-11]
+(6*n-45)*y[n-10]*(n-10)
+(5*n+18)*y[n-9]*(n-9)*(n-10)
-(8*n-139)*y[n-8]*(n-8)*(n-9)*(n-10)
-(26*n-204)*y[n-7]*(n-7)*(n-8)*(n-9)*(n-10)
-(4*n-30)*y[n-6]*(n-6)*(n-7)*(n-8)*(n-9)*(n-10)
+(26*n-148)*y[n-5]*(n-5)*(n-6)*(n-7)*(n-8)*(n-9)*(n-10)
+(8*n-74)*y[n-4]*(n-4)*(n-5)*(n-6)*(n-7)*(n-8)*(n-9)*(n-10)
-(9*n-18)*y[n-3]*(n-3)*(n-4)*(n-5)*(n-6)*(n-7)*(n-8)*(n-9)*(n-10)
-(2*n-15)*y[n-2]*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7)*(n-8)*(n-9)*(n-10)
+(n+2)*y[n-1]*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7)*(n-8)*(n-9)*(n-10))],n],n];
sol=Solve[Table[Coefficient[w,n,j]==0,{j,start,start-t+1,-1}]];
asympt=y[n]/.sol[[1]];
Table[Numerator[Coefficient[asympt,n,-j]],{j,0,t}] (* Vaclav Kotesovec, Apr 06 2012 *)

Terms a(5)-a(19) from Vaclav Kotesovec, Apr 06 2012 (terms a(5)-a(7) were wrong, see A089222 for more information)

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

A089222 Number of ways of seating n people around a table for the second time without anyone sitting next to the same person as they did the first time.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A078630 Numerators of coefficients of asymptotic expansion of probability p(n) (see A002816) in powers of 1/n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions