A001156 Number of partitions of n into squares.
1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 8, 9, 10, 10, 12, 13, 14, 14, 16, 19, 20, 21, 23, 26, 27, 28, 31, 34, 37, 38, 43, 46, 49, 50, 55, 60, 63, 66, 71, 78, 81, 84, 90, 98, 104, 107, 116, 124, 132, 135, 144, 154, 163, 169, 178, 192, 201, 209, 220, 235, 247, 256
Offset: 0
Examples
p_{4*square}(23)=1 because 23 = 3^2 + 3^2 + 2^2 + 1^2 and there is no other partition of 23 into squares.
G.f.: A(x) = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 2*x^7 +...
such that the g.f. A(x) satisfies the identity [_Paul D. Hanna_]:
A(x) = 1/((1-x)*(1-x^4)*(1-x^9)*(1-x^16)*(1-x^25)*...)
A(x) = 1 + x/(1-x) + x^4/((1-x)*(1-x^4)) + x^9/((1-x)*(1-x^4)*(1-x^9)) + x^16/((1-x)*(1-x^4)*(1-x^9)*(1-x^16)) + ...
From _Gus Wiseman_, Mar 09 2019: (Start)
The a(14) = 6 integer partitions into squares are:
(941)
(911111)
(44411)
(44111111)
(41111111111)
(11111111111111)
while the a(14) = 6 integer partitions in which the multiplicity of k is a multiple of k for all k are:
(333221)
(33311111)
(22222211)
(2222111111)
(221111111111)
(11111111111111)
(End)
References
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
- J. Bohman et al., Partitions in squares, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301.
- J. Bohman et al., Partitions in squares, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301. (Annotated scanned copy)
- H. L. Fisher, Letter to N. J. A. Sloane, Mar 16 1989
- G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis, Proceedings of the London Mathematical Society, 2, XVI, 1917, p. 373.
- M. D. Hirschhorn and J. A. Sellers, On a problem of Lehmer on partitions into squares, The Ramanujan Journal 8 (2004), 279-287.
- F. Iacobescu, Smarandache Partition Type and Other Sequences, Bull. Pure Appl. Sci. 16E, 237-240, 1997.
- Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
- Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
- James A. Sellers, Partitions Excluding Specific Polygonal Numbers As Parts, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.
- F. Smarandache, Sequences of Numbers Involved in Unsolved Problems, Hexis, Phoenix, 2006.
- Florentin Smarandache, Sequences of Numbers Involved in Unsolved Problems, arXiv:math/0604019 [math.GM], 2006.
- Eric Weisstein's World of Mathematics, Partition
- Eric Weisstein's World of Mathematics, Smarandache Sequences
- Eric Weisstein's World of Mathematics, Square Number
Crossrefs
Programs
-
Haskell
a001156 = p (tail a000290_list) where p _ 0 = 1 p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m -- Reinhard Zumkeller, Oct 31 2012, Aug 14 2011
-
Magma
m:=70; R
:=PowerSeriesRing(Integers(), m); Coefficients(R!( (&*[1/(1-x^(k^2)): k in [1..(m+2)]]) )); // G. C. Greubel, Nov 11 2018 -
Maple
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, b(n, i-1)+ `if`(i^2>n, 0, b(n-i^2, i)))) end: a:= n-> b(n, isqrt(n)): seq(a(n), n=0..120); # Alois P. Heinz, May 30 2014 -
Mathematica
CoefficientList[ Series[Product[1/(1 - x^(m^2)), {m, 70}], {x, 0, 68}], x] (* Or *) Join[{1}, Table[Length@PowersRepresentations[n, n, 2], {n, 68}]] (* Robert G. Wilson v, Apr 12 2005, revised Sep 27 2011 *) f[n_] := Length@ IntegerPartitions[n, All, Range@ Sqrt@ n^2]; Array[f, 67] (* Robert G. Wilson v, Apr 14 2013 *) b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i^2>n, 0, b[n-i^2, i]]]]; a[n_] := b[n, Sqrt[n]//Floor]; Table[a[n], {n, 0, 120}] (* Jean-François Alcover, Nov 02 2015, after Alois P. Heinz *) -
PARI
{a(n)=polcoeff(1/prod(k=1, sqrtint(n+1), 1-x^(k^2)+x*O(x^n)), n)} \\ Paul D. Hanna, Mar 09 2012 -
PARI
{a(n)=polcoeff(1+sum(m=1, sqrtint(n+1), x^(m^2)/prod(k=1, m, 1-x^(k^2)+x*O(x^n))), n)} \\ Paul D. Hanna, Mar 09 2012
Formula
G.f.: Product_{m>=1} 1/(1-x^(m^2)).
G.f.: Sum_{n>=0} x^(n^2) / Product_{k=1..n} (1 - x^(k^2)). - Paul D. Hanna, Mar 09 2012
a(n) = (1/n)*Sum_{k=1..n} A035316(k)*a(n-k). - Vladeta Jovovic, Nov 20 2002
a(n) = f(n,1,3) with f(x,y,z) = if xReinhard Zumkeller, Nov 08 2009
Conjecture (Jan Bohman, Carl-Erik Fröberg, Hans Riesel, 1979): a(n) ~ c * n^(-alfa) * exp(beta*n^(1/3)), where c = 1/18.79656, beta = 3.30716, alfa = 1.16022. - Vaclav Kotesovec, Aug 19 2015
From Vaclav Kotesovec, Dec 29 2016: (Start)
Correct values of these constants are:
1/c = sqrt(3) * (4*Pi)^(7/6) / Zeta(3/2)^(2/3) = 17.49638865935104978665...
alfa = 7/6 = 1.16666666666666666...
beta = 3/2 * (Pi/2)^(1/3) * Zeta(3/2)^(2/3) = 3.307411783596651987...
a(n) ~ 3^(-1/2) * (4*Pi*n)^(-7/6) * Zeta(3/2)^(2/3) * exp(2^(-4/3) * 3 * Pi^(1/3) * Zeta(3/2)^(2/3) * n^(1/3)). [Hardy & Ramanujan, 1917]
(End)
Extensions
More terms from Eric W. Weisstein
More terms from Gh. Niculescu (ghniculescu(AT)yahoo.com), Oct 08 2006
Comments