login
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.
5
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
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
Sequence in context: A227309 A368279 A374631 * A000693 A054178 A005833
KEYWORD
nonn
AUTHOR
Mike Zabrocki, Oct 28 2006
STATUS
approved