login
A244657
Number T(n,k) of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
14
1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 3, 1, 1, 0, 1, 4, 3, 1, 1, 0, 1, 9, 6, 3, 1, 1, 0, 1, 13, 13, 6, 3, 1, 1, 0, 1, 26, 25, 15, 6, 3, 1, 1, 0, 1, 42, 55, 29, 15, 6, 3, 1, 1, 0, 1, 81, 107, 68, 31, 15, 6, 3, 1, 1, 0, 1, 138, 224, 140, 72, 31, 15, 6, 3, 1, 1
OFFSET
1,13
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 A124343(5) = 6 5-node rooted 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 : : : :
: : : : :
: -1- : ---------2--------- : --3-- : ---4--- :
Thus row 5 = [0, 1, 3, 1, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 1, 3, 1, 1;
0, 1, 4, 3, 1, 1;
0, 1, 9, 6, 3, 1, 1;
0, 1, 13, 13, 6, 3, 1, 1;
0, 1, 26, 25, 15, 6, 3, 1, 1;
0, 1, 42, 55, 29, 15, 6, 3, 1, 1;
0, 1, 81, 107, 68, 31, 15, 6, 3, 1, 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, 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:
T:= (n, k)-> b(n-1$2, k$2):
seq(seq(T(n, k), k=0..n-1), n=1..14);
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]}]]; T[n_, k_] := b[n-1, n-1, k, k]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Feb 03 2015, after Alois P. Heinz *)
CROSSREFS
Columns k=0-10 give: A000007(n-1), A000012 (for n>1), A244703, A244704, A244705, A244706, A244707, A244708, A244709, A244710, A244711.
T(2n,n) gives A244712.
Row sums give A124343.
Sequence in context: A088205 A318923 A336111 * A072024 A238010 A370772
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved