login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

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

REFERENCES

P. Poulet, Reply to Query 4750, Permutations, L'Interm\'{e}diaire des Math\'{e}maticiens, 26 (1919), 117-121.

D. P. Robbins, The probability that neighbors remain neighbors after random rearrangements, Amer. Math. Monthly, 87 (1980), 122-124.

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.

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)/(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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 23 04:43 EDT 2014. Contains 240909 sequences.