A307877 Number of ways of partitioning the set of the first n positive squares into two subsets whose sums differ at most by 1.

1, 1, 0, 0, 0, 0, 2, 1, 1, 5, 2, 1, 5, 13, 43, 43, 57, 193, 274, 239, 430, 1552, 3245, 2904, 5419, 18628, 31048, 27813, 50213, 188536, 372710, 348082, 649300, 2376996, 4197425, 3913496, 7287183, 27465147, 53072709, 50030553, 93696497, 351329160, 650125358

Offset

0,7

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Wikipedia, Partition problem

Formula

a(n) = A083527(n) if n == 0 or 3 (mod 4).

Example

a(6) = 2: 1,9,36/4,16,25; 1,4,16,25/9,36.
a(7) = 1: 1,4,16,49/9,25,36.

Maple

s:= proc(n) s(n):= `if`(n=0, 1, n^2+s(n-1)) end:
b:= proc(n, i) option remember; `if`(i=0, `if`(n<=1, 1, 0),
      `if`(n>s(i), 0, (p-> b(n+p, i-1)+b(abs(n-p), i-1))(i^2)))
    end:
a:= n-> ceil(b(0, n)/2):
seq(a(n), n=0..45);

Mathematica

s[n_] := s[n] = If[n == 0, 1, n^2 + s[n - 1]];
b[n_, i_] := b[n, i] = If[i == 0, If[n <= 1, 1, 0], If[n > s[i], 0, Function[p, b[n + p, i - 1] + b[Abs[n - p], i - 1]][i^2]]];
a[n_] := Ceiling[b[0, n]/2];
a /@ Range[0, 45] (* Jean-François Alcover, Dec 07 2020, after Alois P. Heinz *)

Crossrefs

Cf. A000290, A069918, A083527, A158092, A306443, A308682.

Sequence in context: A330964 A128704 A075259 * A259703 A316996 A169589

Adjacent sequences: A307874 A307875 A307876 * A307878 A307879 A307880

Keyword

nonn

Author

Alois P. Heinz, Jun 04 2019

Status

approved