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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

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

Examples

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

References

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

Links

• 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

Crossrefs

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

Programs

Maple

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;

Mathematica

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

Formula

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

Extensions

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

More terms from Sascha Kurz, Mar 22 2002