|
|
A245120
|
|
Number T(n,k) of n-node rooted identity trees with thinning limbs and root outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=max-index-of-row(n), read by rows.
|
|
12
|
|
|
1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 3, 0, 1, 4, 1, 0, 1, 8, 2, 0, 1, 12, 4, 0, 1, 22, 9, 0, 1, 36, 17, 2, 0, 1, 63, 35, 3, 0, 1, 107, 67, 9, 0, 1, 188, 131, 20, 0, 1, 327, 249, 46, 1, 0, 1, 578, 484, 94, 4, 0, 1, 1020, 922, 202, 11, 0, 1, 1820, 1775, 412, 28
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,14
|
|
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
|
|
|
EXAMPLE
|
The A124346(7) = 6 7-node rooted identity trees with thinning 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 o o : o o :
: | : | | | | : | :
: o : o o o o : o :
: | : | | | : :
: o : o o o : :
: | : | : :
: o : o : :
: | : : :
: o : : :
: : : :
: -1- : -------------2------------ : --3-- :
Thus row 7 = [0, 1, 4, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1;
0, 1, 1;
0, 1, 1;
0, 1, 3;
0, 1, 4, 1;
0, 1, 8, 2;
0, 1, 12, 4;
0, 1, 22, 9;
0, 1, 36, 17, 2;
0, 1, 63, 35, 3;
|
|
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, add(binomial(A(i, min(i-1, h)), 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:
g:= proc(n) local k; if n=1 then 0 else
for k while T(n, k)>0 do od; k-1 fi
end:
T:= (n, k)-> b(n-1$2, k$2):
seq(seq(T(n, k), k=0..g(n)), n=1..25);
|
|
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, Sum[Binomial[A[i, Min[i-1, h]], 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]}]]; g[n_] := If[n==1, 0, For[k=1, T[n, k]>0, k++]; k-1]; T[n_, k_] := b[n-1, n-1, k, k]; Table[T[n, k], {n, 1, 25}, {k, 0, g[n]}] // Flatten (* Jean-François Alcover, Jan 18 2017, translated from Maple *)
|
|
CROSSREFS
|
Column k=0-10 give: A000007(n-1), A000012 (for n>1), A245121, A245122, A245123, A245124, A245125, A245126, A245127, A245128, A245129.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|