login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 32

%I #93 Oct 21 2021 10:46:19

%S 1,1,1,3,8,25,75,245,800,2700,9225,32065,112632,400023,1432613,

%T 5170575,18783360,68635477,252085716,930138521,3446158600,12815663595,

%U 47820414961,178987624513,671825020128,2528212128750,9536894664375,36054433807398,136583760011496

%N 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 Also number of asymmetric rooted plane trees with n+1 nodes. - _Christian G. Bower_

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

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

%C 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 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 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 336 (4.4.64)

%H Alois P. Heinz, <a href="/A022553/b022553.txt">Table of n, a(n) for n = 0..1000</a>

%H M. J. H. Al-Kaabi, <a href="https://doi.org/10.1088/1757-899X/871/1/012048">Title</a>, IOP Conf. Ser.: Mater. Sci. Eng. (2020) Vol. 871, 012048.

%H D. 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 G. Labelle, P. 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 H. Munthe-Kaas and A. 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 J.-C. Novelli and J.-Y. 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 Y. Puri and T. 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 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Lu#Lyndon">Index entries for sequences related to Lyndon words</a>

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

%F 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 a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Sep 11 2014

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

%p with(numtheory):

%p a:= n-> `if`(n=0, 1,

%p add(mobius(n/d)*binomial(2*d, d), d=divisors(n))/(2*n)):

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 21 2011

%t 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 (PARI) a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)

%o (Python)

%o from sympy import mobius, binomial, divisors

%o def a(n):

%o return 1 if n == 0 else sum(mobius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)

%o print([a(n) for n in range(31)]) # _Indranil Ghosh_, Aug 05 2017

%o (Sage)

%o def a(n):

%o return 1 if n ==0 else sum(moebius(n//d)*binomial(2*d, d) for d in divisors(n))//(2*n)

%o # _F. Chapoton_, Apr 23 2020

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

%Y A diagonal of the square array described in A051168.

%K nonn

%O 0,4

%A _David Broadhurst_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)