A335362 -id:A335362 - cp's OEIS frontend

A000055 Number of trees with n unlabeled nodes.

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410221, 300628862480, 823779631721, 2262366343746, 6226306037178

Offset: 0

N. J. A. Sloane

Also, number of unlabeled 2-gonal 2-trees with n-1 2-gons, for n>0. [Corrected by Andrei Zabolotskii, Jul 29 2025]
Main diagonal of A054924.
Left border of A157905. - Gary W. Adamson, Mar 08 2009
From Robert Munafo, Jan 24 2010: (Start)
Also counts classifications of n items that require exactly n-1 binary partitions; see Munafo link at A005646, also A171871 and A171872.
The 11 trees for n = 7 are illustrated at the Munafo web link.
Link to A171871/A171872 conjectured by Robert Munafo, then proved by Andrew Weimholt and Franklin T. Adams-Watters on Dec 29 2009. (End)
This is also "Number of tree perfect graphs on n nodes" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015
For n > 0, a(n) is the number of ways to arrange n-1 unlabeled non-intersecting circles on a sphere. - Vladimir Reshetnikov, Aug 25 2016
All trees for n=1 through n=12 are depicted in Chapter 1 of the Steinbach reference. On p. 6 appear encircled two trees (with n=10) which seem inequivalent only when considered as ordered (planar) trees. Earlier instances of such possibly (in)equivalent trees could appear from n=6 on (and from n=9 on without equivalence modulo plane symmetry) but are not drawn separately there. - M. F. Hasler, Aug 29 2017

			a(1) = 1 [o]; a(2) = 1 [o-o]; a(3) = 1 [o-o-o];
