|
| |
|
|
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 (Menage 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
|
| |
|
|
