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.

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

Alois P. Heinz, Rows n = 1..141, flattened

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.

Cf. A245120, A245151.

Sequence in context: A088205 A318923 A336111 * A072024 A238010 A370772

Adjacent sequences: A244654 A244655 A244656 * A244658 A244659 A244660

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 04 2014

Status

approved