cp's OEIS Frontend

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.

%I A022553 #111 Aug 29 2025 20:53:59
%S A022553 1,1,1,3,8,25,75,245,800,2700,9225,32065,112632,400023,1432613,
%T A022553 5170575,18783360,68635477,252085716,930138521,3446158600,12815663595,
%U A022553 47820414961,178987624513,671825020128,2528212128750,9536894664375,36054433807398,136583760011496
%N 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.
%C A022553 Also number of asymmetric rooted plane trees with n+1 nodes. - _Christian G. Bower_
%C A022553 Conjecturally, number of irreducible alternating Euler sums of depth n and weight 3n.
%C A022553 a(n+1) is inverse Euler transform of A000108. Inverse Witt transform of A006177.
%C A022553 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
%C A022553 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
%D A022553 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)
%H A022553 Alois P. Heinz, <a href="/A022553/b022553.txt">Table of n, a(n) for n = 0..1000</a>
%H A022553 M. J. H. Al-Kaabi, <a href="https://doi.org/10.1088/1757-899X/871/1/012048">Monomial Bases for Free Post-Lie Algebras</a>, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.
%H A022553 Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, <a href="https://arxiv.org/abs/2505.06941">When are Hopf algebras determined by integer sequences?</a>, arXiv:2505.06941 [math.CO], 2025. See pp. 3, 6.
%H A022553 David J. Broadhurst, <a href="http://arXiv.org/abs/hep-th/9604128">On the enumeration of irreducible k-fold Euler sums and their roles in knot theory and field theory</a>, arXiv:hep-th/9604128, 1996.
%H A022553 Gilbert Labelle and Pierre Leroux, <a href="https://doi.org/10.1016/S0012-365X(96)83017-2">Enumeration of (uni- or bicolored) plane trees according to their degree distribution</a>, Disc. Math. 157 (1996) 227-240, Eq. (1.20).
%H A022553 Hans Munthe-Kaas and Alexander Lundervold, <a href="https://arxiv.org/abs/1203.4738">On post-Lie algebras, Lie-Butcher series and moving frames</a>, arXiv preprint arXiv:1203.4738 [math.NA], 2012. - From _N. J. A. Sloane_, Sep 20 2012
%H A022553 Jean-Christophe Novelli and Jean-Yves Thibon, <a href="https://arxiv.org/abs/math/0511200">Hopf algebras and dendriform structures arising from parking functions</a>, arXiv:math/0511200 [math.CO], 2005.
%H A022553 Tilman Piesk, <a href="https://oeis.org/A385666/a385666_3.txt">List of 2n-bead balanced binary Lyndon words for n=1...8</a>
%H A022553 Yash Puri and Thomas Ward, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/WARD/short.html">Arithmetic and growth of periodic orbits</a>, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
%H A022553 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A022553 <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>
%F A022553 a(n) = A060165(n)/2 = A007727(n)/(2*n) = A045630(n)/n.
%F A022553 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_
%F A022553 a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Sep 11 2014
%F A022553 G.f.: 1 + Sum_{k>=1} mu(k)*log((1 - sqrt(1 - 4*x^k))/(2*x^k))/k. - _Ilya Gutkovskiy_, May 18 2019
%e A022553 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
%p A022553 with(numtheory):
%p A022553 a:= n-> `if`(n=0, 1,
%p A022553         add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):
%p A022553 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jan 21 2011
%t A022553 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 *)
%o A022553 (PARI) a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)
%o A022553 (Python)
%o A022553 from sympy import mobius, binomial, divisors
%o A022553 def a(n):
%o A022553     return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
%o A022553 print([a(n) for n in range(31)]) # _Indranil Ghosh_, Aug 05 2017
%o A022553 (Sage)
%o A022553 def a(n):
%o A022553     return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)
%o A022553 # _F. Chapoton_, Apr 23 2020
%Y A022553 Cf. A003239, A005354, A000740, A007727, A086655, A289978 (multiset trans.), A001037 (binary Lyndon wds.), A074655 (3 letters), A074656 (4 letters).
%Y A022553 A diagonal of the square array described in A051168.
%K A022553 nonn,changed
%O A022553 0,4
%A A022553 _David Broadhurst_