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

0, 1, 2, 2, 3, 8, 14, 20, 35, 64, 122, 260, 586, 1296, 2708, 5400, 10468, 19888, 37580, 71960, 140612, 279264, 560544, 1133760, 2310316, 4750368, 9876264, 20788880, 44282696, 95241664, 206150208, 447470464, 970862029, 2100029344

Offset: 0

Author

Frank Ruskey

Keywords

• nonn

Comments

Are a(2) = a(3) = 2 and a(4) = 3 the only primes in this sequence? - Jonathan Vos Post, Jun 17 2005

Links

• 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. A001137, A014535, A037026.

Programs

Maple

spec := [B, {B=Union(Z, Subst(M, B)), M=Union(Prod(Z,Z),Prod(Z,Z,Z,Z))} ]; [seq(combstruct[count](spec, size=2*n), n=0..40)]; # N. J. A. Sloane, Dec 21 2000. Compare A014535, A037026.
a := proc(n) option remember; if n < 3 then return n fi; add(binomial(2*k, n-2*k)*a(k), k = iquo(n,4)..iquo(n,2)) end:
seq(a(n), n=0..33); # Peter Luschny, Oct 23 2019

Mathematica

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

PARI

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

Formula

a(1) = 1, a(2) = 2 and for n>2: a(n) = Sum_[n/4 <= m <= n/2] binomial(2m,n-2m)*a(m), John Moon, as quoted in Ruskey. - Jonathan Vos Post, Jun 17 2005.

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