A056219 Number of partitions of n in SPM(n): these are the partitions obtained from (n) by iteration of the following transformation: p -> p' if p' is a partition (i.e., decreasing) and p' is obtained from p by removing a unit from the i-th component of p and adding one to the (i+1)-th component, for any i.

1, 2, 2, 4, 5, 6, 9, 13, 15, 19, 25, 34, 42, 51, 61, 78, 98, 122, 146, 175, 209, 253, 307, 374, 444, 524, 617, 729, 858, 1016, 1200, 1414, 1649, 1916, 2223, 2586, 2996, 3475, 4031, 4672, 5385, 6191, 7102, 8148, 9329, 10673, 12201, 13957, 15939, 18172

Offset

1,2

Comments

The SPM (Sand Pile Model) originated in physics, where it is used as a paradigm for Self-Organized Criticality. Also used in computer science as a model of distributed behavior. It is a special case of Chip Firing Game and more generally it can be viewed as a cellular automaton.

It is known that the sets SPM(n) have a lattice structure. An explicit formula is known for the (unique) fixed point of SPM(n), as well as a characterization of the elements of SPM(n).

References

George E. Andrews, Number Theory, Dover Publications, N.Y. 1971, pp 167-169.

Links

Robert Israel, Table of n, a(n) for n = 1..2000

S. Corteel and D. Gouyou-Beauchamps, Enumeration of Sand Piles, Discrete Maths, 256 (2002) 3, 625-643.

D. Dhar, P. Ruelle, S. Sen and D. Verma, Algebraic aspects of sandpile models, Journal of Physics A 28: 805-831, 1995.

E. Goles and M.A. Kiwi, Games on line graphs and sand piles, Theoretical Computer Science 115: 321-349, 1993

M. Latapy, R. Mantaci, M. Morvan and H. D. Phan, Structure of some sand piles model, Theoret. Comput. Sci. 262 (2001), 525-556.

Index entries for sequences related to cellular automata

Formula

G.f.: Sum_{n>=1} x^(n*(n+1)/2)*Product_{k=1..n} (x+1/(1-x^k)). - Vladeta Jovovic, Jun 09 2007

Example

The fifth term of the sequence is 5 since SPM(5) = { (5), (4,1), (3,2), (3,1,1), (2,2,1) }.
The seventh term of the sequence is 9 since SPM(7) = { (7), (6,1), (5,2), (4,3), (5,1,1), (4,2,1), (3,3,1), (3,2,2), (3,2,1,1) }.

Maple

N:= 100: # to get a(1) .. a(N)
g:= add(x^(n*(n+1)/2)*mul(x+1/(1-x^k), k=1..n), n=1..floor(sqrt(9+8*N)/2)):
S:= series(g, x, N+1):
seq(coeff(S, x, j), j=1..N); # Robert Israel, Oct 20 2016

Mathematica

max = 60; gf = (1/x) Sum[x^(n*(n+1)/2)*Product[(x + 1/(1-x^k)), {k, n}], {n, max}] + O[x]^max; CoefficientList[gf, x] (* Jean-François Alcover, Oct 20 2016, after Vladeta Jovovic *)
max:= 100; Rest@CoefficientList[Series[Sum[x^(n*(n+1)/2)*Product[(x +1/(1-x^k)), {k, n}], {n, Floor[Sqrt[9+8*(max)]/2]}], {x, 0, max}], x] (* G. C. Greubel, Nov 29 2019 *)

Prog

(Magma)
max:=50;
R<x>:=PowerSeriesRing(Integers(), max); b:=Coefficients(R!( (&+[x^Binomial(n+1, 2)*(&*[x + 1/(1-x^j): j in [1..n]]): n in [1..Floor(Sqrt(9+8*max)/2)]]) ));
[b[n]: n in [1..max-1]]; // G. C. Greubel, Nov 29 2019
(Sage)
max=50;
def A056219_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( sum(x^binomial(n+1, 2)*product((x + 1/(1-x^j)) for j in (1..n)) for n in (1..floor(sqrt(9+8*max)/2))) ).list()
a=A056219_list(max); a[1:] # G. C. Greubel, Nov 29 2019

Crossrefs

Cf. A166869, A166870.

Sequence in context: A121269 A211860 A250114 * A085140 A232166 A325555

Adjacent sequences: A056216 A056217 A056218 * A056220 A056221 A056222

Keyword

nonn,nice

Author

Matthieu Latapy (latapy(AT)liafa.jussieu.fr), Aug 03 2000

Status

approved