cp's OEIS Frontend

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

%I A002816 M3102 N1257 #58 Feb 16 2025 08:32:26
%S A002816 1,0,0,0,1,3,23,177,1553,14963,157931,1814453,22566237,302267423,
%T A002816 4340478951,66541218865,1084982173641,18752743351339,342523093859011,
%U A002816 6593167693927885,133408305489947029,2831112931136162775,62878579846490149375,1458746608689369440265
%N A002816 Number of polygons that can be formed from n points on a circle, no two adjacent.
%C A002816 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).
%C A002816 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.
%C A002816 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.
%C A002816 Number of Hamiltonian cycles in the complement of C_n where C_n is the n-cycle graph. - _Andrew Howroyd_, Mar 15 2016
%D A002816 P. Poulet, Reply to Query 4750, Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117-121.
%D A002816 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002816 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002816 T. D. Noe, <a href="/A002816/b002816.txt">Table of n, a(n) for n = 1..100</a>
%H A002816 B. Aspvall and F. M. Liang, <a href="http://infolab.stanford.edu/TR/CS-TR-80-829.html">The dinner table problem</a>, Technical Report CS-TR-80-829, Computer Science Department, Stanford, California, 1980.
%H A002816 D. P. Robbins, <a href="http://www.jstor.org/stable/2321990">The probability that neighbors remain neighbors after random rearrangements</a>, Amer. Math. Monthly 87 (1980), 122-124.
%H A002816 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CycleComplementGraph.html">Cycle Complement Graph</a>
%H A002816 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H A002816 <a href="/index/La#lacings">Index entries for sequences related to shoe lacings</a>
%F A002816 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.
%F A002816 p(n) = exp(-2)*(1 + O(1/n)). - Aspvall and Liang.
%F A002816 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
%e A002816 a(6)=3: 135264, 136425, 142635.
%p A002816 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 A002816 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 *)
%t A002816 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 *)
%Y A002816 Cf. A000179 (Ménage problem), A078603, A078630, A078631, A242522 (Hamiltonian cycles in complement of path), A006184, left column of A326411.
%K A002816 nonn,nice,easy
%O A002816 1,6
%A A002816 _N. J. A. Sloane_
%E A002816 Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001
%E A002816 More terms from _Sascha Kurz_, Mar 22 2002