A022553 Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period.

1, 1, 1, 3, 8, 25, 75, 245, 800, 2700, 9225, 32065, 112632, 400023, 1432613, 5170575, 18783360, 68635477, 252085716, 930138521, 3446158600, 12815663595, 47820414961, 178987624513, 671825020128, 2528212128750, 9536894664375, 36054433807398, 136583760011496

Offset

0,4

Comments

Also number of asymmetric rooted plane trees with n+1 nodes. - Christian G. Bower

Conjecturally, number of irreducible alternating Euler sums of depth n and weight 3n.

a(n+1) is inverse Euler transform of A000108. Inverse Witt transform of A006177.

Dimension of the degree n part of the primitive Lie algebra of the Hopf algebra CQSym (Catalan Quasi-Symmetric functions). - Jean-Yves Thibon (jyt(AT)univ-mlv.fr), Oct 22 2006

For n>0, 2*a(n) is divisible by n (cf. A268619), 12*a(n) is divisible by n^2 (cf. A268592). - Max Alekseyev, Feb 09 2016

References

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)

Links

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

M. J. H. Al-Kaabi, Title, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.

D. J. Broadhurst, On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory, arXiv:hep-th/9604128, 1996.

G. Labelle, P. Leroux, Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Disc. Math. 157 (1996) 227-240, Eq. (1.20).

H. Munthe-Kaas and A. Lundervold, On post-Lie algebras, Lie-Butcher series and moving frames, arXiv preprint arXiv:1203.4738 [math.NA], 2012. - From N. J. A. Sloane, Sep 20 2012

J.-C. Novelli and J.-Y. Thibon, Hopf algebras and dendriform structures arising from parking functions, arXiv:math/0511200 [math.CO], 2005.

Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.

Index entries for sequences related to rooted trees

Index entries for sequences related to Lyndon words

Formula

a(n) = A060165(n)/2 = A007727(n)/(2*n) = A045630(n)/n.

Product_n (1-x^n)^a(n) = 2/(1+sqrt(1-4*x)); a(n) = 1/(2*n) * Sum_{d|n} mu(n/d)*C(2*d,d). Also Moebius transform of A003239. - Christian G. Bower

a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 11 2014

G.f.: 1 + Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - Ilya Gutkovskiy, May 18 2019

Example

a(3)=3 counts 6-periodic 000111, 001011 and 00110. a(4)=8 counts 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, and 00110101. - R. J. Mathar, Oct 20 2021

Maple

with(numtheory):
a:= n-> `if`(n=0, 1,
        add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):
seq(a(n), n=0..30);  # Alois P. Heinz, Jan 21 2011

Mathematica

a[n_] := Sum[MoebiusMu[n/d]*Binomial[2d, d], {d, Divisors[n]}]/(2n); a[0] = 1; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 02 2015 *)

Prog

(PARI) a(n)=if(n<1, n==0, sumdiv(n, d, moebius(n/d)*binomial(2*d, d))/2/n)
(Python)
from sympy import mobius, binomial, divisors
def a(n):
    return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 05 2017
(Sage)
def a(n):
    return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
# F. Chapoton, Apr 23 2020

Crossrefs

Cf. A003239, A005354, A000740, A007727, A086655, A289978 (multiset trans.), A001037 (binary Lyndon wds.), A074655 (3 letters), A074656 (4 letters).

A diagonal of the square array described in A051168.

Sequence in context: A006177 A148788 A292778 * A292884 A148789 A088327

Adjacent sequences: A022550 A022551 A022552 * A022554 A022555 A022556

Keyword

nonn

Author

David Broadhurst

Status

approved