A339426 Number of compositions (ordered partitions) of n into an even number of powers of 2.

1, 0, 1, 2, 2, 6, 9, 14, 30, 48, 86, 156, 268, 478, 849, 1486, 2638, 4660, 8214, 14532, 25664, 45304, 80078, 141412, 249768, 441276, 779376, 1376696, 2431924, 4295534, 7587753, 13403102, 23674870, 41819588, 73870046, 130483396, 230486384, 407130332, 719153726

Offset

0,4

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} A023359(k) * A339422(n-k).

Example

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

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, 1):
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, A034008, A040039, A339422, A339427.

Sequence in context: A188808 A021819 A359896 * A000021 A367718 A000022

Adjacent sequences: A339423 A339424 A339425 * A339427 A339428 A339429

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 03 2020

Status

approved