|
|
A245151
|
|
Number T(n,k) of n-node unlabeled rooted trees with thickening limbs and root outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
|
|
12
|
|
|
1, 0, 1, 0, 1, 1, 0, 2, 0, 1, 0, 3, 1, 0, 1, 0, 5, 1, 0, 0, 1, 0, 7, 3, 1, 0, 0, 1, 0, 12, 3, 1, 0, 0, 0, 1, 0, 17, 8, 1, 1, 0, 0, 0, 1, 0, 28, 9, 3, 1, 0, 0, 0, 0, 1, 0, 42, 21, 3, 1, 1, 0, 0, 0, 0, 1, 0, 69, 28, 5, 1, 1, 0, 0, 0, 0, 0, 1, 0, 105, 56, 9, 3, 1, 1, 0, 0, 0, 0, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,8
|
|
COMMENTS
|
In a rooted tree with thickening limbs the outdegree of a parent node is smaller than or equal to the outdegree of any of its non-leaf child nodes.
T(n+1,1) = Sum_{k=0..n-1} T(n,k) for n>=1.
T(n+1,n) = T(2n+1,n) = 1 for n>=0.
T(n,1+floor((n-1)/2)) = 0 for n>3.
|
|
LINKS
|
|
|
EXAMPLE
|
The A245152(5) = 5 5-node rooted trees with thickening limbs sorted by root outdegree are:
: o o o : o : o :
: | | | : / \ : /( )\ :
: o o o : o o : o o o o :
: | | /|\ : / \ : :
: o o o o o : o o : :
: | / \ : : :
: o o o : : :
: | : : :
: o : : :
: : : :
: ------1------ : ---2--- : ---4--- :
Thus row 5 = [0, 3, 1, 0, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 0, 1;
0, 3, 1, 0, 1;
0, 5, 1, 0, 0, 1;
0, 7, 3, 1, 0, 0, 1;
0, 12, 3, 1, 0, 0, 0, 1;
0, 17, 8, 1, 1, 0, 0, 0, 1;
0, 28, 9, 3, 1, 0, 0, 0, 0, 1;
0, 42, 21, 3, 1, 1, 0, 0, 0, 0, 1;
0, 69, 28, 5, 1, 1, 0, 0, 0, 0, 0, 1;
0, 105, 56, 9, 3, 1, 1, 0, 0, 0, 0, 0, 1;
0, 176, 81, 12, 3, 1, 1, 0, 0, 0, 0, 0, 0, 1;
|
|
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, 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=k..n-1))
end:
T:= (n, k)-> b(n-1$2, k$2):
seq(seq(T(n, k), k=0..n-1), n=1..20);
|
|
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, 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, k, n-1}]]; T[n_, k_] := b[n-1, n-1, k, k]; Table[ Table[T[n, k], {k, 0, n - 1}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)
|
|
CROSSREFS
|
Columns k=0-10 give: A000007(n-1), A245152(n-1), A245142, A245143, A245144, A245145, A245146, A245147, A245148, A245149, A245150.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|