A123915 Number of binary words whose (unique) decreasing Lyndon decomposition is into Lyndon words each with an even number of 1's; EULER transform of A051841.

1, 1, 1, 2, 3, 6, 11, 21, 39, 75, 143, 275, 528, 1020, 1971, 3821, 7414, 14419, 28072, 54739, 106847, 208815, 408470, 799806, 1567333, 3073916, 6032971, 11848693, 23285202, 45787650, 90085410, 177331748, 349243800, 688129474, 1356433342, 2674877358, 5276869233

Offset

0,4

Links

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

Formula

Prod_{n>=1} 1/(1-q^n)^A051841(n) = 1+sum_{n>=1} a(n) q^n.

a(n) ~ c * 2^n / sqrt(n), where c = 0.466342789995157602308480670781344540837057109916338560252870092619488755668... - Vaclav Kotesovec, May 31 2019

Example

The binary words 00000, 01100, 00110, 01111, 00011, 00101 of length 5 decompose as 0*0*0*0*0, 011*0*0, 0011*0, 01111, 00011, 00101 and each subword has an even number of 1's, therefore a(5)=6.

Maple

with(numtheory):
b:= proc(n) option remember; add(igcd(d, 2)*
      2^(n/d)*mobius(d), d=divisors(n))/(2*n)
    end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(
      d*b(d), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 28 2017

Mathematica

b[n_] := b[n] = Sum[GCD[d, 2] 2^(n/d) MoebiusMu[d], {d, Divisors[n]}]/(2n);
a[n_] := a[n] = If[n==0, 1, Sum[Sum[d b[d], {d, Divisors[j]}] a[n-j], {j, 1, n}]/n];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 19 2020, after Alois P. Heinz *)

Crossrefs

Cf. A051841.

Sequence in context: A113409 A092684 A366107 * A132832 A316796 A079116

Adjacent sequences: A123912 A123913 A123914 * A123916 A123917 A123918

Keyword

nonn

Author

Mike Zabrocki, Oct 28 2006

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 28 2017

Status

approved