%I #43 Oct 23 2019 12:45:59
%S 0,1,2,2,3,8,14,20,35,64,122,260,586,1296,2708,5400,10468,19888,37580,
%T 71960,140612,279264,560544,1133760,2310316,4750368,9876264,20788880,
%U 44282696,95241664,206150208,447470464,970862029,2100029344
%N Number of red-black rooted trees with n-1 internal nodes.
%C Are a(2) = a(3) = 2 and a(4) = 3 the only primes in this sequence? - _Jonathan Vos Post_, Jun 17 2005
%H F. Ruskey, <a href="http://www.theory.cs.uvic.ca/~cos/inf/tree/RedBlackTree.html">Information on Red-Black Trees</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Red-BlackTree.html">Red-Black Tree.</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F 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.
%F G.f. satisfies: A(x) = x+x^2 + A((x+x^2)^2). - _Paul D. Hanna_, Jun 14 2012
%p 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.
%p 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:
%p seq(a(n), n=0..33); # _Peter Luschny_, Oct 23 2019
%t m = 34; A[_] = 0;
%t Do[A[x_] = x + x^2 + A[(x + x^2)^2] + O[x]^m // Normal, {m}];
%t CoefficientList[A[x], x] (* _Jean-François Alcover_, Oct 23 2019 *)
%o (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
%Y Cf. A001137, A014535, A037026.
%K nonn
%O 0,3
%A _Frank Ruskey_