|
| |
|
|
A001131
|
|
Number of red-black rooted trees with n-1 internal nodes.
|
|
0
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Are a(2) = a(3) = 2 and a(4) = 3 the only primes in this sequence? - Jonathan Vos Post (jvospost3(AT)gmail.com), Jun 17 2005
|
|
|
LINKS
| F. Ruskey, Information on Red-Black Trees
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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][(2m)C(n-2m) * a(m)} according to John Moon, as cited in Ruskey. - Jonathan Vos Post (jvospost3(AT)gmail.com), Jun 17 2005
|
|
|
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)]; # from N. J. A. Sloane (njas(AT)research.att.com), Dec 21, 2000. Compare A014535, A037026.
|
|
|
CROSSREFS
| Sequence in context: A159789 A153932 A158763 * A019177 A153941 A184844
Adjacent sequences: A001128 A001129 A001130 * A001132 A001133 A001134
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Frank Ruskey (ruskey(AT)cs.uvic.ca)
|
| |
|
|
