A103198 Number of compositions of n into a square number of parts.

1, 1, 1, 1, 2, 5, 11, 21, 36, 58, 94, 166, 331, 716, 1574, 3368, 6892, 13447, 25127, 45391, 80428, 142615, 259085, 491855, 982400, 2045001, 4352661, 9291361, 19609786, 40574017, 81973315, 161568281, 311062991, 586764281, 1089615033, 2005257849, 3688711427

Offset: 0

Author

Vladeta Jovovic, Mar 18 2005

Keywords

• easy
• nonn

Comments

From Gus Wiseman, Jan 17 2019: (Start)

Also the number of ways to fill a square matrix with the parts of an integer partition of n. For example, the a(6) = 11 matrices are:

[6]

.

[1 1] [1 1] [1 3] [3 1] [1 1] [1 2] [1 2] [2 1] [2 1] [2 2]

[1 3] [3 1] [1 1] [1 1] [2 2] [1 2] [2 1] [1 2] [2 1] [1 1]

(End)

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3329 (terms n = 1..1000 from Vaclav Kotesovec)
• Vaclav Kotesovec, a(n+1)/a(n) as a graph

Crossrefs

Cf. A000290, A011782, A052467, A089299, A089333, A120732, A323433, A323519, A323525.

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0,
      `if`(issqr(t), 1, 0), add(b(n-j, t+1), j=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 18 2019

Mathematica

nmax = 40; Rest[CoefficientList[Series[-1/2 + EllipticTheta[3, 0, x/(1-x)]/2, {x, 0, nmax}], x]] (* Vaclav Kotesovec, Jan 03 2017 *)

Formula

a(n) = Sum_{k>=0} (x/(1-x))^(k^2).

Binomial transform of the characteristic function of squares A010052, with 0th term omitted. - Carl Najafi, Sep 09 2011

a(n) = Sum_{k >= 0} binomial(n-1,k^2-1). - Gus Wiseman, Jan 17 2019

Extensions

a(0)=1 prepended by Alois P. Heinz, Jan 18 2019