login
A244372
Number T(n,k) of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
25
1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 2, 1, 0, 1, 10, 6, 2, 1, 0, 1, 22, 16, 6, 2, 1, 0, 1, 45, 43, 17, 6, 2, 1, 0, 1, 97, 113, 49, 17, 6, 2, 1, 0, 1, 206, 300, 136, 50, 17, 6, 2, 1, 0, 1, 450, 787, 386, 142, 50, 17, 6, 2, 1, 0, 1, 982, 2074, 1081, 409, 143, 50, 17, 6, 2, 1
OFFSET
1,9
LINKS
EXAMPLE
The A000081(5) = 9 rooted trees with 5 nodes sorted by maximal 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 o o : : :
: | : : : :
: o : : : :
: : : : :
: -1- : ---------------2--------------- : -----3----- : ---4--- :
Thus row 5 = [0, 1, 5, 2, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 1, 2, 1;
0, 1, 5, 2, 1;
0, 1, 10, 6, 2, 1;
0, 1, 22, 16, 6, 2, 1;
0, 1, 45, 43, 17, 6, 2, 1;
0, 1, 97, 113, 49, 17, 6, 2, 1;
0, 1, 206, 300, 136, 50, 17, 6, 2, 1;
0, 1, 450, 787, 386, 142, 50, 17, 6, 2, 1;
0, 1, 982, 2074, 1081, 409, 143, 50, 17, 6, 2, 1;
MAPLE
b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
`if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
end:
T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):
seq(seq(T(n, k), k=0..n-1), n=1..14);
MATHEMATICA
b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[b[i-1, i-1, k, k]+j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[k == 0, 0, b[n-1, n-1, k-1, k-1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jul 01 2014, translated from Maple *)
CROSSREFS
T(2n,n) gives A244407(n).
T(2n+1,n) gives A244410(n).
Row sum give A000081.
Cf. A244454.
Sequence in context: A220235 A066603 A263339 * A370773 A119331 A351641
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt and Alois P. Heinz, Jun 26 2014
STATUS
approved