A006456 Number of compositions (ordered partitions) of n into squares.

1, 1, 1, 1, 2, 3, 4, 5, 7, 11, 16, 22, 30, 43, 62, 88, 124, 175, 249, 354, 502, 710, 1006, 1427, 2024, 2870, 4068, 5767, 8176, 11593, 16436, 23301, 33033, 46832, 66398, 94137, 133462, 189211, 268252, 380315, 539192, 764433, 1083764, 1536498, 2178364

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..5000 (terms 0..500 from T. D. Noe)
• Jan Bohman, Carl-Erik Fröberg, Hans Riesel, 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)
• N. Robbins, On compositions whose parts are polygonal numbers, Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 239-243. See p. 242.
• Index entries for sequences related to sums of squares

Crossrefs

Cf. A280542.

Row sums of A337165.

Programs

Maple

a:= proc(n) option remember; `if`(n<0, 0,
      `if`(n=0, 1, add(a(n-j^2), j=1..isqrt(n))))
    end:
seq(a(n), n=0..44);  # Alois P. Heinz, Jul 26 2025

Mathematica

a[n_]:=a[n]=If[n==0, 1, Sum[a[n - k], {k, Select[Range[n], IntegerQ[Sqrt[#]] &]}]]; Table[a[n], {n,0,  100}] (* Indranil Ghosh, Jul 28 2017, after David W. Wilson's formula *)

PARI

N=66;  x='x+O('x^N);
Vec( 1/( 1 - sum(k=1,1+sqrtint(N), x^(k^2) ) ) )
/* Joerg Arndt, Sep 30 2012 */

Python

from gmpy2 import is_square
class Memoize:
    def _init_(self, func):
        self.func=func
        self.cache={}
    def _call_(self, arg):
        if arg not in self.cache:
            self.cache[arg] = self.func(arg)
        return self.cache[arg]
@Memoize
def a(n): return 1 if n==0 else sum([a(n - k) for k in range(1, n + 1) if is_square(k)])
print([a(n) for n in range(101)]) # Indranil Ghosh, Jul 28 2017, after David W. Wilson's formula

Formula

a(0) = 1; a(n) = Sum_{1 <= k^2 <= n} a(n-k^2), if n > 0. - David W. Wilson

G.f.: 1/(1-x-x^4-x^9-....) - Jon Perry, Jul 04 2004

a(n) ~ c * d^n, where d is the root of the equation EllipticTheta(3, 0, 1/d) = 3, d = 1.41774254618138831428829091099000662953179532057717725688..., c = 0.46542113389379672452973940263069782869244877335179331541... - Vaclav Kotesovec, May 01 2014, updated Jan 05 2017

G.f.: 2/(3 - theta_3(q)), where theta_3() is the Jacobi theta function. - Ilya Gutkovskiy, Aug 08 2018

Extensions

Name corrected by Bob Selcoe, Feb 12 2014