A095133 -id:A095133 - cp's OEIS frontend

A005196 a(n) = Sum_t t*F(n,t), where F(n,t) (see A095133) is the number of forests with n (unlabeled) nodes and exactly t trees.

1, 3, 6, 13, 24, 49, 93, 190, 381, 803, 1703, 3755, 8401, 19338, 45275, 108229, 262604, 647083, 1613941, 4072198, 10374138, 26663390, 69056163, 180098668, 472604314, 1247159936, 3307845730, 8814122981, 23585720703, 63359160443, 170815541708, 462049250165

Offset: 1

N. J. A. Sloane

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..300
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121. [The 17th entry is wrong]
Eric Weisstein's World of Mathematics, Forest

Cf. A000055, A005195, A095133.

with(numtheory):
b:= proc(n) option remember; local d, j; `if` (n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
t:= proc(n) option remember; local k; `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)
    end:
g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j) *
       binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
    end:
a:= n-> add(k*g(n, n, k), k=1..n):
seq(a(n), n=1..40);  # Alois P. Heinz, Aug 20 2012

nn=30;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);ft=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,nn}];CoefficientList[Series[D[Product[1/(1-y x^i)^ft[[i]],{i,1,nn}],y]/.y->1,{x,0,20}],x]  (* Geoffrey Critzer, Oct 13 2012, after code given by Robert A. Russell in A000055 *)

To get a(n), take row n of the triangle in A095133, multiply successive terms by 1, 2, 3, ... and sum. E.g., a(4) = 1*2 + 2*2 + 3*1 + 4*1 = 13.

More terms from Vladeta Jovovic, Jun 03 2004

Definition clarified by N. J. A. Sloane, May 29 2012

A000055 Number of trees with n unlabeled nodes.

Original entry on oeis.org

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

A005195 Number of forests with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, 8599, 20514, 49905, 122963, 307199, 775529, 1977878, 5086638, 13184156, 34402932, 90328674, 238474986, 632775648, 1686705630, 4514955632, 12132227370, 32717113805, 88519867048, 240235675303

Offset: 0

N. J. A. Sloane

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
  {}  {}  {}    {}       {}          {}
          {12}  {12}     {12}        {12}
                {13,23}  {12,34}     {12,34}
                         {13,23}     {13,23}
                         {13,24,34}  {12,35,45}
                         {14,24,34}  {13,24,34}
                                     {14,24,34}
                                     {13,24,35,45}
                                     {14,25,35,45}
                                     {15,25,35,45}
(End)

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
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 = 0..1000 (first 201 terms from T. D. Noe)
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Forest.
Index entries for sequences related to forests

Cf. A095133 (by number of trees), A136605 (by number of edges).
A diagonal of A144215.
The connected case is A000055.
The labeled version is A001858.
The covering case is A144958, labeled A105784.
For triangles instead of cycles we have A006785, covering A372169.
Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000272, A002807, A054548, A137917, A367863, A372176.

EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
b[n_] := b[n] = If[n <= 1, n, Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}]/(n - 1)];
a55[n_] := a55[n] = If[n == 0, 1, b[n] - (Sum[ b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; A000055 = Table[ a55[n], {n, 1, 31}]; EulerTransform[ A000055 ] (* Jean-François Alcover, Mar 15 2012 *)

Euler transform of A000055: Product_{n>0} (1-x^n)^(-A000055(n)). a(n) = 1/n*Sum_{k=1..n} b(k)*a(n-k), where b(k) = Sum_{d divides k} d*A000055(d). - Vladeta Jovovic, Sep 05 2002
G.f.: exp(sum_{k>0} B(x^k)/k ), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - Vaclav Kotesovec, Nov 16 2014
First differences are A144958. - Gus Wiseman, Apr 29 2024

More terms from Vladeta Jovovic, Sep 05 2002

A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 2, 4, 6, 6, 1, 1, 2, 4, 7, 11, 11, 1, 1, 2, 4, 8, 14, 23, 23, 1, 1, 2, 4, 8, 15, 29, 46, 47, 1, 1, 2, 4, 8, 16, 32, 60, 99, 106, 1, 1, 2, 4, 8, 16, 33, 66, 128, 216, 235, 1, 1, 2, 4, 8, 16, 34, 69, 143, 284, 488, 551, 1, 1, 2, 4, 8, 16, 34, 70, 149, 315, 636, 1121, 1301

Offset: 1

N. J. A. Sloane, May 09 2008

			Triangle begins:
1
1,1
1,1,1
1,1,2,2
1,1,2,3,3
1,1,2,4,6,6 <- T(6,3) = 4 forests on 6 nodes with 3 edges.
1,1,2,4,7,11,11
1,1,2,4,8,14,23,23
1,1,2,4,8,15,29,46,47
1,1,2,4,8,16,32,60,99,106
1,1,2,4,8,16,33,66,128,216,235
1,1,2,4,8,16,34,69,143,284,488,551
1,1,2,4,8,16,34,70,149,315,636,1121,1301
1,1,2,4,8,16,34,71,152,330,710,1467,2644,3159

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.

Alois P. Heinz, Rows n = 1..141, flattened

Row sums give A005195. Rightmost diagonal gives A000055. Cf. A001858, A138464.

Rows converge to A215930. Reflected table is A095133. - Alois P. Heinz, Apr 11 2014

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:
t:= 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):
g:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, expand(add(binomial(t(i)+j-1, j)*
       g(n-i*j, i-1)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(g(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Apr 11 2014

b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}])/(n-1)]; t[n_] := If[n == 0, 1, b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0, Expand[Sum[Binomial[t[i] + j - 1, j]*g[n - i*j, i-1]*x^j, {j, 0, n/i}]]]]; T[n_] := CoefficientList[g[n, n], x] // Reverse // Most; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Apr 16 2014, after Alois P. Heinz *)

G.f.: Product_{k>=1} 1/(1 - y^(k-1)*x^k)^A000055(k). - Geoffrey Critzer, Nov 10 2014

A274937 Number of unlabeled forests on n nodes that have exactly two nonempty components.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 6, 11, 23, 46, 99, 216, 488, 1121, 2644, 6334, 15437, 38132, 95368, 241029, 614968, 1582030, 4100157, 10697038, 28075303, 74086468, 196470902, 523383136, 1400051585, 3759508536, 10131097618, 27391132238, 74283552343, 202030012554, 550934060120, 1506161266348

Offset: 0

N. J. A. Sloane, Jul 19 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000055, A274935, A274936, A274938. [A274935, A274936, A274937, A274938] are analogs for forests of [A275165, A275166, A216785, A274934] for graphs.

b:= proc(n) option remember; `if`(n<2, n, (add(add(d*
      b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
g:= proc(n) option remember; `if`(n=0, 1, b(n)-add(b(j)*
      b(n-j), j=0..n/2)+`if`(n::odd, 0, (t->t*(t+1)/2)(b(n/2))))
    end:
a:= proc(n) option remember; add(g(j)*g(n-j), j=1..n/2)-
      `if`(n::odd, 0, (t-> t*(t-1)/2)(g(n/2)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 20 2016

b[n_] := b[n] = If[n<2, n, Sum[DivisorSum[j, #*b[#]&]*b[n-j], {j, 1, n-1}]/ (n-1)];
g[n_] := g[n] = If[n==0, 1, b[n]-Sum[b[j]*b[n-j], {j, 0, n/2}] + If[OddQ[n], 0, Function[t, t*(t+1)/2][b[n/2]]]];
a[n_] := a[n] = Sum[g[j]*g[n-j], {j, 1, n/2}] - If[OddQ[n], 0, Function[t, t*(t-1)/2][g[n/2]]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 14 2017, after Alois P. Heinz *)

G.f.: [A(x)^2 + A(x^2)]/2 where A(x) is the o.g.f. for A000055 without the initial constant 1.

a(n) = A095133(n,2). - R. J. Mathar, Jul 20 2016

A105821 Triangle of the numbers of different forests with one or more isolated vertices. Those forests have order N and m trees.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 3, 3, 2, 1, 1, 0, 6, 6, 4, 2, 1, 1, 0, 11, 11, 7, 4, 2, 1, 1, 0, 23, 23, 14, 8, 4, 2, 1, 1, 0, 47, 46, 29, 15, 8, 4, 2, 1, 1, 0, 106, 99, 60, 32, 16, 8, 4, 2, 1, 1, 0, 235, 216, 128, 66, 33, 16, 8, 4, 2, 1, 1, 0, 551, 488, 284, 143, 69, 34, 16, 8, 4, 2, 1, 1

Offset: 1

Washington Bomfim, Apr 25 2005

The unique tree with an isolated node has order one. For N > 1 and m > 1 there is at least one partition of N in m parts, with a part equal to 1, so a(n) > 0, when m > 1 and a(n) = 0, when m = 1 and N > 1. A095133(n) = A105821(n) + A105820(n).

a(2*n+1,n+1) = A215930(n) for n>=0. - Alois P. Heinz, Jul 10 2013

			a(5,2) = 2 because 5 vertices can be partitioned in two trees only in one way: one tree gets 4 nodes and the other tree gets 1. Since A000055(4) = 2 and A000055(1) = 1, there are 2 forests. The forests of order less than or equal to 5 are depicted in the Weisstein "Forest" link.
1;
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 2, 2, 1, 1;
0, 3, 3, 2, 1, 1;
0, 6, 6, 4, 2, 1, 1;
0, 11, 11, 7, 4, 2, 1, 1;
0, 23, 23, 14, 8, 4, 2, 1, 1;
0, 47, 46, 29, 15, 8, 4, 2, 1, 1;
0, 106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
0, 235, 216, 128, 66, 33, 16, 8, 4, 2, 1, 1;

Alois P. Heinz, Rows n = 1..141, flattened
Eric Weisstein's World of Mathematics, Forest

Cf. A095133, A105820, A215930, row-reversed variant of A136605.

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and one or more parts equal to 1, of Product_{i=1..N} binomial(A000055(i)+Ki-1, Ki).

A215930 Number of forests on unlabeled nodes with n edges and no single node trees.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 34, 71, 154, 341, 768, 1765, 4134, 9838, 23766, 58226, 144353, 361899, 916152, 2339912, 6023447, 15617254, 40752401, 106967331, 282267774, 748500921, 1993727506, 5332497586, 14316894271, 38574473086, 104273776038, 282733466684, 768809041078

Offset: 0

Alois P. Heinz, Aug 27 2012

nonn

Each forest counted by a(n) with n>0 has number of nodes from the interval [n+1,2*n] and number of trees in [1,n].
Also limiting sequence of reversed rows of A095133.
Differs from A011782 first at n=6 (32) and from A088325 at n=8 (153).

			a(0) = 1: (  ), the empty forest with 0 trees and 0 edges.
a(1) = 1: ( o-o ), 1 tree and 1 edge.                      o
a(2) = 2: ( o-o-o ), ( o-o o-o ).                          |
a(3) = 4: ( o-o-o-o ), ( o-o-o o-o ), ( o-o o-o o-o ), ( o-o-o ).

Alois P. Heinz, Table of n, a(n) for n = 0..650

Cf. A000055, A005195, A011782, A051491, A088325, A095133, A105821, A136605.

with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/(n-1))
    end:
t:= proc(n) option remember; local k; `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)
    end:
g:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(g(n-i*j, i-1, p-j)*
       binomial(t(i)+j-1, j), j=0..min(n/i, p)))))
    end:
a:= n-> g(2*n, 2*n, n):
seq(a(n), n=0..40);

nn = 30; t[x_] := Sum[a[n] x^n, {n, 1, nn}]; a[0] = 0;
a[1] = 1; sol =
SolveAlways[
  0 == Series[
    t[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}], x];
b[x_] := Sum[a[n] x^n /. sol, {n, 0, nn}]; ft =
Drop[Flatten[
   CoefficientList[Series[b[x] - (b[x]^2 - b[x^2])/2, {x, 0, nn}],
    x]], 1]; Drop[
CoefficientList[
  Series[Product[1/(1 - y ^(i - 1))^ft[[i]], {i, 2, nn}], {y, 0, nn}],
y], -1] (* Geoffrey Critzer, Nov 10 2014 *)

a(n) = A095133(2*n,n).
a(n) = A105821(2*n+1,n+1). - Alois P. Heinz, Jul 10 2013
a(n) = A136605(2*n+1,n). - Alois P. Heinz, Apr 11 2014
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.955765285..., c = 3.36695186... . - Vaclav Kotesovec, Sep 10 2014

A105820 Triangle giving the numbers of different forests of m trees of smallest order 2, i.e., without isolated vertices.

