A005354 -id:A005354 - 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.

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

David Broadhurst

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

			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

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

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

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.

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

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 *)

a(n)=if(n<1,n==0,sumdiv(n,d,moebius(n/d)*binomial(2*d,d))/2/n)

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

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

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

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146, 46509358, 164107650, 582538732, 2079165208, 7457847082, 26873059986, 97239032056, 353218528324, 1287658723550, 4709785569184

Offset: 0

N. J. A. Sloane

Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - Antti Karttunen, Sep 03 2000
Equivalently, the number of noncrossing partitions up to rotation composed of n-1 blocks of size 2. - Andrew Howroyd, May 04 2018
a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - Valery A. Liskovets, Oct 19 2005
Labeled plane trees are counted by A006963. - David Callan, Aug 19 2014
This sequence is similar to A000055 but those trees are not embedded in a plane. - Michael Somos, Aug 19 2014

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 14*x^7 + 34*x^8 + 95*x^9 + ...
a(7) = 14 = 11 + 3 because there are 11 trees with 7 nodes but three of them can be embedded in a plane in two ways. These three trees have degree sequences 4221111, 3321111, 3222111, where there are two trees with each degree sequence but in the first, the two nodes of degree two are adjacent, in the second, the two nodes of degree three are adjacent, and in the third, the node of degree three is adjacent to two nodes of degree two. - _Michael Somos_, Aug 19 2014

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 304.
A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.26).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=0..200
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
CombOS - Combinatorial Object Server, Generate free plane trees
R. Cori and M. Marcus, Counting non-isomorphic chord diagrams, Theor. Comp. Sci. 204 (1998) 55-75, Corollary 5.2.
Paul Drube and Puttipong Pongtanapaisan, Annular Non-Crossing Matchings, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
A. Errera, Reviews of two articles on Analysis Situs, from Fortschritte [Annotated scanned copy]
D. Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
Bernold Fiedler, Scalar polynomial vector fields in real and complex time, arXiv:2410.05043 [math.DS], 2024. See pp. 21, 50.
Bernold Fiedler, Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere, arXiv:2504.20503 [math.DS], 2025. See p. 23.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335.
F. Harary and R. W. Robinson, The number of achiral trees, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
G. Labelle, Sur la symétrie et l'asymétrie des structures combinatoires, Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Torsten Mütze, Proof of the middle levels conjecture, arXiv preprint arXiv:1404.4442 [math.CO], 2014.
Torsten Mütze, A book proof of the middle levels theorem, arXiv:2306.13019 [math.CO], 2023.
Torsten Mütze and Franziska Weber, Construction of 2-factors in the middle layer of the discrete cube, arXiv preprint arXiv:1111.2413 [math.CO], 2011.
Torsten Mütze and F. Weber, Construction of 2-factors in the middle layer of the discrete cube, Journal of Combinatorial Theory, Series A, 119(8) (2012), 1832-1855.
J. Sawada, Generating rooted and free plane trees, ACM Transactions on Algorithms, Vol. 2 No. 1 (2006), 1-13.
Seunghyun Seo and Heesung Shin, Two involutions on vertices of ordered trees, FPSAC'02 (2002). (see p_n).
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233. See Table 1.
D. W. Walkup, The number of plane trees, Mathematika, vol. 19, No. 2 (1972), 200-204.
Index entries for sequences related to trees

Column k=2 of A303694 and A303864.

Cf. A000055, A000108, A002996, A003239, A005354, A057502, A061417, A064640.

with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : # Zerinvary Lajos, Dec 01 2006

a[0] = a[1] = 1; a[n_] := (1/(2*(n-1)))*Sum[ EulerPhi[(n-1)/d]*Binomial[2*d, d], {d, Divisors[n-1]}] - CatalanNumber[n-1]/2 + If[ EvenQ[n], CatalanNumber[n/2-1]/2, 0]; Table[ a[n], {n, 0, 29}] (* Jean-François Alcover, Mar 07 2012, from formula *)

catalan(n) = binomial(2*n, n)/(n+1);
a(n) = if (n<2, 1, n--; sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/(2*n) - catalan(n)/2 + if ((n-1) % 2, 0, catalan((n-1)/2)/2)); \\ Michel Marcus, Jan 23 2016

G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).

a(n) = 1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*binomial(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.

More terms, formula from Christian G. Bower, Dec 15 1999

Name corrected ("labeled" --> "unlabeled") by David Callan, Aug 19 2014

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A175955 Number of ways to connect with nonintersecting chords n unlabeled points equally spaced on a circle such that the resulting configuration is not invariant w.r.t. rotation any angle < 2*Pi.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula