A260755 Number of ways to relax the chip-configuration of Anderson et al. one chip at a time.

1, 1, 1, 2, 4, 252, 2304, 343712160, 17361257184, 817232021393069622912, 337615438409845853800240, 1002314950534089781700930298791626826040504, 4687493998578314511363173974007271386258869456

Offset

1,4

Comments

Terms grow cubic-exponentially but have unexpectedly many small prime factors.

Links

Table of n, a(n) for n=1..13.

R. Anderson, L. Lovász, P. Shor, J. Spencer, E. Tardos, S. Winograd, Disks, balls and walls: analysis of a combinatorial game, Amer. Math. Monthly, 6, 96, pp. 481-493, 1989.

James Propp, Games of No Strategy and Low-Grade Combinatorics (2015)

Example

For n=4, 00400 relaxes to 01210 which relaxes to 02020. At this point, there are two ways to finish the game, so a(4)=2.

Mathematica

relax[L_] :=
relax[L] =
  If[Min[L] < 0, 0,
   If[Max[L] <= 1, 1,
    Sum[relax[
      Table[If[i == k - 1 || i == k + 1, L[[i]] + 1,
        If[i == k, L[[i]] - 2, L[[i]]]], {i, 1, Length[L]}]], {k, 2,
      Length[L] - 1}]]]
a[n_] := relax[
  Join[Append[Table[0, {Floor[n/2]}], n], Table[0, {Floor[n/2]}]]]

Crossrefs

Sequence in context: A005275 A009673 A018770 * A173566 A271551 A058990

Adjacent sequences: A260752 A260753 A260754 * A260756 A260757 A260758

Keyword

nonn

Author

James Propp, Jul 30 2015

Status

approved