Original entry on oeis.org

0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 3, 1, 0, 0, 0, 6, 3, 1, 0, 0, 0, 11, 5, 1, 0, 0, 0, 0, 23, 12, 3, 1, 0, 0, 0, 0, 47, 23, 6, 1, 0, 0, 0, 0, 0, 106, 52, 14, 3, 1, 0, 0, 0, 0, 0, 235, 110, 29, 6, 1, 0, 0, 0, 0, 0, 0, 551, 253, 68, 15, 3, 1, 0, 0, 0, 0, 0, 0, 1301, 570, 148, 31, 6, 1, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Washington Bomfim, Apr 25 2005

Forests of order N with m components, m > floor(N/2) must contain an isolated vertex since it is impossible to partition N vertices in floor(N/2) + 1 or more trees without giving only one vertex to a tree.

			a(12) = 1 because 5 nodes can be partitioned into two trees only in one way: one tree gets 3 nodes and the other tree gets 2. Since A000055(3) = A000055(2) = 1, there is only one forest. (The forests of order less than or equal to 5 are depicted in the Weisstein link.)

Alois P. Heinz, Rows n = 1..141, flattened
Eric Weisstein's World of Mathematics, Forest

Cf. A033185, A095133, A105786, A105821.

a(n) = sum over the partitions of N: 1K1 + 2K2 + ... + NKN, with exactly m parts and no part equal to 1, of Product_{i=1..N} binomial(A000055(i)+Ki-1, Ki).

