%I A002816 M3102 N1257
%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
%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.
%D A002816 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002816 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A002816 P. Poulet, Reply to Query 4750, Permutations, L'Interm\'{e}diaire des 
               Math\'{e}maticiens, 26 (1919), 117-121.
%D A002816 D. P. Robbins, The probability that neighbors remain neighbors after 
               random rearrangements, Amer. Math. Monthly, 87 (1980), 122-124.
%H A002816 B. Aspvall and F. M. Liang, <a href="http://www-db.stanford.edu/TR/cstr8x.html">
               The dinner table problem</a>, Technical Report CS-TR-80-829, Computer 
               Science Department, Stanford, California, 1980.
%H A002816 <a href="Sindx_La.html#lacings">Index entries for sequences related to 
               shoe lacings</a>
%F A002816 (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). - Poulet.
%F A002816 p(n) = exp(-2)*(1 + O(1/n)). - Aspvall and Liang.
%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;
%Y A002816 Cf. A000179 (Menage problem), A078603, A078630, A078631.
%Y A002816 Sequence in context: A027141 A002398 A110065 this_sequence A144479 A074579 
               A060880
%Y A002816 Adjacent sequences: A002813 A002814 A002815 this_sequence A002817 A002818 
               A002819
%K A002816 nonn,nice,easy
%O A002816 1,6
%A A002816 N. J. A. Sloane (njas(AT)research.att.com).
%E A002816 Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001
%E A002816 More terms from Sascha Kurz (sascha.kurz(AT)uni-bayreuth.de), Mar 22 
               2002