|
%I #44 Feb 17 2022 01:04:11
%S 1,2,2,4,5,6,9,13,15,19,25,34,42,51,61,78,98,122,146,175,209,253,307,
%T 374,444,524,617,729,858,1016,1200,1414,1649,1916,2223,2586,2996,3475,
%U 4031,4672,5385,6191,7102,8148,9329,10673,12201,13957,15939,18172
%N 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.
%C 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.
%C 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).
%D George E. Andrews, Number Theory, Dover Publications, N.Y. 1971, pp 167-169.
%H Robert Israel, <a href="/A056219/b056219.txt">Table of n, a(n) for n = 1..2000</a>
%H S. Corteel and D. Gouyou-Beauchamps, <a href="https://doi.org/10.1016/S0012-365X(02)00339-4">Enumeration of Sand Piles</a>, Discrete Maths, 256 (2002) 3, 625-643.
%H D. Dhar, P. Ruelle, S. Sen and D. Verma, <a href="http://dx.doi.org/10.1088/0305-4470/28/4/009">Algebraic aspects of sandpile models</a>, Journal of Physics A 28: 805-831, 1995.
%H E. Goles and M.A. Kiwi, <a href="http://dx.doi.org/10.1016/0304-3975(93)90122-A">Games on line graphs and sand piles</a>, Theoretical Computer Science 115: 321-349, 1993
%H M. Latapy, R. Mantaci, M. Morvan and H. D. Phan, <a href="http://dx.doi.org/10.1016/S0304-3975(00)00363-7">Structure of some sand piles model</a>, Theoret. Comput. Sci. 262 (2001), 525-556.
%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%F G.f.: Sum_{n>=1} x^(n*(n+1)/2)*Product_{k=1..n} (x+1/(1-x^k)). - _Vladeta Jovovic_, Jun 09 2007
%e The fifth term of the sequence is 5 since SPM(5) = { (5), (4,1), (3,2), (3,1,1), (2,2,1) }.
%e 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) }.
%p N:= 100: # to get a(1) .. a(N)
%p g:= add(x^(n*(n+1)/2)*mul(x+1/(1-x^k),k=1..n),n=1..floor(sqrt(9+8*N)/2)):
%p S:= series(g,x,N+1):
%p seq(coeff(S,x,j),j=1..N); # _Robert Israel_, Oct 20 2016
%t 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_ *)
%t 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 *)
%o (Magma)
%o max:=50;
%o 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)]]) ));
%o [b[n]: n in [1..max-1]]; // _G. C. Greubel_, Nov 29 2019
%o (Sage)
%o max=50;
%o def A056219_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o 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()
%o a=A056219_list(max); a[1:] # _G. C. Greubel_, Nov 29 2019
%Y Cf. A166869, A166870.
%K nonn,nice
%O 1,2
%A Matthieu Latapy (latapy(AT)liafa.jussieu.fr), Aug 03 2000
|
