A033185 -id:A033185 - cp's OEIS frontend

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

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

A029855 Number of rooted trees where root has degree 4.

Original entry on oeis.org

1, 1, 3, 7, 19, 46, 124, 320, 858, 2282, 6161, 16647, 45352, 123861, 340000, 936098, 2586518, 7166394, 19911638, 55456892, 154814055, 433081632, 1213901668, 3408659401, 9587879987, 27011564035, 76212078500

Offset: 5

Christian G. Bower

nonn

Fourth column of A033185. - Michael Somos, Aug 20 2018

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 53.

Washington Bomfim, Table of n, a(n) for n = 5..200
Frank Ruskey, Combinatorial Generation Algorithm 4.26, p. 96
Eric Weisstein's World of Mathematics, Frequency Representation
Eric Weisstein's World of Mathematics, Rooted Tree
Index entries for sequences related to rooted trees

Cf. A000226 (root degree 3), A000081, A033185.

Needs["Combinatorica`"];
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);rt=Table[a[i],{i,1,nn}];Drop[Take[CoefficientList[CycleIndex[SymmetricGroup[4],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],4]  (* Geoffrey Critzer, Oct 14 2012, after code by Robert A. Russell in A000081 *)

max_n = 200; f=vector(max_n);            \\ f[n] = A000081[n], n=1..max_n
sum2(k) = {local(s); s=0; fordiv(k, d, s += d*f[d]); return(s)};
Init_f()={f[1]=1;
for(n =1, max_n -2, s=0; for(k=1, n, s+=sum2(k)*f[n-k+1]); f[n+1]=s/n)};
S=0; P=[0,1,1,1,1,0];
visit4() = {i = 3; k = 2; p = P[2]; Pr = 1;
while(1, while(P[i]==p, i++);c=i-k;Pr*=binomial(f[P[k]]+c-1, c);
if(P[i] == 0, S += Pr; return); p = P[i]; k = i; i++)};
                                         \\ F. Ruskey partition generator
Part(n, k, s, t) = { P[t] = s;
if((k == 1) || (n == k), visit4(), L = max(1, ceil((n - s)/(k - 1)));
for(j = L, min(s, n-s-k+2), Part(n-s, k-1, j, t+1))); P[t] = 1;};
\\
a(n) = {S=0; n--; Part(2*n,4+1,n,1); return(S)}
Init_f(); for(n=5, max_n, print(n, " ", a(n)))           \\ b-file format
\\ # Washington Bomfim, Jul 10 2012

a(n)= Sum_(P){ Prod_(1^a1 2^a2 3^a3 ...){ binomial(f(i)+a_i -1, a_i) } }, where P is the set of the partitions of n with four parts, and f = A000081. - Washington Bomfim, Jul 10 2012

a(n) ~ c * A051491^n / n^(3/2), where c = 0.036592912312268101787903577... - Vaclav Kotesovec, Dec 26 2020

A105819 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

Original entry on oeis.org

0, 2, 0, 9, 0, 0, 64, 12, 0, 0, 625, 180, 0, 0, 0, 7776, 2730, 120, 0, 0, 0, 117649, 46410, 3780, 0, 0, 0, 0, 2097152, 893816, 99120, 1680, 0, 0, 0, 0, 43046721, 19389384, 2600640, 90720, 0, 0, 0, 0, 0, 1000000000, 469532790, 71734320, 3654000, 30240, 0

Offset: 1

Washington Bomfim, Apr 21 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.

Also the Bell transform of A055860. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			a(8) = 12 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. Two trees on 2 vertices can be labeled in binomial(4,2) ways and to each one of the 2*binomial(4,2) = 12 possibilities there are more 2 possible trees of order 2 in a forest. But since we have 2 trees of the same order, i.e., 2, we must divide 2*binomial(4,2)*2 by 2!.
Triangle T(n,k) begins:
:       0;
:       2,      0;
:       9,      0,     0;
:      64,     12,     0,    0;
:     625,    180,     0,    0, 0;
:    7776,   2730,   120,    0, 0, 0;
:  117649,  46410,  3780,    0, 0, 0, 0;
: 2097152, 893816, 99120, 1680, 0, 0, 0, 0;

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

Cf. A033185, A055860, A105599, A354794, A360193.

Row sums give A105785.

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0,0,(n+1)^n), 9); # Peter Luschny, Jan 27 2016
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
       binomial(n-1, j-1)*j^(j-1)*x*b(n-j), j=2..n)))
    end:
