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

Author

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

Keywords

• nonn
• nice

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

Examples

			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) }.
		

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

Crossrefs

Cf. A166869, A166870.

Programs

Magma

max:=50;
R:=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

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 *)

Sage

max=50;
def A056219_list(prec):
    P. = 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

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