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

Author

Alois P. Heinz, Jul 12 2014

Keywords

• nonn

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.

Examples

			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                          :
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 4..1000

Crossrefs

Column k=2 of A245120.

Programs

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 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 *)

Formula

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