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.
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
Examples
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;
Links
- Alois P. Heinz, Rows n = 1..141, flattened
Crossrefs
Programs
-
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 *)
Comments