This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002816 Number of polygons that can be formed from n points on a circle, no two adjacent. (Formerly M3102 N1257) 7
 1, 0, 0, 0, 1, 3, 23, 177, 1553, 14963, 157931, 1814453, 22566237, 302267423, 4340478951, 66541218865, 1084982173641, 18752743351339, 342523093859011, 6593167693927885, 133408305489947029, 2831112931136162775 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,6 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 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. FORMULA (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 EXAMPLE a(6)=3: 135264, 136425, 142635. 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 *) CROSSREFS Cf. A000179 (Ménage problem), A078603, A078630, A078631, A242522 (Hamiltonian cycles in complement of path), A006184. Sequence in context: A027141 A002398 A110065 * A320265 A144479 A074579 Adjacent sequences:  A002813 A002814 A002815 * A002817 A002818 A002819 KEYWORD nonn,nice,easy AUTHOR EXTENSIONS Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001 More terms from Sascha Kurz, Mar 22 2002 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 23 11:44 EDT 2019. Contains 325254 sequences. (Running on oeis4.)