A245121 Number of n-node rooted identity trees with thinning limbs and root outdegree (branching factor) 2.

1, 1, 3, 4, 8, 12, 22, 36, 63, 107, 188, 327, 578, 1020, 1820, 3248, 5839, 10511, 19022, 34484, 62755, 114421, 209234, 383327, 703901, 1294822, 2386376, 4405083, 8144701, 15080416, 27961728, 51912054, 96496481, 179577543, 334558479, 623936240, 1164765120

Offset

4,3

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, Table of n, a(n) for n = 4..1000

Formula

a(n) ~ c * d^n / n^(3/2), where d = 1.938950593419038561279875... and c = 0.929315638487153276953929... . - Vaclav Kotesovec, Jul 13 2014

Example

a(7) = 4:
:   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                          :

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, add(binomial(A(i, min(i-1, h)), 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:
a:= n-> b(n-1$2, 2$2):
seq(a(n), n=4..45);

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, Sum[Binomial[A[i, Min[i - 1, h]], 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] } ] ];
a[n_] := b[n-1, n-1, 2, 2];
a /@ Range[4, 45] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

Crossrefs

Column k=2 of A245120.

Sequence in context: A173534 A074331 A052952 * A329730 A153339 A275989

Adjacent sequences: A245118 A245119 A245120 * A245122 A245123 A245124

Keyword

nonn

Author

Alois P. Heinz, Jul 12 2014

Status

approved