cp's OEIS Frontend

A089222 Number of ways of seating n people around a table for the second time without anyone sitting next to the same person as they did the first time.

%I A089222 #61 Aug 10 2025 11:56:57
%S A089222 1,0,0,0,0,10,36,322,2832,27954,299260,3474482,43546872,586722162,
%T A089222 8463487844,130214368530,2129319003680,36889393903794,675098760648204,
%U A089222 13015877566642418,263726707757115400,5603148830577775218,124568968969991162100,2892414672938546871250
%N A089222 Number of ways of seating n people around a table for the second time without anyone sitting next to the same person as they did the first time.
%C A089222 A078603 counts these arrangements up to circular symmetry (i.e., two arrangements are the same if one can be rotated to give the other). A002816 counts them up to dihedral symmetry (i.e., two arrangements are the same if one can be rotated or reflected to give the other). - _Joel B. Lewis_, Jan 28 2010
%D A089222 J. Snell, Introduction to Probability, e-book, pp. 101 Q. 20.
%H A089222 Vincenzo Librandi, <a href="/A089222/b089222.txt">Table of n, a(n) for n = 0..200</a>
%H A089222 Art of Problem Solving forum, <a href="https://artofproblemsolving.com/community/c6h327208">Random neighbors</a>. - _Joel B. Lewis_, Jan 28 2010
%H A089222 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 A089222 Charles M. Grinstead and J. Laurie Snell, <a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html">Introduction to Probability</a>.
%H A089222 Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 626.
%H A089222 Roberto Tauraso, <a href="http://www.emis.de/journals/INTEGERS/papers/g11/g11.Abstract.html">The Dinner Table Problem: The Rectangular Case</a>, INTEGERS: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. Note that in this paper a(1) = 1. See Column 2 in the table on page 3.
%F A089222 Inclusion-exclusion gives that for n > 2, we have a(n) = n! + 2*n*(-1)^n + Sum_{1 <= k <= m < n} (-1)^m * (n/k) * binomial(n-m-1, k-1) * binomial(m-1, k-1) * 2^k * n * (n-m-1)!. - _Joel B. Lewis_, Jan 28 2010
%F A089222 a(n) = (3*n-30)*a(n-11) + (6*n-45)*a(n-10) + (5*n+18)*a(n-9) - (8*n-139)*a(n-8) - (26*n-204)*a(n-7) - (4*n-30)*a(n-6) + (26*n-148)*a(n-5) + (8*n-74)*a(n-4) - (9*n-18)*a(n-3) - (2*n-15)*a(n-2) + (n+2)*a(n-1), n >= 14. - _Vaclav Kotesovec_, Apr 13 2010
%F A089222 The asymptotic expansion from article by Aspvall and Liang (also cited in article by Tauraso) is wrong. Bad terms are 736/(15*n^5) + 8428/(45*n^6) + 40174/(63*n^7). Right asymptotic formula is a(n) ~ (n!/e^2)*(1 - 4/n + 20/(3*n^3) + 58/(3*n^4) + 796/(15*n^5) + 7858/(45*n^6) + 40324/(63*n^7) + 140194/(63*n^8) + ...). Verified also numerically. For example, for n=200, exact/asymptotic results are 1.0000000000125542243 (Aspvall + Liang), 1.0000000000000008990 (Kotesovec 7 terms) or 1.0000000000000000121 (Kotesovec 8 terms). - _Vaclav Kotesovec_, Apr 06 2012
%F A089222 a(n) = 2*n*A002816(n) for n > 1. - _Martin Renner_, Apr 01 2022
%e A089222 a(4)=0 because trying to arrange 1,2,3,4 around a table will always give a couple who is sitting next to each other and differ by 1.
%t A089222 Same[cperm_, n_] := ( For[same = False; i = 2, (i <= n) && ! same, i++, same = ((Mod[cperm[[i - 1]], n] + 1) == cperm[[i]]) || ((Mod[cperm[[ i]], n] + 1) == cperm[[i - 1]])]; same = same || ((Mod[cperm[[n]], n] + 1) == cperm[[1]]) || ((Mod[ cperm[[1]], n] + 1) == cperm[[n]]); Return[same]); CntSame[n_] := (allPerms = Permutations[Range[n]]; count = 0; For[j = 1, j <= n!, j++, perm = allPerms[[j]]; If[ ! Same[perm, n], count++ ]]; Return[count]);
%t A089222 (* or direct computation of terms *)
%t A089222 Table[If[n<3, 0, n! + (-1)^n*2n + Sum[(-1)^r*(n/(n-r))^2 * (n-r)! * Sum[2^c * Binomial[r-1,c-1] * Binomial[n-r,c], {c,1,r}], {r,1,n-1}]], {n,1,25}] (* _Vaclav Kotesovec_, Apr 06 2012 *)
%Y A089222 Cf. A002464, A002816, A078603, A078630, A078631.
%K A089222 nonn,nice
%O A089222 0,6
%A A089222 Udi Hadad (somebody(AT)netvision.net.il), Dec 22 2003
%E A089222 Tauraso reference from _Parthasarathy Nambi_, Dec 21 2006
%E A089222 More terms from _Vladeta Jovovic_, Nov 29 2009
%E A089222 a(0)=1 prepended by _Alois P. Heinz_, Jul 31 2019