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,4

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

Formula

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

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

Crossrefs

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

Sequence in context: A267399 A267400 A363064 * A280275 A009598 A355861

Adjacent sequences: A052299 A052300 A052301 * A052303 A052304 A052305

Keyword

nonn

Author

Christian G. Bower, Nov 15 1999

Status

approved