

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)/((n1)!/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 ncycle graph.  Andrew Howroyd, Mar 15 2016


REFERENCES

P. Poulet, Reply to Query 4750, Permutations, L'Intermédiaire des Mathématiciens, 26 (1919), 117121.
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 CSTR80829, Computer Science Department, Stanford, California, 1980.
D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly 87 (1980), 122124.
Index entries for sequences related to shoe lacings


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)/(n1)! ~ 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 := (n1)!/2 + (1)^n; for k from 1 to n1 do for j from 1 to min(nk, k) do sum := sum+(1)^k*binomial(k1, j1)*binomial(nk, j)*n/(nk)*(nk1)!/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 * A144479 A074579 A060880
Adjacent sequences: A002813 A002814 A002815 * A002817 A002818 A002819


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001
More terms from Sascha Kurz, Mar 22 2002


STATUS

approved



