|
| |
|
|
A089222
|
|
Number of ways of sitting n people around a table for the second time without anyone sitting next to the same person as they did the first time.
|
|
4
| |
|
|
0, 0, 0, 0, 10, 36, 322, 2832, 27954, 299260, 3474482, 43546872, 586722162, 8463487844, 130214368530, 2129319003680, 36889393903794, 675098760648204, 13015877566642418, 263726707757115400, 5603148830577775218
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,5
|
|
|
COMMENTS
| A078603 counts these arrangements up to circular symmetry (i.e., two arrangements are the same if one can be rotated to give the otehr). 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). [From Joel Brewster Lewis (jblewis(AT)post.harvard.edu), Jan 28 2010]
|
|
|
REFERENCES
| J. Snell, Introduction to Probability, e-book, pp. 101 Q. 20.
Roberto Tauraso, The Dinner Table Problem: The Rectangular Case, INTEGERS, vol. 6 (2006), paper A11 (Note that in this paper a(1) = 1.)
Robert Tauraso, "The Dinner Table Problem: The Rectangular Case", Integers: Electronic Journal of Combinatorial Number Theory, Vol. 6 (2006), #A11. See Column 2 in the table on page 3.
|
|
|
LINKS
| Charles M. Grinstead & J. Laurie Snell Introduction to Probability.
Art of Problem Solving forum, Random neighbors. [From Joel Brewster Lewis (jblewis(AT)post.harvard.edu), Jan 28 2010]
|
|
|
FORMULA
| 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 * binom(n - m - 1, k - 1) * binom(m - 1, k - 1) * 2^k * n * (n - m - 1)! [From Joel Brewster Lewis, Jan 28 2010]
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]
|
|
|
EXAMPLE
| 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.
|
|
|
MATHEMATICA
| 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]);
|
|
|
CROSSREFS
| Cf. A002464.
Cf. A002816. [From Vladeta Jovovic (vladeta(AT)eunet.rs), Nov 29 2009]
A078603 [From Joel Brewster Lewis (jblewis(AT)post.harvard.edu), Jan 28 2010]
Sequence in context: A153371 A169880 A117404 * A139242 A139236 A096000
Adjacent sequences: A089219 A089220 A089221 * A089223 A089224 A089225
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Udi Hadad (somebody(AT)netvision.net.il), Dec 22 2003
|
|
|
EXTENSIONS
| Tauraso reference from Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Dec 21 2006
More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Nov 29 2009
|
| |
|
|
