A171871 -id:A171871 - 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

A039754 Irregular triangle read by rows: T(n,k) = number of binary codes of length n with k words (n >= 0, 0 <= k <= 2^n); also number of 0/1-polytopes with vertices from the unit n-cube; also number of inequivalent Boolean functions of n variables with exactly k nonzero values under action of Jevons group.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 3, 6, 3, 3, 1, 1, 1, 1, 4, 6, 19, 27, 50, 56, 74, 56, 50, 27, 19, 6, 4, 1, 1, 1, 1, 5, 10, 47, 131, 472, 1326, 3779, 9013, 19963, 38073, 65664, 98804, 133576, 158658, 169112, 158658, 133576, 98804, 65664, 38073, 19963, 9013, 3779, 1326, 472, 131, 47, 10, 5, 1, 1

Offset: 0

N. J. A. Sloane

For N=1 through N=5, the first 2^(N-1) terms of row N are also found in triangle A171871, which is related to A005646. This was shown for all N by Andrew Weimholt, Dec 30 2009. [Robert Munafo, Jan 25 2010]

			Triangle begins:
  k  0  1  2  3   4   5   6   7   8   9  10  11  12 13 14 15 16   sums
n
0    1  1                                                            2
1    1  1  1                                                         3
2    1  1  2  1   1                                                  6
3    1  1  3  3   6   3   3   1   1                                 22
4    1  1  4  6  19  27  50  56  74  56  50  27  19  6  4  1  1    402

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 112.
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 150.

Jan Brandts, A. Cihangir, Enumeration and investigation of acute 0/1-simplices modulo the action of the hyperoctahedral group, arXiv preprint arXiv:1512.03044 [math.CO], 2015. See Fig. 13.
D. Condon, S. Coskey, L. Serafin, and C. Stockdale, On generalizations of separating and splitting families, arXiv preprint arXiv:1412.4683 [math.CO], 2014-2015.
Jacob Feldman, A catalog of Boolean concepts, Journal of Mathematical Psychology, Volume 47, Issue 1, 2003, 75-89.
Harald Fripertinger, Enumeration, construction and random generation of block codes, Designs, Codes, Crypt., 14 (1998), 213-219.
Harald Fripertinger, Isometry Classes of Codes
Harald Fripertinger, Enumeration of block codes
Tilman Piesk, Illustration of row 3
Index entries for sequences related to Boolean functions

Row sums give A000616. Cf. A052265.
Rows give A034188, A034189, A034190, etc.
Columns are A034198, A034199, A034200, etc.
Diagonal is A276412.
For other versions of this triangle see A171876, A039754, A276777.
Cf. A171871.

P = IntegerPartitions;
AC[d_Integer] := Module[{C, M, p},(* from W. Y. C. Chen algorithm *) M[p_List] := Plus @@ p!/(Times @@ p * Times @@ (Length /@ Split[p]!)); C[p_List, q_List] := Module[{r, m, k, x}, r = If[0 == Length[q], 1, 2*2^IntegerExponent[LCM @@ q, 2]]; m = LCM @@ Join[p/GCD[r, p], q/GCD[r, q]]; CoefficientList[Expand[Product[(1 + x^(k *r))^((Plus @@ Map[MoebiusMu[k/#]*2^Plus @@ GCD[#*r, Join[p, q]]&, Divisors[k]])/(k*r)), {k, 1, m}]], x]]; Sum[Binomial[d, p]*Plus @@ Plus @@ Outer[M[#1] M[#2] C[#1, #2]*2^(d - Length[#1] - Length[#2]) &, P[p], P[d - p], 1], {p, 0, d}]/(d! 2^d)]; AC[0]  = {1, 1};
AC /@ Range[0, 5] // Flatten (* Jean-François Alcover, Dec 15 2019, after Robert A. Russell in A034189 *)
Table[ CoefficientList[ CycleIndexPolynomial[ GraphData[ {"Hypercube", n}, "AutomorphismGroup"], Array[Subscript[x, ##] &, 2^n]] /. Table[ Subscript[x, i] -> 1 + x^i, {i, 1, 2^n}], x], {n, 1,8}] // Grid (* Geoffrey Critzer, Jan 10 2020 *)

Reference gives g.f.

Fripertinger gives g.f. for the number of classes of (n, m) nonlinear codes over an alphabet of size A.

Corrected and extended by Vladeta Jovovic, Apr 20 2000
Entry revised by N. J. A. Sloane, Sep 19 2016
T(0, 1) = 1 inserted. (There are two 0-ary functions.) - Tilman Piesk, Jan 10 2023

cp's OEIS Frontend

A171873 Column sums of triangle A171871.

Views

Author

Keywords

Comments

Links

A171875 Subdiagonal of triangle A171871: Classifications of N elements containing exactly N-2 binary partitions.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A005646 Number of classifications of n elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A171872 Triangle read by columns: Distinct classifications of N elements containing exactly R binary partitions.

Views

Author

Keywords

Comments

Links

Crossrefs

A171876 Mutual solutions to two classification counting problems: binary block codes of wordlength J with N used words; and classifications of N elements by J partitions.

Views

Author

Keywords

Comments

Links

Crossrefs