A033461 Number of partitions of n into distinct squares.

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, 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, 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

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

"WEIGH" transform of squares A000290.

a(n) = 0 for n in {A001422}, a(n) > 0 for n in {A003995}. - Alois P. Heinz, May 14 2014

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

The Heinz numbers of integer partitions into distinct pairs are given by A324587. - Gus Wiseman, Mar 09 2019

From Gus Wiseman, Mar 09 2019: (Start)

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:

1: (1)

4: (22)

5: (221)

9: (333)

10: (3331)

13: (33322)

14: (333221)

16: (4444)

17: (44441)

20: (444422)

21: (4444221)

25: (55555)

25: (4444333)

26: (555551)

26: (44443331)

29: (5555522)

29: (444433322)

30: (55555221)

30: (4444333221)

The case where the distinct parts are taken in decreasing order is A324572, with Heinz numbers given by A324571.

(End)

Examples

			a(50)=3 because we have [1,4,9,36], [1,49], and [9,16,25]. - _Emeric Deutsch_, Jan 26 2016
From _Gus Wiseman_, Mar 09 2019: (Start)
The first 30 terms count the following integer partitions:
   1: (1)
   4: (4)
   5: (4,1)
   9: (9)
  10: (9,1)
  13: (9,4)
  14: (9,4,1)
  16: (16)
  17: (16,1)
  20: (16,4)
  21: (16,4,1)
  25: (25)
  25: (16,9)
  26: (25,1)
  26: (16,9,1)
  29: (25,4)
  29: (16,9,4)
  30: (25,4,1)
  30: (16,9,4,1)
(End)
		

References

• James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 288-289.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
• M. Brack, M. V. N. Murthy, and J. Bartel, Application of semiclassical methods to number theory, University of Regensburg (Germany, 2020).
• Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
• Vaclav Kotesovec, Graph - The asymptotic ratio.
• M. V. N. Murthy, Matthias Brack, Rajat K. Bhaduri, and Johann Bartel, Semi-classical analysis of distinct square partitions, arXiv:1808.05146 [cond-mat.stat-mech], 2018.

Crossrefs

Cf. A001422, A003995, A078434, A242434 (the same for compositions), A279329.

Cf. A001156 (non-strict case), A001462, A005117, A052335, A078135, A109298, A114638, A117144, A324571, A324572, A324587, A324588.

Row sums of A341040.

Programs

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-1))))
    end:
a:= n-> b(n, isqrt(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, May 14 2014

Mathematica

nn=10; CoefficientList[Series[Product[(1+x^(k*k)), {k,nn}], {x,0,nn*nn}], x] (* T. D. Noe, Jul 24 2006 *)
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 *)
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 *)
Table[Length[Select[IntegerPartitions[n],Reverse[Union[#]]==Length/@Split[#]&]],{n,30}] (* Gus Wiseman, Mar 09 2019 *)

PARI

a(n)=polcoeff(prod(k=1,sqrt(n),1+x^k^2), n)

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

Python

from functools import cache
from sympy.core.power import isqrt
@cache
def b(n,i):
  # Code after Alois P. Heinz
  if n == 0: return 1
  if i == 0: return 0
  i2 = i*i
  return b(n, i-1) + (0 if i2 > n else b(n - i2, i-1))
a = lambda n: b(n, isqrt(n))
print([a(n) for n in range(1, 101)]) # Darío Clavijo, Nov 30 2023

Formula

G.f.: Product_{n>=1} ( 1+x^(n^2) ).

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

See Murthy, Brack, Bhaduri, Bartel (2018) for a more complete asymptotic expansion. - N. J. A. Sloane, Aug 17 2018

Extensions

More terms from Michael Somos