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,3

Links

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

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

Example

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

Prog

(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

Crossrefs

Cf. A000048, A271929.

Sequence in context: A291875 A227309 A368279 * A000693 A054178 A005833

Adjacent sequences: A123913 A123914 A123915 * A123917 A123918 A123919

Keyword

nonn

Author

Mike Zabrocki, Oct 28 2006

Status

approved