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

Comments

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

Links

Table of n, a(n) for n=0..33.

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

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

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

Prog

(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

Crossrefs

Cf. A001137, A014535, A037026.

Sequence in context: A159789 A153932 A158763 * A019177 A153941 A184844

Adjacent sequences: A001128 A001129 A001130 * A001132 A001133 A001134

Keyword

nonn

Author

Frank Ruskey

Status

approved