cp's OEIS Frontend

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

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