a(4) = 2 [o-o-o and o-o-o-o]
            |
            o
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 55.
N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 49.
A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 459).
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 58 and 244.
D. E. Knuth, Fundamental Algorithms, 3d Ed. 1997, pp. 386-88.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar and Robert G. Wilson v, Table of n, a(n) for n = 0..1000
Jeremy C. Adcock, Sam Morley-Short, Joshua W. Silverstone, and Mark G. Thompson, Hard limits on the postselectability of optical graph states, arXiv:1806.03263 [quant-ph], 2018.
H. R. Afshar, E. A. Bergshoeff, and W. Merbis, Interacting spin-2 fields in three dimensions, arXiv preprint arXiv:1410.6164 [hep-th], 2014-2015.
Ruggero Bandiera and Florian Schaetz, Eulerian idempotent, pre-Lie logarithm and combinatorics of trees, arXiv:1702.08907 [math.CO], 2017. Mentions this sequence.
Madeleine Burkhart and Joel Foisy, Enumerating spherical n-links, Involve, Vol. 11 (2018), No. 2, 195-206.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
A. Cayley, On the analytical forms called trees, Amer. J. Math., 4 (1881), 266-268.
CombOS - Combinatorial Object Server, Generate graphs
Benjamin Côté, Hélène Cossette, and Etienne Marceau, Centrality and topology properties in a tree-structured Markov random field, arXiv:2410.20240 [math.ST], 2024. See p. 18.
Antoine Dailly and Tuomo Lehtilä, Reconstructing graphs with subgraph compositions, arXiv:2504.00169 [math.CO], 2025. See p. 28.
R. Ferrer-i-Cancho, Non-crossing dependencies: least effort, not grammar, arXiv preprint arXiv:1411.2645 [cs.CL], 2014.
S. R. Finch, Otter's Tree Enumeration Constants
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 481.
Andrew Gainer-Dewar, Gamma-Species and the Enumeration of k-Trees, Electronic Journal of Combinatorics, Volume 19 (2012), #P45 and arXiv:1208.5993 [math.CO], 2012.
Xiangrui Gao, Song He, and Yong Zhang, Labelled tree graphs, Feynman diagrams and disk integrals arxiv:1708.08701 [hep-th], 2017, see p. 4.
Ira M. Gessel, Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees, arXiv:2305.03157 [math.CO], 2023.
D. D. Grant, The stability index of graphs, pp. 29-52 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974. Gives first 45 terms.
Paul E. Gunnells, Generalized Catalan numbers from hypergraphs, arXiv:2102.05121 [math.CO], 2021. Mentions this sequence p. 3.
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
House of Graphs, Trees
Andrew Jobbings, Enumerating nets, Preprint 2015.
Mithra Karamchedu and Lucas Bang, Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism, arXiv:2508.13480 [cs.DS], 2025. See p. 4.
Elena V. Konstantinova and Maxim V. Vidyuk, Discriminating tests of information and topological indices. Animals and trees, J. Chem. Inf. Comput. Sci. 43 (2003), 1860-1871. See Table 15, column 1 on page 1868.
G. Labelle, C. Lamathe and P. Leroux, Labeled and unlabeled enumeration of k-gonal 2-trees, arXiv:math/0312424 [math.CO], 2003.
Steve Lawford and Yll Mehmeti, Cliques and a new measure of clustering: with application to U.S. domestic airlines, arXiv:1806.05866 [cs.SI], 2018.
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)
Gang Li, Generation of Rooted Trees and Free Trees, Comp. Sci. MSc thesis paper, 1996.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Robert Munafo, Relation to Tree Graphs
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
Sebastian Piec, Krzysztof Malarz and Krzysztof Kulakowski. How to count trees?, arXiv:cond-mat/0501594 [cond-mat.stat-mech], 2005; Int. J. Modern Phys., C16 (2005) 1527-1534.
N. Pippenger, Enumeration of equicolorable trees, SIAM J. Discrete Math., 14 (2001), 93-115.
J. M. Plotkin and J. W. Rosenthal, How to obtain an asymptotic expansion of a sequence from an analytic identity satisfied by its generating function, J. Austral. Math. Soc. (Series A), Vol. 56 (1994), 131-143.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. W. Robinson, Letter to N. J. A. Sloane, Jul 29 1980
Yaniv Sadeh, Haim Kaplan, and Uri Zwick, Search Trees on Trees via LP, arXiv:2501.17563 [cs.DS], 2025. See p. 12.
Sage, Common Graphs
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Overview of the following parts: Cover, Front matter, Chapter 1: Trees, Trees (cont'd: pt.2), Trees (cont'd: pt.3), Chapter 2: Centers and Centroids, Chap.2 (cont'd), Chapter 3: Random Trees, Chapter 4: Rooted Trees, Chapter 5: Homeomorphically Irreducible Trees, Chapter 6: Tables (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Ivan Stošić and Ivan Damnjanović, An efficient algorithm for generating transmission irregular trees, arXiv:2502.15453 [cs.DM], 2025. See p. 11.
Tanay Wakhare, Eric Wityk, and Charles R. Johnson. The proportion of trees that are linear, Discrete Mathematics 343.10 (2020): 112008. Also arXiv:1901.08502 [math.CO], 2019-2020. See Tables 1 and 2 (but beware errors).
Eric Weisstein's World of Mathematics, Tree
Pascal Welke, Tamás Horváth, and Stefan Wrobel, Probabilistic and exact frequent subtree mining in graphs beyond forests, Machine Learning (2019), 1-28.
Robert Alan Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay, Constant Time Generation of Free Trees, SIAM Journal of Computing, vol. 15, no. 2, pp. 540-548, (1986) [preprint].
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000676 (centered trees), A000677 (bicentered trees), A027416 (trees with a centroid), A102011 (trees with a bicentroid), A034853 (refined by diameter), A238414 (refined by maximum vertex degree).
Cf. A000081 (rooted trees), A000272 (labeled trees), A000169 (labeled rooted trees), A212809 (radius of convergence).
Cf. A036361 (labeled 2-trees), A036362 (labeled 3-trees), A036506 (labeled 4-trees), A054581 (unlabeled 2-trees).
Cf. A157904, A157905, A005195 (Euler transform = forests), A095133 (multisets).
Column 0 of A335362 and A034799.
Related to A005646; see A171871 and A171872.
Cf. also A000088, A008406, A051491, A086308.

import Data.List (generic_index)
import Math.OEIS (getSequenceByID)
triangle x = (x * x + x) `div` 2
a000055 n = let {r = genericIndex (fromJust (getSequenceByID "A000081")); (m, nEO) = divMod n 2}
            in  r n - sum (zipWith (*) (map r [0..m]) (map r [n, n-1..]))
                + (1-nEO) * (triangle (r m + 1))
-- Walt Rorie-Baety, Jun 12 2021

N := 30; P := PowerSeriesRing(Rationals(),N+1); f := func< A | x*&*[Exp(Evaluate(A,x^k)/k) : k in [1..N]]>; G := x; for i in [1..N] do G := f(G); end for; G000081 := G; G000055 := 1 + G - G^2/2 + Evaluate(G,x^2)/2; A000055 := Eltseq(G000055); // Geoff Baileu (geoff(AT)maths.usyd.edu.au), Nov 30 2009

G000055 := series(1+G000081-G000081^2/2+subs(x=x^2,G000081)/2,x,31); A000055 := n->coeff(G000055,x,n); # where G000081 is g.f. for A000081 starting with n=1 term
with(numtheory): b:= proc(n) option remember; `if`(n<=1, n, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= n-> `if`(n=0, 1, b(n) -(add(b(k) *b(n-k), k=0..n) -`if`(irem(n, 2)=0, b(n/2), 0))/2):
seq(a(n), n=0..50);
# Alois P. Heinz, Aug 21 2008
# Program to create b-file b000055.txt:
A000081 := proc(n) option remember; local d, j;
if n <= 1 then n else
    add(add(d*procname(d),d=numtheory[divisors](j))*procname(n-j),j=1..n-1)/(n-1);
fi end:
A000055 := proc(nmax) local a81, n, t, a, j, i ;
a81 := [seq(A000081(i), i=0..nmax)] ; a := [] ;
for n from 0 to nmax do
    if n = 0 then
        t := 1+op(n+1, a81) ;
    else
        t := op(n+1, a81) ;
    fi;
    if type(n, even) then
        t := t-op(1+n/2, a81)^2/2 ;
        t := t+op(1+n/2, a81)/2 ;
    fi;
    for j from 0 to (n-1)/2 do
        t := t-op(j+1, a81)*op(n-j+1, a81) ;
    od:
    a := [op(a), t] ;
od:
a end:
L := A000055(1000) ;
#  R. J. Mathar, Mar 06 2009

s[n_, k_] := s[n, k] = a[n + 1 - k] + If[n < 2k, 0, s[n - k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[i] s[n-1, i] i, {i, 1, n-1}] / (n-1); Table[a[i] - Sum[a[j] a[i-j], {j, 1, i/2}] + If[OddQ[i], 0, a[i/2] (a[i/2] + 1)/2], {i, 1, 50}] (* Robert A. Russell *)
b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[d*b[d]*b[n-j], {j, 1, n-1}, {d, Divisors[j]}]/(n-1); a[0] = 1; a[n_] := b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *)

{a(n) = local(A, A1, an, i, t); if( n<2, n>=0, an = Vec(A = A1 = 1 + O('x^n)); for(m=2, n, i=m\2; an[m] = sum(k=1, i, an[k] * an[m-k]) + (t = polcoeff( if( m%2, A *= (A1 - 'x^i)^-an[i], A), m-1))); t + if( n%2==0, binomial( -polcoeff(A, i-1), 2)))}; /* Michael Somos */

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
Vec( 1 + H(x) - 1/2*( H(x)^2 - H(x^2) ) )
\\ Joerg Arndt, Jul 10 2014

