login
A244703
Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 2.
2
1, 1, 3, 4, 9, 13, 26, 42, 81, 138, 262, 467, 885, 1620, 3076, 5743, 10953, 20721, 39714, 75873, 146139, 281259, 544230, 1053552, 2047147, 3981790, 7766018, 15165195, 29676887, 58148087, 114129308, 224278526, 441368913, 869583189, 1715365690, 3387344619
OFFSET
3,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
FORMULA
a(n) ~ c * d^n / n^(3/2), where d = 2.0554620926822709065075792..., c = 1.0209036918758320315742... . - Vaclav Kotesovec, Aug 27 2014
EXAMPLE
a(6) = 4:
o o o o
/ \ / \ / \ / \
o o o o o o o o
| / \ | | / \ |
o o o o o o o o
| | |
o o o
|
o
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 2$2):
seq(a(n), n=3..50);
MATHEMATICA
b[n_, i_, h_, v_] := b[n, i, h, v] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[n == v, 1, Sum[Binomial[A[i, Min[i - 1, h]] + j - 1, j]*b[n - i*j, i - 1, h, v - j], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n<2, n, Sum[b[n-1, n-1, j, j], {j, 1, Min[k, n-1] }]];
a[n_] := b[n-1, n-1, 2, 2];
a /@ Range[3, 50] (* Jean-François Alcover, Dec 27 2020, after Alois P. Heinz *)
CROSSREFS
Column k=2 of A244657.
Sequence in context: A250111 A079284 A000624 * A232801 A357238 A056514
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved