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

1, 1, 2, 3, 6, 10, 19, 34, 65, 120, 229, 432, 829, 1583, 3051, 5874, 11370, 22012, 42756, 83113, 161917, 315723, 616588, 1205232, 2358604, 4619485, 9055960, 17766086, 34880215, 68524486, 134707150, 264960828, 521449025

Offset: 1

Author

Mike Zabrocki, Oct 28 2006

Keywords

• nonn

Examples

			The binary words 1111, 1101, 1001, 0101, 0111, 0001 of length 4 decompose as 1*1*1*1, 1*1*01, 1*001, 01*01, 0111, 0001 and each subword has an odd number of 1's, therefore a(4)=6.
G.f. A(x) = x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 10*x^6 + 19*x^7 + 34*x^8 + ... such that A(x)^2 * (1 - 2*x) = A(x^2).
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..700

Crossrefs

Cf. A000048, A271929.

Programs

PARI

/* G.f. A(x) satisfies: A(x)^2 = A(x^2)/(1 - 2*x) */
{a(n) = my(A=x); for(i=1,n, A = sqrt( subst(A,x, x^2)/(1 - 2*x +x*O(x^n)))); polcoeff(A,n)}
for(n=1,50, print1(a(n),", ")) \\ Paul D. Hanna, Apr 17 2016

PARI

/* As the EULER transform of A000048 */
{A000048(n) = sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n)} \\ Michael B. Porter
{a(n) = polcoeff( prod(k=1,n, 1/(1 - x^k +x*O(x^n))^A000048(k)), n-1)}
for(n=1,50, print1(a(n),", ")) \\ Paul D. Hanna, Apr 17 2016

Formula

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

G.f. A(x) satisfies: A(x)^2 = A(x^2) / (1 - 2*x). - Paul D. Hanna, Apr 17 2016

a(n) ~ c * 2^n / sqrt(n), where c = 0.3412831644583761326654... . - Vaclav Kotesovec, Apr 18 2016

G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = v^2 * (v^2 - 2*u^2*v - u^4) + 2*w*u^4. - Michael Somos, Jun 27 2017