# uses function from A000081
def A000055(n): return 1 if n == 0 else A000081(n)-sum(A000081(i)*A000081(n-i) for i in range(1,n//2+1)) + (0 if n % 2 else (A000081(n//2)+1)*A000081(n//2)//2) # Chai Wah Wu, Feb 03 2022

[len(list(graphs.trees(n))) for n in range(16)] # Peter Luschny, Mar 01 2020

G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.
a(n) ~ A086308 * A051491^n * n^(-5/2). - Vaclav Kotesovec, Jan 04 2013
a(n) = A000081(n) - A217420(n+1), n > 0. - R. J. Mathar, Sep 19 2016
a(n) = A000676(n) + A000677(n). - R. J. Mathar, Aug 13 2018
a(n) = A000081(n) - (Sum_{1<=i<=j, i+j=n} A000081(i)*A000081(j)) + (1-(-1)^(n-1)) * binomial(A000081(n/2)+1,2) / 2 [Li, equation 4.2]. - Walt Rorie-Baety, Jul 05 2021

A000238 Number of oriented trees with n nodes.

Original entry on oeis.org

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, 2266502, 10598452, 50235931, 240872654, 1166732814, 5702001435, 28088787314, 139354922608, 695808554300, 3494390057212, 17641695461662, 89495023510876, 456009893224285, 2332997330210440

Offset: 1

N. J. A. Sloane

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 286.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 60, r(x).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 350 terms from N. J. A. Sloane)
H. R. Afshar, E. A. Bergshoeff, W. Merbis, Interacting spin-2 fields in three dimensions, arXiv preprint arXiv:1410.6164 [hep-th], 2014-2015, JHEP 2015 (2015) # 040.
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), TOC
R. J. Mathar, Oriented trees A000238
R. Simion, Trees with 1-factors and oriented trees, Discrete Math., 88 (1991), 93-104.
Index entries for sequences related to trees

Cf. A000060, A000151, A051437 (linear oriented), A334827 (oriented star-like).

Diagonal of A335362.

A:= proc(n) option remember; if n=0 then 0 else unapply(convert(series(x*exp(2* add(A(n-1)(x^k)/k, k=1..n-1)), x=0,n), polynom), x) fi end: a:= n-> coeff(series(A(n+1)(x) *(1-A(n+1)(x)), x=0, n+1), x,n): seq(a(n), n=1..26); # Alois P. Heinz, Aug 20 2008

A[n_][y_] := A[n][y] = If[n == 0, 0, Normal[Series[x*Exp[2*Sum[A[n-1][x^k]/k, {k, 1, n-1}]], {x, 0, n}] /. x -> y]]; a[n_] := SeriesCoefficient[A[n+1][x]*(1-A[n+1][x]), {x, 0, n}]; Table[a[n], {n, 1, 26}] (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

seq(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 2/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); Vec(Ser(A)-x*Ser(A)^2)} \\ Andrew Howroyd, May 13 2018

G.f. = x+x^2+3*x^3+8*x^4+27*x^5+... = R(x)-R(x)^2, where R(x) = g.f. for A000151.

a(n) ~ c * d^n / n^(5/2), where d = A245870 = 5.64654261623294971289271351621..., c = 0.22571615379282714232305... . - Vaclav Kotesovec, Dec 08 2014

2 errors corrected by Paul Zimmermann, Mar 01 1996

More terms from N. J. A. Sloane, Mar 10 2007

A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

Original entry on oeis.org

1, 2, 5, 12, 30, 74, 188, 478, 1235, 3214, 8450, 22370, 59676, 160140, 432237, 1172436, 3194870, 8741442, 24007045, 66154654, 182864692, 506909562, 1408854940, 3925075510, 10959698606, 30665337738, 85967279447, 241433975446, 679192039401, 1913681367936, 5399924120339

Offset: 2

N. J. A. Sloane

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 2..1000 (terms n = 2..200 from T. D. Noe)
Vsevolod Gubarev, Rota-Baxter operators on a sum of fields, arXiv:1811.08219 [math.RA], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 385
Index entries for sequences related to rooted trees

Column d=1 of A335362.
Column 2 of A339067.
Cf. A000081, A000242, A000300, A000343, A000395, A027852 (forests of 2 rooted trees).

a000106 n = a000106_list !! (n-2)
a000106_list = drop 2 $ conv a000081_list [] where
   conv (v:vs) ws = (sum $ zipWith (*) ws' $ reverse ws') : conv vs ws'
                    where ws' = v : ws
-- Reinhard Zumkeller, Jun 17 2013

b:= proc(n) option remember; if n<=1 then n else add(k*b(k)* s(n-1, k), k=1..n-1)/(n-1) fi end: s:= proc(n,k) option remember; add(b(n+1-j*k), j=1..iquo(n,k)) end: B:= proc(n) option remember; add(b(k)*x^k, k=1..n) end: a:= n-> coeff(series(B(n-1)^2, x=0, n+1), x,n): seq(a(n), n=2..35); # Alois P. Heinz, Aug 21 2008

<Jean-François Alcover, Nov 02 2011 *)
b[n_] := b[n] = If[n <= 1, n, Sum[k*b[k]*s[n-1, k], {k, 1, n-1}]/(n-1)]; s[n_, k_] := s[n, k] = Sum[b[n+1-j*k], {j, 1, Quotient[n, k]}]; B[n_] := B[n] = Sum[b[k]*x^k, {k, 1, n}]; a[n_] := SeriesCoefficient[B[n-1]^2, {x, 0, n}]; Table[a[n], {n, 2, 35}] (* Jean-François Alcover, Dec 01 2016, after Alois P. Heinz *)

Self-convolution of rooted trees A000081.
a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.87984802514205060808180678... . - Vaclav Kotesovec, Sep 11 2014
In the asymptotics above the constant c = 2 * A187770. - Vladimir Reshetnikov, Aug 13 2016

More terms from Christian G. Bower, Nov 15 1999

cp's OEIS Frontend

A000055 Number of trees with n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A000238 Number of oriented trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A000106 2nd power of rooted tree enumerator; number of linear forests of 2 rooted trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A006965 Number of directed trees with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A335601 The number of mixed trees with n nodes and n-2 arcs.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula