1,6

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.

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.

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

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

p(n) = exp(-2)*(1 + O(1/n)). - Aspvall and Liang.

a(6)=3: 135264, 136425, 142635.

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;

Cf. A000179 (Menage problem), A078603, A078630, A078631.

Sequence in context: A027141 A002398 A110065 this_sequence A074579 A060880 A093155

Adjacent sequences: A002813 A002814 A002815 this_sequence A002817 A002818 A002819

nonn,nice,easy

njas

Entry improved by Michael Steyer (m.steyer(AT)osram.de), Aug 30 2001

More terms from Sascha Kurz (sascha.kurz(AT)uni-bayreuth.de), Mar 22 2002