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

Author

Frank Ruskey

Keywords

• nonn

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

Crossrefs

Cf. A001131.

Programs

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

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

Formula

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

Extensions

More terms from Sean A. Irvine, Mar 08 2012