G.f.: 1/Product_{i>=2}(1 - x*y^i)^A000055(i). - Vladeta Jovovic, Apr 27 2005

A005199 a(n) = Sum_t t*F(n,t), where F(n,t) is the number of forests with n (unlabeled) nodes and exactly t trees, all of which are planted (that is, rooted trees in which the root has degree 1).

Original entry on oeis.org

0, 1, 1, 4, 6, 18, 35, 93, 214, 549, 1362, 3534, 9102, 23951, 63192, 168561, 451764, 1219290, 3305783, 9008027, 24643538, 67681372, 186504925, 515566016, 1429246490, 3972598378, 11068477743, 30908170493, 86488245455, 242481159915, 681048784377, 1916051725977, 5399062619966

Offset: 1

N. J. A. Sloane

nonn

The triangular array F(n,t) (analogous to A095133 for A005196 and A033185 for A005197) is A336087.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Washington Bomfim, Table of n, a(n) for n = 1..120
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.

Cf. A000081, A336087.

g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;
for(j=1, m, f[j+1]=1/j * sum(k=1, j, sumdiv(k,d, d * f[d]) * f[j-k+1])); f[m+1] };
global(max_n = 130); A000081 = vector(max_n, n, g(n-1));
F(n,t)={my(s=0, D, c, P_1); forpart(P_1 = n, D = Set(P_1); c = vector(#D);
for(k=1, #D, c[k] = #select(x->x == D[k], Vec(P_1)));
s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k]) )
,[2,n],[t,t]); s};
seq(n) = sum(t=1,n\2, t*F(n,t) ); \\   Washington Bomfim, Jul 08 2020

a(n) = Sum_{t=1, floor(n/2)}( t*F(n,t) ), where F(n,t) = Sum_{P_1(n,t)} (Product_{k=2..n} binomial(A000081(k-1) + c_k - 1, c_k)), where P_1(n, t) is the set of the partitions of n with t parts greater than one: 2*c_2 + ... + n*c_n = n; c_2, ..., c_n >= 0. - Washington Bomfim, Jul 08 2020

Definition clarified by N. J. A. Sloane, May 29 2012

A336096 Irregular triangular array read by rows. T(n,k) is the number of unlabeled forests of distinct trees on n nodes containing exactly k trees.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 3, 6, 5, 1, 11, 11, 2, 23, 21, 5, 47, 46, 12, 106, 96, 27, 2, 235, 216, 62, 4, 551, 482, 142, 13, 1301, 1121, 328, 33, 3159, 2633, 763, 87, 1, 7741, 6334, 1809, 211, 6, 19320, 15414, 4322, 532, 18, 48629, 38132, 10488, 1301, 55, 123867, 95321, 25710, 3232, 157, 317955, 241029, 63802, 7996, 429, 3, 823065, 614862, 159817, 19973, 1149, 12

Offset: 1

Geoffrey Critzer, Jul 09 2020

			Triangle begins:
    1;
    1;
    1,  1;
    2,  1;
    3,  3;
    6,  5,  1;
   11, 11,  2;
   23, 21,  5;
   47, 46, 12;
  106, 96, 27, 2;
  ...

Cf. A035055 (row sums), A000055 (column 1), A095133.

nn = 20; f[x_] := Sum[a[n] x^n, {n, 0, nn}]; sol = SolveAlways[0 == Series[f[x] - x Product[1/(1 - x^i)^a[i], {i, 1, nn}], {x, 0, nn}], x]; r[x_] := Sum[a[n] x^n, {n, 0, nn}] /. sol; b = Drop[Flatten[CoefficientList[Series[r[x] - 1/2 (r[x]^2 - r[x^2]), {x, 0, nn}],x]], 1]; Map[Select[#, # > 0 &] &, Drop[CoefficientList[
    Series[Product[(1 + y x^n)^b[[n]], {n, 1, nn}], {x, 0, nn}], {x,y}], 1]] // Grid

O.g.f.: Product_n>=1 (1+ y*x^n)^A000055(n).

cp's OEIS Frontend

A005196 a(n) = Sum_t t*F(n,t), where F(n,t) (see A095133) is the number of forests with n (unlabeled) nodes and exactly t trees.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

A005195 Number of forests with n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A274937 Number of unlabeled forests on n nodes that have exactly two nonempty components.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A105821 Triangle of the numbers of different forests with one or more isolated vertices. Those forests have order N and m trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A215930 Number of forests on unlabeled nodes with n edges and no single node trees.

Views

Author

Keywords