T:= (n, k)-> coeff(b(n), x, k):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Aug 13 2017

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^n]], rows];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N: 1K1 + 2K2 + ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*Product_{i=1..N}i^((i-1)Ki) and D = Product_{i=1..N}(Ki!(i!)^Ki).
From Mélika Tebni, Apr 23 2023: (Start)
E.g.f. of column k: (-x - LambertW(-x))^k / k!, k > 0.
Sum_{k=1..n} (-1)^(n-k)*T(n+k,k) = n+1.
Sum_{k=1..n} (-1)^(k+1)*T(n,k) = A360193(n), for n > 0.
Sum_{k=1..n} (-1)^(k+1)*T(n+k,k)/(n+k-1) = 1/n, for n > 1.
T(n,k) = Sum_{j=k..n} j!*abs(Stirling1(j-k,k))*A354794(n,j)/(j-k)!. (End)

A336087 Triangle read by rows: T(n, k) is the number of forests with n (unlabeled) nodes and k planted trees.

Original entry on oeis.org

0, 1, 0, 1, 0, 0, 2, 1, 0, 0, 4, 1, 0, 0, 0, 9, 3, 1, 0, 0, 0, 20, 6, 1, 0, 0, 0, 0, 48, 16, 3, 1, 0, 0, 0, 0, 115, 37, 7, 1, 0, 0, 0, 0, 0, 286, 96, 18, 3, 1, 0, 0, 0, 0, 0, 719, 239, 44, 7, 1, 0, 0, 0, 0, 0, 0, 1842, 622, 117, 19, 3, 1, 0, 0, 0, 0, 0, 0, 4766, 1607, 299, 46, 7, 1, 0, 0, 0, 0, 0, 0, 0, 12486, 4235, 793, 124

Offset: 1

Washington Bomfim, Jul 08 2020

The number of planted trees with n+1 nodes is equal to the number of rooted trees with n nodes. [See Palmer-Schwenk link, pp. 115].

			                           Triangle T(n,k)
n\k     1      2     3    4   5  6  7  8 9 10 11 12 13 14 15
1       0;
2       1,     0;
3       1,     0,    0;
4       2,     1,    0,   0;
5       4,     1,    0,   0,  0;
6       9,     3,    1,   0,  0, 0;
7      20,     6,    1,   0,  0, 0, 0;
8      48,    16,    3,   1,  0, 0, 0, 0;
9     115,    37,    7,   1,  0, 0, 0, 0, 0;
10    286,    96,   18,   3,  1, 0, 0, 0, 0, 0;
11    719,   239,   44,   7,  1, 0, 0, 0, 0, 0, 0;
12   1842,   622,  117,  19,  3, 1, 0, 0, 0, 0, 0, 0;
13   4766,  1607,  299,  46,  7, 1, 0, 0, 0, 0, 0, 0, 0;
14  12486,  4235,  793, 124, 19, 3, 1, 0, 0, 0, 0, 0, 0, 0;
15  32973, 11185, 2095, 320, 47, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0;
                           ...
n\k     1      2     3    4   5  6  7  8  9 10 11 12 13 14 15
A005199(6) = Sum_{k=1..6}( k * T(6,k) ) = 1*9 + 2*3 +3*1 = 18.

E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
Index entries for sequences related to rooted trees

Cf. A000081, A005199, A005198 (row sums), A033185.

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); if(n==1,return(0)); 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};

T(1,1) = 0, if n >= 2 T(n,k) = Sum_{P_1(n,k)}( Product_{j=2..n} binomial(A000081(j-1) + c_j - 1, c_j) ), where P_1(n, k) is the set of the partitions of n with k parts greater than one: 2*c_2 + ... + n*c_n = n; c_2, ..., c_n >= 0.

If k > floor(n/2), T(n,k) = 0; otherwise T(n,k) = A033185(n-k, k).

A105786 Triangle of the numbers of different forests of m unrooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

Original entry on oeis.org

0, 1, 0, 3, 0, 0, 16, 3, 0, 0, 125, 30, 0, 0, 0, 1296, 330, 15, 0, 0, 0, 16807, 4305, 315, 0, 0, 0, 0, 262144, 66248, 5880, 105, 0, 0, 0, 0, 4782969, 1183644, 115290, 3780, 0, 0, 0, 0, 0, 100000000, 24170310, 2467080, 107100, 945, 0, 0, 0, 0, 0, 2357947691, 556409535

Offset: 1

Washington Bomfim, Apr 21 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.

Also the Bell transform of A000272(n+1) (with a(0)=0). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			a(8) = 3 because 4 vertices can be partitioned in two trees only in one way: both trees receiving 2 vertices. The unique tree on 2 vertices can be labeled in binomial(4,2) ways and to each one of the binomial(4,2) = 6 possibilities there is just another tree of order 2 in a forest. But since we have 2 trees of the same order, i.e., 2, we must divide binomial(4,2) by 2!.

Cf. A033185, A105599.

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> `if`(n=0,0,(n+1)^(n-1)), 9); # Peter Luschny, Jan 27 2016

BellMatrix[f_, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
B = BellMatrix[Function[n, If[n == 0, 0, (n+1)^(n-1)]], rows = 12];
Table[B[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 28 2018, after Peter Luschny *)

a(n)= 0, if m > floor(N/2) (see comments), or can be calculated by the sum Num/D over the partitions of N: 1K1 + 2K2+ ... + nKN, with exactly m parts and smallest part = 2, where Num = N!*Product_{i=1..N}i^((i-2)Ki) and D = Product_{i=1..N}(Ki!(i!)^Ki).

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

Original entry on oeis.org

0, 1, 0, 2, 0, 0, 4, 1, 0, 0, 9, 2, 0, 0, 0, 20, 7, 1, 0, 0, 0, 48, 17, 2, 0, 0, 0, 0, 115, 48, 7, 1, 0, 0, 0, 0, 286, 124, 21, 2, 0, 0, 0, 0, 0, 719, 336, 60, 7, 1, 0, 0, 0, 0, 0, 1842, 888, 171, 21, 2, 0, 0, 0, 0, 0, 0, 4766, 2393, 488, 65, 7, 1, 0, 0, 0, 0, 0, 0

Offset: 1

Washington Bomfim, Apr 26 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. A033185(n) = A106235(n) + A106234(n).

			a(12)=2 because 5 nodes can be partitioned in two trees only in a way: one tree gets 3 nodes and the other tree gets 2. Since A000081(3) = 2 and A000081(2)=1, there are two forests.
Triangle T(n,k) begins:
    0;
    1,   0;
    2,   0,  0;
    4,   1,  0, 0;
    9,   2,  0, 0, 0;
   20,   7,  1, 0, 0, 0;
   48,  17,  2, 0, 0, 0, 0;
  115,  48,  7, 1, 0, 0, 0, 0;
  286, 124, 21, 2, 0, 0, 0, 0, 0;
  719, 336, 60, 7, 1, 0, 0, 0, 0, 0;

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

Cf. A033185, A106234.

with(numtheory):
g:= proc(n) option remember; `if`(n<=1, n, (add(add(
      d*g(d), d=divisors(j))*g(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=1,
      0, expand(add(x^j*b(n-i*j, i-1)*
      binomial(g(i)+j-1, j), j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Jun 25 2014

g[n_] := g[n] = If[n <= 1, n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n-j], {j, 1, n-1}])/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i == 1, 0, Expand[Sum[x^j*b[n-i*j, i-1]*Binomial[g[i]+j-1, j], {j, 0, n/i}]]]]; T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, n]]; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 05 2015, after Alois P. Heinz *)

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(A000081(i)+Ki-1, Ki).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A029855 Number of rooted trees where root has degree 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A105819 Triangle of the numbers of different forests of m rooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A336087 Triangle read by rows: T(n, k) is the number of forests with n (unlabeled) nodes and k planted trees.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A105786 Triangle of the numbers of different forests of m unrooted trees of smallest order 2, i.e., without isolated vertices, on N labeled nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula