A123916 - OEIS

%I #21 Aug 16 2022 16:06:29

%S 1,1,2,3,6,10,19,34,65,120,229,432,829,1583,3051,5874,11370,22012,

%T 42756,83113,161917,315723,616588,1205232,2358604,4619485,9055960,

%U 17766086,34880215,68524486,134707150,264960828,521449025

%N 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.

%H Vaclav Kotesovec, <a href="/A123916/b123916.txt">Table of n, a(n) for n = 1..700</a>

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

%F G.f. A(x) satisfies: A(x)^2 = A(x^2) / (1 - 2*x). - _Paul D. Hanna_, Apr 17 2016

%F a(n) ~ c * 2^n / sqrt(n), where c = 0.3412831644583761326654... . - _Vaclav Kotesovec_, Apr 18 2016

%F 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

%e 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.

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

%o (PARI) /* G.f. A(x) satisfies: A(x)^2 = A(x^2)/(1 - 2*x) */

%o {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)}

%o for(n=1,50, print1(a(n),", ")) \\ _Paul D. Hanna_, Apr 17 2016

%o (PARI) /* As the EULER transform of A000048 */

%o {A000048(n) = sumdiv(n, d, (d%2)*(moebius(d)*2^(n/d)))/(2*n)} \\ _Michael B. Porter_

%o {a(n) = polcoeff( prod(k=1,n, 1/(1 - x^k +x*O(x^n))^A000048(k)), n-1)}

%o for(n=1,50, print1(a(n),", ")) \\ _Paul D. Hanna_, Apr 17 2016

%Y Cf. A000048, A271929.

%K nonn

%O 1,3

%A _Mike Zabrocki_, Oct 28 2006