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

Author

Mike Zabrocki, Oct 28 2006

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A051841.

Programs

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 *)

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

Extensions

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