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
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
-
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 *)
A144528
Triangle read by rows: T(n,k) is the number of trees on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).
Original entry on oeis.org
1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 4, 5, 6, 0, 0, 1, 6, 9, 10, 11, 0, 0, 1, 11, 18, 21, 22, 23, 0, 0, 1, 18, 35, 42, 45, 46, 47, 0, 0, 1, 37, 75, 94, 101, 104, 105, 106, 0, 0, 1, 66, 159, 204, 223, 230, 233, 234, 235, 0, 0, 1, 135, 355, 473, 520, 539, 546, 549, 550, 551
Offset: 1
Triangle begins:
1
0 1
0 0 1
0 0 1 2
0 0 1 2 3
0 0 1 4 5 6
0 0 1 6 9 10 11
0 0 1 11 18 21 22 23
0 0 1 18 35 42 45 46 47
0 0 1 37 75 94 101 104 105 106
...
From _Andrew Howroyd_, Dec 17 2020: (Start)
Formatted as an array to show the full columns:
================================================
n\k | 0 1 2 3 4 5 6 7 8 9 10
-----+------------------------------------------
1 | 1 1 1 1 1 1 1 1 1 1 1 ...
2 | 0 1 1 1 1 1 1 1 1 1 1 ...
3 | 0 0 1 1 1 1 1 1 1 1 1 ...
4 | 0 0 1 2 2 2 2 2 2 2 2 ...
5 | 0 0 1 2 3 3 3 3 3 3 3 ...
6 | 0 0 1 4 5 6 6 6 6 6 6 ...
7 | 0 0 1 6 9 10 11 11 11 11 11 ...
8 | 0 0 1 11 18 21 22 23 23 23 23 ...
9 | 0 0 1 18 35 42 45 46 47 47 47 ...
10 | 0 0 1 37 75 94 101 104 105 106 106 ...
11 | 0 0 1 66 159 204 223 230 233 234 235 ...
12 | 0 0 1 135 355 473 520 539 546 549 550 ...
...
(End)
-
b[n_, i_, t_, k_] := b[n, i, t, k] = If[i<1, 0, Sum[Binomial[b[i-1, i-1,
k, k] + j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; a = {}; nmax = 20;
For[ni=2, ni < nmax-1, ni++, (* columns 3 to max-1 *)
gf[x_] = 1 + Sum[b[j-1, j-1, ni, ni] x^j, {j, 1, nmax}];
ci[x_] = SymmetricGroupIndex[ni+1, x] /. x[i_] -> gf[x^i];
a = Append[a, CoefficientList[Normal[Series[
gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x], {x, 0, nmax}]], x]];]
Join[{1, 0, 1, 0, 0, 1}, Table[Join[{0, 0, 1}, Table[a[[k-3]][[n+1]],
{k, 4, n}]], {n, 4, nmax}]] // Flatten (* Robert A. Russell, Feb 05 2023 *)
-
\\ here V(n,k) gives column k as a vector.
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={Mat(vector(m, k, V(n,k-1)[2..1+n]~))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020
a(53) corrected and terms a(56) and beyond from
Andrew Howroyd, Dec 17 2020
A339788
Triangle read by rows: T(n,k) is the number of forests with n unlabeled vertices and maximum vertex degree k, (0 <= k < n).
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 3, 7, 6, 2, 1, 1, 3, 11, 13, 6, 2, 1, 1, 4, 17, 30, 15, 6, 2, 1, 1, 4, 25, 60, 39, 15, 6, 2, 1, 1, 5, 36, 128, 94, 41, 15, 6, 2, 1, 1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1, 1, 6, 70, 523, 561, 270, 105, 41, 15, 6, 2, 1
Offset: 1
Triangle begins:
1;
1, 1;
1, 1, 1;
1, 2, 2, 1;
1, 2, 4, 2, 1;
1, 3, 7, 6, 2, 1;
1, 3, 11, 13, 6, 2, 1;
1, 4, 17, 30, 15, 6, 2, 1;
1, 4, 25, 60, 39, 15, 6, 2, 1;
1, 5, 36, 128, 94, 41, 15, 6, 2, 1;
1, 5, 50, 254, 232, 103, 41, 15, 6, 2, 1;
...
-
\\ Here V(n, k) gives column k of A144528.
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={my(v=vector(m, k, EulerT(V(n,k-1)[2..1+n])~)); Mat(vector(m, k, v[k]-if(k>1, v[k-1])))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) }
A144529
Triangle read by rows: T(n,k) = number of edges in graph whose vertices are forests with n unlabeled nodes and degree <= k and in which two vertices are joined by an edge if the forests differ (up to isomorphism) by exactly one edge.
Original entry on oeis.org
0, 0, 1, 0, 1, 2, 0, 2, 5, 6, 0, 2, 9, 13, 14, 0, 3, 18, 32, 36, 37, 0, 3, 28, 67, 82, 87, 88
Offset: 1
Triangle begins:
0
0 1
0 1 2
0 2 5 6
0 2 9 13 14
0 3 18 32 36 37
0 3 28 67 82 87 88
Showing 1-4 of 4 results.
Comments