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

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

Comments

From Gus Wiseman, Oct 26 2025: (Start)

Also the number of integer compositions of n such that every maximal run (x,...,x) has length divisible by x. For example, the composition c = (2,2,2,2,3,3,3,1,1) has maximal runs ((2,2,2,2),(3,3,3),(1,1)), with lengths 4, 3, 2, divisible by 2, 3, 1, respectively, so c is counted under a(19). The a(1) = 1 through a(10) = 16 compositions are:

1 11 111 22 122 1122 11122 2222 333 1333

1111 221 1221 11221 111122 12222 3331

11111 2211 12211 111221 22122 112222

111111 22111 112211 22221 122122

1111111 122111 1111122 122221

221111 1111221 221122

11111111 1112211 221221

1122111 222211

1221111 11111122

2211111 11111221

111111111 11112211

11122111

11221111

12211111

22111111

1111111111

(End)

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

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

Example

From Gus Wiseman, Oct 26 2025: (Start)
The a(1) = 1 through a(9) = 11 compositions into squares:
  1  11  111  4     14     114     1114     44        9
              1111  41     141     1141     11114     144
                    11111  411     1411     11141     414
                           111111  4111     11411     441
                                   1111111  14111     111114
                                            41111     111141
                                            11111111  111411
                                                      114111
                                                      141111
                                                      411111
                                                      111111111
(End)

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 *)

Prog

(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

Crossrefs

For partitions instead of compositions we have A001156, ranks A324588.

The case without 1 is A280542.

For equality instead of divisibility we have A301503, ranks A389530.

The strict case is A331844, for partitions A033461.

Row sums of A337165.

For inequality we have A389508, ranks A389531, partitions A276429, ranks A325130.

A003242 counts anti-run (Carlitz) compositions, ranks A333489.

A011782 counts compositions.

A032020 counts strict compositions, ranks A233564.

A098124 counts compositions with maximum part = length, ranks A389532.

A238130 and A333755 count compositions by maximal runs, partitions A365676.

Cf. A000740, A008965, A070211, A098504, A107429, A175342, A275001, A280195, A280240, A325129.

Sequence in context: A046420 A108318 A358876 * A018134 A245823 A143284

Adjacent sequences: A006453 A006454 A006455 * A006457 A006458 A006459

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Name corrected by Bob Selcoe, Feb 12 2014

Status

approved