A052302 Number of Greg trees with n black nodes.

1, 1, 1, 2, 5, 12, 37, 116, 412, 1526, 5995, 24284, 101619, 434402, 1893983, 8385952, 37637803, 170871486, 783611214, 3625508762, 16906577279, 79395295122, 375217952457, 1783447124452, 8521191260092, 40907997006020, 197248252895597, 954915026282162

Offset: 0

Author

Christian G. Bower, Nov 15 1999

Keywords

• nonn

Comments

A Greg tree can be described as a tree with 2-colored nodes where only the black nodes are counted and the white nodes are of degree at least 3.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for sequences related to trees

Crossrefs

Cf. A005263, A005264, A048159, A048160, A052300, A052301, A052303.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(g(i)+j-1, j)*b(n-i*j, i-1), j=0..n/i)))
    end:
g:= n-> `if`(n<1, 0, b(n-1$2)+b(n, n-1)):
a:= n-> `if`(n=0, 1, g(n)-add(g(j)*g(n-j), j=0..n)):
seq(a(n), n=0..40);  # Alois P. Heinz, Jun 22 2018

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0,
    Sum[Binomial[g[i] + j - 1, j]*b[n - i*j, i - 1], {j, 0, n/i}]]];
g[n_] := If[n < 1, 0, b[n - 1, n - 1] + b[n, n - 1]];
a[n_] := If[n == 0, 1, g[n] - Sum[g[j]*g[n - j], {j, 0, n}]];
a /@ Range[0, 40] (* Jean-François Alcover, Jun 11 2021, after Alois P. Heinz *)

Formula

G.f.: 1 + B(x) - B(x)^2 where B(x) is g.f. of A052300.