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

1, 1, 3, 4, 9, 13, 26, 42, 81, 138, 262, 467, 885, 1620, 3076, 5743, 10953, 20721, 39714, 75873, 146139, 281259, 544230, 1053552, 2047147, 3981790, 7766018, 15165195, 29676887, 58148087, 114129308, 224278526, 441368913, 869583189, 1715365690, 3387344619

Offset

3,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 = 3..1000

Formula

a(n) ~ c * d^n / n^(3/2), where d = 2.0554620926822709065075792..., c = 1.0209036918758320315742... . - Vaclav Kotesovec, Aug 27 2014

Example

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

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:
a:= n-> b(n-1$2, 2$2):
seq(a(n), n=3..50);

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] }]];
a[n_] := b[n-1, n-1, 2, 2];
a /@ Range[3, 50] (* Jean-François Alcover, Dec 27 2020, after Alois P. Heinz *)

Crossrefs

Column k=2 of A244657.

Sequence in context: A250111 A079284 A000624 * A232801 A357238 A056514

Adjacent sequences: A244700 A244701 A244702 * A244704 A244705 A244706

Keyword

nonn

Author

Alois P. Heinz, Jul 04 2014

Status

approved