A001137 Number of black-rooted red-black trees with n internal nodes.

1, 2, 2, 4, 8, 16, 33, 56, 90, 164, 330, 688, 1440, 3008, 6291, 13168, 27604, 57896, 120730, 248312, 501464, 995664, 1954582, 3821328, 7495996, 14848472, 29815976, 60741680, 125363472, 261452256, 549461078, 1160693056, 2459679936, 5221717888

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..900

F. Ruskey, Information on Red-Black Trees

Eric Weisstein's World of Mathematics, Red-Black Tree.

Index entries for sequences related to rooted trees

Formula

G.f. satisfies: A(x) = x*(1+x)^2*(1 + A((x+x^2)^2)). - Paul D. Hanna, Jun 14 2012

Mathematica

m = 35; A[_] = 0;
Do[A[x_] = x*(1 + x)^2*(1 + A[(x + x^2)^2]) + O[x]^m // Normal, {m}];
CoefficientList[A[x]/x, x] (* Jean-François Alcover, Oct 19 2019 *)

Prog

(PARI) {a(n)=local(A=x); for(i=1, n, A=x*(1+x)^2*(1 + subst(A, x, (x+x^2)^2+x*O(x^n)))); polcoeff(A, n)} \\ Paul D. Hanna, Jun 14 2012

Crossrefs

Cf. A001131.

Sequence in context: A318187 A217931 A090129 * A123593 A122748 A108774

Adjacent sequences: A001134 A001135 A001136 * A001138 A001139 A001140

Keyword

nonn

Author

Frank Ruskey

Extensions

More terms from Sean A. Irvine, Mar 08 2012

Status

approved