A339427 Number of compositions (ordered partitions) of n into an odd number of powers of 2.

0, 1, 1, 1, 4, 4, 9, 17, 26, 50, 88, 150, 274, 478, 841, 1497, 2634, 4650, 8234, 14518, 25654, 45340, 80040, 141414, 249822, 441192, 779422, 1376752, 2431772, 4295678, 7587761, 13402881, 23675186, 41819442, 73869802, 130483966, 230485902, 407130212, 719154602

Offset

0,5

Links

Table of n, a(n) for n=0..38.

Index entries for sequences related to compositions

Formula

G.f.: (1/2) * (1 / (1 - Sum_{k>=0} x^(2^k)) - 1 / (1 + Sum_{k>=0} x^(2^k))).

a(n) = (A023359(n) - A339422(n)) / 2.

a(n) = -Sum_{k=0..n-1} A023359(k) * A339422(n-k).

Example

a(5) = 4 because we have [2, 2, 1], [2, 1, 2], [1, 2, 2] and [1, 1, 1, 1, 1].

Maple

b:= proc(n, t) option remember; `if`(n=0, t,
      add(b(n-2^i, 1-t), i=0..ilog2(n)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Dec 03 2020

Mathematica

nmax = 38; CoefficientList[Series[(1/2) (1/(1 - Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}]) - 1/(1 + Sum[x^(2^k), {k, 0, Floor[Log[2, nmax]] + 1}])), {x, 0, nmax}], x]

Crossrefs

Cf. A000079, A023359, A040039, A166444, A339422, A339426.

Sequence in context: A059815 A202670 A203003 * A319646 A214826 A135065

Adjacent sequences: A339424 A339425 A339426 * A339428 A339429 A339430

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 03 2020

Status

approved