login
A244454
Number T(n,k) of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
13
1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 7, 1, 0, 1, 0, 17, 2, 0, 0, 1, 0, 42, 4, 1, 0, 0, 1, 0, 105, 7, 2, 0, 0, 0, 1, 0, 267, 15, 2, 1, 0, 0, 0, 1, 0, 684, 28, 4, 2, 0, 0, 0, 0, 1, 0, 1775, 56, 7, 2, 1, 0, 0, 0, 0, 1, 0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1
OFFSET
1,8
COMMENTS
T(1,0) = 1 by convention.
Sum_{i=2..n-1} T(n,i) = A001678(n+1) for n>1.
LINKS
EXAMPLE
The A000081(5) = 9 rooted trees with 5 nodes sorted by minimal outdegree of inner nodes 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--- : ---4--- :
Thus row 5 = [0, 7, 1, 0, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 3, 0, 1;
0, 7, 1, 0, 1;
0, 17, 2, 0, 0, 1;
0, 42, 4, 1, 0, 0, 1;
0, 105, 7, 2, 0, 0, 0, 1;
0, 267, 15, 2, 1, 0, 0, 0, 1;
0, 684, 28, 4, 2, 0, 0, 0, 0, 1;
0, 1775, 56, 7, 2, 1, 0, 0, 0, 0, 1;
0, 4639, 110, 12, 2, 2, 0, 0, 0, 0, 0, 1;
MAPLE
b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
1, 0), `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
b(n-i*j, i-1, max(0, t-j), k), j=0..n/i)))
end:
T:= (n, k)-> b(n-1$2, k$2) -`if`(n=1 and 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, If[t == 0 || t == k, 1, 0], If[i<1, 0, Sum[Binomial[b[i-1, i-1, k, k]+j-1, j]* b[n-i*j, i-1, Max[0, t-j], k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[n == 1 && 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, Jan 08 2015, translated from Maple *)
CROSSREFS
Row sums give A000081.
Cf. A001678, A244372, A244530 (ordered unlabeled rooted trees).
Sequence in context: A262964 A135481 A180049 * A238123 A128311 A334076
KEYWORD
nonn,tabl
AUTHOR
Joerg Arndt and Alois P. Heinz, Jun 28 2014
STATUS
approved