A136605 -id:A136605 - cp's OEIS frontend

A005195 Number of forests with n unlabeled nodes.

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

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 6, 15, 16, 1, 10, 45, 110, 125, 1, 15, 105, 435, 1080, 1296, 1, 21, 210, 1295, 5250, 13377, 16807, 1, 28, 378, 3220, 18865, 76608, 200704, 262144, 1, 36, 630, 7056, 55755, 320544, 1316574, 3542940, 4782969, 1, 45, 990, 14070, 143325, 1092105, 6258000, 26100000, 72000000, 100000000

Offset: 1

N. J. A. Sloane, May 09 2008

The rows of the triangle give the coefficients of the Ehrhart polynomials of integral Coxeter permutahedra of type A. These polynomials count lattice points in a dilated lattice polytope. For a definition see Ardila et al. (p. 1158), the generating functions of these polynomials for the classical root systems are given in theorem 5.2 (p. 1163). - Peter Luschny, May 01 2021

			Triangle begins:
[1]  1;
[2]  1,  1;
[3]  1,  3,   3;
[4]  1,  6,  15,   16;
[5]  1, 10,  45,  110,  125;
[6]  1, 15, 105,  435, 1080,  1296;
[7]  1, 21, 210, 1295, 5250, 13377, 16807;

Alois P. Heinz, Rows n = 1..141, flattened
Federico Ardila, Matthias Beck, and Jodi McWhirter, The arithmetic of Coxeter permutahedra, Rev. Acad. Colomb. Cienc. Ex. Fis. Nat. 44(173):1152-1166, 2020.
John Riordan and N. J. A. Sloane, Correspondence, 1974

Row sums give A001858. Rightmost diagonal gives A000272. Cf. A136605.
Rows reflected give A105599. - Alois P. Heinz, Oct 28 2011
Cf. A088956.
Lower diagonals give: A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687. - Alois P. Heinz, Apr 11 2014
T(2n,n) gives A302112.
For Ehrhart polynomials of integral Coxeter permutahedra of classical type cf. this sequence (type A), A343805 (type B), A343806 (type C), A343807 (type D).

T:= proc(n) option remember; if n=0 then 0 else T(n-1) +n^(n-1) *x^n/n! fi end: TT:= proc(n) option remember; expand(T(n) -T(n)^2/2) end: f:= proc(k) option remember; if k=0 then 1 else unapply(f(k-1)(x) +x^k/k!, x) fi end: A:= proc(n,k) option remember; series(f(k)(TT(n)), x,n+1) end: aa:= (n,k)-> coeff(A(n,k), x,n) *n!: a:= (n,k)-> aa(n,n-k) -aa(n,n-k-1): seq(seq(a(n,k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 02 2008
alias(W = LambertW): EhrA := exp(-W(-t*x)/t - W(-t*x)^2/(2*t)):
ser := series(EhrA, x, 12): cx := n -> n!*coeff(ser, x, n):
T := n -> seq(coeff(cx(n), t, k), k=0..n-1):
seq(T(n), n = 1..10); # Peter Luschny, Apr 30 2021

t[0, 0] = 1; t[n_ /; n >= 1, k_] /; (0 <= k <= n-1) := t[n, k] = Sum[(i+1)^(i-1)*Binomial[n-1, i]*t[n-i-1, k-i], {i, 0, k}]; t[, ] = 0; Table[t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Peter Bala *)
gf := E^(-(ProductLog[-(t x)] (2 + ProductLog[-(t x)]))/(2 t));
ser := Series[gf, {x, 0, 12}]; cx[n_] := n! Coefficient[ser, x, n];
Table[CoefficientList[cx[n], t], {n, 1, 10}] // Flatten  (* Peter Luschny, May 01 2021 *)

From Peter Bala, Aug 14 2012: (Start)
T(n+1,k) = Sum_{i=0..k} (i+1)^(i-1)*binomial(n,i)*T(n-i,k-i) with T(0,0)=1.
Recurrence equation for row polynomials R(n,t): R(n,t) = Sum_{k=0..n-1} (k+1)^(k-1)*binomial(n-1,k)*t^k*R(n-k-1,t) with R(0,t) = R(1,t) = 1.
The production matrix for the row polynomials of the triangle is obtained from A088956 and starts:
    1    t
    1    1    t
    3    2    1    t
   16    9    3    1    t
  125   64   18    4    1   t
(End)
E.g.f.: exp( Sum_{n >= 1} n^(n-2)*t^(n-1)*x^n/n! ). - Peter Bala, Nov 08 2015
T(n, k) = [t^k] n! [x^n] exp(-W(-t*x)/t - W(-t*x)^2/(2*t)), where W denotes the Lambert function. - Peter Luschny, Apr 30 2021 [Typo corrected after note from Andrew Howroyd, Peter Luschny, Jun 20 2021]

More terms from Alois P. Heinz, Sep 02 2008

A095133 Triangle of numbers of forests on n nodes containing k trees.

Original entry on oeis.org

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

Offset: 1

Eric W. Weisstein, May 29 2004

Row sums are A005195.

For k > n/2, T(n,k) = T(n-1,k-1). - Geoffrey Critzer, Oct 13 2012

			Triangle begins:
    1;
    1,  1;
    1,  1,  1;
    2,  2,  1,  1;
    3,  3,  2,  1,  1;
    6,  6,  4,  2,  1, 1;
   11, 11,  7,  4,  2, 1, 1;
   23, 23, 14,  8,  4, 2, 1, 1;
   47, 46, 29, 15,  8, 4, 2, 1, 1;
  106, 99, 60, 32, 16, 8, 4, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
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 6 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Forest

Cf. A005195 (row sums), A005196, A106240, A000055 (first column), A274937 (2nd column), A105821.
Limiting sequence of reversed rows gives A215930.
Reflected table is A136605. - Alois P. Heinz, Apr 11 2014

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, k)-> g(n, n, k):
seq(seq(a(n, k), k=1..n), n=1..14);  # 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[Product[1/(1-y x^i)^ft[[i]],{i,1,nn}],{x,0,20}],{x,y}]//Grid (* Geoffrey Critzer, Oct 13 2012, after code given by Robert A. Russell in A000055 *)

T(n, k) = sum over the partitions of n, 1M1 + 2M2 + ... + nMn, with exactly k parts, of Product_{i=1..n} binomial(A000055(i) + Mi - 1, Mi). - Washington Bomfim, May 12 2005

More terms from Vladeta Jovovic, Jun 03 2004

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

cp's OEIS Frontend

A005195 Number of forests with n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A095133 Triangle of numbers of forests on n nodes containing k trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula