Search: a245103 -id:a245103
|
| |
|
|
A034781
|
|
Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.
|
|
+10
48
|
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 18, 13, 5, 1, 1, 14, 38, 36, 19, 6, 1, 1, 21, 76, 93, 61, 26, 7, 1, 1, 29, 147, 225, 180, 94, 34, 8, 1, 1, 41, 277, 528, 498, 308, 136, 43, 9, 1, 1, 55, 509, 1198, 1323, 941, 487, 188, 53, 10, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,5
|
|
|
LINKS
|
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
|
|
|
FORMULA
|
Reference gives recurrence.
|
|
|
EXAMPLE
|
Triangle begins:
1;
1 1;
1 2 1;
1 4 3 1;
1 6 8 4 1;
1 10 18 13 5 1;
1 14 38 36 19 6 1;
thus there are 10 trees with 7 nodes and height 2.
|
|
|
MAPLE
|
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
end:
T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
|
|
|
MATHEMATICA
|
Drop[Map[Select[#, # > 0 &] &,
Transpose[
Prepend[Table[
f[n_] :=
Nest[CoefficientList[
Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1 || k<1, 0, Sum[Binomial[b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k]-b[n-1, n-1, k-1]; Table[T[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A339440
|
|
Number of linear forests with n rooted trees and 2*n-1 nodes.
|
|
+10
3
|
|
|
|
0, 1, 2, 9, 44, 230, 1236, 6790, 37832, 213057, 1209660, 6912367, 39705516, 229055918, 1326168018, 7701734250, 44846271632, 261735599172, 1530650010312, 8967361033572, 52619233554120, 309203221308702, 1819290987055630, 10716835948503349, 63196331969007264
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) ~ c * d^n / sqrt(n), where d = 6.031382795097860532993547039674008662345079835351392549515262162478014679... and c = 0.05599525103242350197279211300654208236718263537075... - Vaclav Kotesovec, Dec 18 2020
|
|
|
MAPLE
|
b:= proc(n) option remember; `if`(n<2, n, (add(add(d*b(d),
d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))
end:
T:= proc(n, k) option remember; `if`(k=1, b(n), (t->
add(T(j, t)*T(n-j, k-t), j=1..n-1))(iquo(k, 2)))
end:
a:= n-> T(2*n-1, n):
seq(a(n), n=0..24);
|
|
|
MATHEMATICA
|
b[n_] := b[n] = If[n<2, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}])/(n - 1)];
T[n_, k_] := T[n, k] = If[k == 1, b[n], With[{t = Quotient[k, 2]}, Sum[T[j, t]*T[n - j, k - t], {j, 1, n - 1}]]];
a[n_] := T[2n-1, n];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.006 seconds
|
