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
Examples
a(3)=3 counts 6-periodic 000111, 001011 and 001101. a(4)=8 counts 00001111, 00010111, 00011011, 00011101, 00100111, 00101011, 00101101, and 00110101. - _R. J. Mathar_, Oct 20 2021
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, Monomial Bases for Free Post-Lie Algebras, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.
- Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See pp. 3, 6.
- David 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.
- Gilbert Labelle and Pierre Leroux, Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Disc. Math. 157 (1996) 227-240, Eq. (1.20).
- Hans Munthe-Kaas and Alexander 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
- Jean-Christophe Novelli and Jean-Yves Thibon, Hopf algebras and dendriform structures arising from parking functions, arXiv:math/0511200 [math.CO], 2005.
- Tilman Piesk, List of 2n-bead balanced binary Lyndon words for n=1...8
- Yash Puri and Thomas 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
Crossrefs
Programs
-
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 *) -
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
Formula
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
Comments