cp's OEIS Frontend

A033461 Number of partitions of n into distinct squares.

%I A033461 #90 Jul 28 2025 20:17:37
%S A033461 1,1,0,0,1,1,0,0,0,1,1,0,0,1,1,0,1,1,0,0,1,1,0,0,0,2,2,0,0,2,2,0,0,0,
%T A033461 1,1,1,1,1,1,1,2,1,0,0,2,2,0,0,2,3,1,1,2,2,1,1,1,1,1,0,2,3,1,1,4,3,0,
%U A033461 1,2,2,1,0,1,4,3,0,2,4,2,1,3,2,1,2,3,3,2,1,3,6,3,0,2,5,3,0,1,3,3,3,4
%N A033461 Number of partitions of n into distinct squares.
%C A033461 "WEIGH" transform of squares A000290.
%C A033461 a(n) = 0 for n in {A001422}, a(n) > 0 for n in {A003995}. - _Alois P. Heinz_, May 14 2014
%C A033461 Number of partitions of n in which each part i has multiplicity i. Example: a(50)=3 because we have [1,2,2,3,3,3,6,6,6,6,6,6], [1,7,7,7,7,7,7,7], and [3,3,3,4,4,4,4,5,5,5,5,5]. - _Emeric Deutsch_, Jan 26 2016
%C A033461 The Heinz numbers of integer partitions into distinct pairs are given by A324587. - _Gus Wiseman_, Mar 09 2019
%C A033461 From _Gus Wiseman_, Mar 09 2019: (Start)
%C A033461 Equivalent to _Emeric Deutsch_'s comment, a(n) is the number of integer partitions of n where the multiplicities (where if x < y the multiplicity of x is counted prior to the multiplicity of y) are equal to the distinct parts in increasing order. The Heinz numbers of these partitions are given by A109298. For example, the first 30 terms count the following integer partitions:
%C A033461    1: (1)
%C A033461    4: (22)
%C A033461    5: (221)
%C A033461    9: (333)
%C A033461   10: (3331)
%C A033461   13: (33322)
%C A033461   14: (333221)
%C A033461   16: (4444)
%C A033461   17: (44441)
%C A033461   20: (444422)
%C A033461   21: (4444221)
%C A033461   25: (55555)
%C A033461   25: (4444333)
%C A033461   26: (555551)
%C A033461   26: (44443331)
%C A033461   29: (5555522)
%C A033461   29: (444433322)
%C A033461   30: (55555221)
%C A033461   30: (4444333221)
%C A033461 The case where the distinct parts are taken in decreasing order is A324572, with Heinz numbers given by A324571.
%C A033461 (End)
%D A033461 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 288-289.
%H A033461 Alois P. Heinz, <a href="/A033461/b033461.txt">Table of n, a(n) for n = 0..10000</a> (first 1001 terms from T. D. Noe)
%H A033461 M. Brack, M. V. N. Murthy, and J. Bartel, <a href="https://homepages.uni-regensburg.de/~brm04014/notes/F2Kaz4.pdf">Application of semiclassical methods to number theory</a>, University of Regensburg (Germany, 2020).
%H A033461 Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449 [math.CO], 2018.
%H A033461 Vaclav Kotesovec, <a href="/A033461/a033461.jpg">Graph - The asymptotic ratio</a>.
%H A033461 M. V. N. Murthy, Matthias Brack, Rajat K. Bhaduri, and Johann Bartel, <a href="https://arxiv.org/abs/1808.05146">Semi-classical analysis of distinct square partitions</a>, arXiv:1808.05146 [cond-mat.stat-mech], 2018.
%F A033461 G.f.: Product_{n>=1} ( 1+x^(n^2) ).
%F A033461 a(n) ~ exp(3 * 2^(-5/3) * Pi^(1/3) * ((sqrt(2)-1)*zeta(3/2))^(2/3) * n^(1/3)) * ((sqrt(2)-1)*zeta(3/2))^(1/3) / (2^(4/3) * sqrt(3) * Pi^(1/3) * n^(5/6)), where zeta(3/2) = A078434. - _Vaclav Kotesovec_, Dec 09 2016
%F A033461 See Murthy, Brack, Bhaduri, Bartel (2018) for a more complete asymptotic expansion. - _N. J. A. Sloane_, Aug 17 2018
%e A033461 a(50)=3 because we have [1,4,9,36], [1,49], and [9,16,25]. - _Emeric Deutsch_, Jan 26 2016
%e A033461 From _Gus Wiseman_, Mar 09 2019: (Start)
%e A033461 The first 30 terms count the following integer partitions:
%e A033461    1: (1)
%e A033461    4: (4)
%e A033461    5: (4,1)
%e A033461    9: (9)
%e A033461   10: (9,1)
%e A033461   13: (9,4)
%e A033461   14: (9,4,1)
%e A033461   16: (16)
%e A033461   17: (16,1)
%e A033461   20: (16,4)
%e A033461   21: (16,4,1)
%e A033461   25: (25)
%e A033461   25: (16,9)
%e A033461   26: (25,1)
%e A033461   26: (16,9,1)
%e A033461   29: (25,4)
%e A033461   29: (16,9,4)
%e A033461   30: (25,4,1)
%e A033461   30: (16,9,4,1)
%e A033461 (End)
%p A033461 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A033461        b(n, i-1) +`if`(i^2>n, 0, b(n-i^2, i-1))))
%p A033461     end:
%p A033461 a:= n-> b(n, isqrt(n)):
%p A033461 seq(a(n), n=0..100);  # _Alois P. Heinz_, May 14 2014
%t A033461 nn=10; CoefficientList[Series[Product[(1+x^(k*k)), {k,nn}], {x,0,nn*nn}], x] (* _T. D. Noe_, Jul 24 2006 *)
%t A033461 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-1]]]]; a[n_] := b[n, Floor[Sqrt[n]]]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Sep 21 2015, after _Alois P. Heinz_ *)
%t A033461 nmax = 20; poly = ConstantArray[0, nmax^2 + 1]; poly[[1]] = 1; poly[[2]] = 1; Do[Do[poly[[j + 1]] += poly[[j - k^2 + 1]], {j, nmax^2, k^2, -1}];, {k, 2, nmax}]; poly (* _Vaclav Kotesovec_, Dec 09 2016 *)
%t A033461 Table[Length[Select[IntegerPartitions[n],Reverse[Union[#]]==Length/@Split[#]&]],{n,30}] (* _Gus Wiseman_, Mar 09 2019 *)
%o A033461 (PARI) a(n)=polcoeff(prod(k=1,sqrt(n),1+x^k^2), n)
%o A033461 (PARI) first(n)=Vec(prod(k=1,sqrtint(n),1+'x^k^2,O('x^(n+1))+1)) \\ _Charles R Greathouse IV_, Sep 03 2015
%o A033461 (Python)
%o A033461 from functools import cache
%o A033461 from sympy.core.power import isqrt
%o A033461 @cache
%o A033461 def b(n,i):
%o A033461   # Code after _Alois P. Heinz_
%o A033461   if n == 0: return 1
%o A033461   if i == 0: return 0
%o A033461   i2 = i*i
%o A033461   return b(n, i-1) + (0 if i2 > n else b(n - i2, i-1))
%o A033461 a = lambda n: b(n, isqrt(n))
%o A033461 print([a(n) for n in range(1, 101)]) # _Darío Clavijo_, Nov 30 2023
%Y A033461 Cf. A001422, A003995, A078434, A242434 (the same for compositions), A279329.
%Y A033461 Cf. A001156 (non-strict case), A001462, A005117, A052335, A078135, A109298, A114638, A117144, A324571, A324572, A324587, A324588.
%Y A033461 Row sums of A341040.
%K A033461 nonn,nice
%O A033461 0,26
%A A033461 _N. J. A. Sloane_
%E A033461 More terms from _Michael Somos_