An extended Binary Tree satisfying the following conditions:

- 1. Every node has two Children, each colored either red or black.
- 2. Every Leaf node is colored black.
- 3. Every red node has both of its Children colored black.
- 4. Every path from the Root to a Leaf contains the same number (the ``black-height'') of black nodes.

Let be the Generating Function for the number of red-black trees of black-height indexed by the number of
Leaves. Then

(1) |

(2) |

(3) |

**References**

Beyer, R. ``Symmetric Binary -Trees: Data Structures and Maintenance Algorithms.'' *Acta Informat.* **1**, 290-306, 1972.

Rivest, R. L.; Leiserson, C. E.; and Cormen, R. H. *Introduction to Algorithms.* New York: McGraw-Hill, 1990.

Ruskey, F. ``Information on Red-Black Trees.'' http://sue.csc.uvic.ca/~cos/inf/tree/RedBlackTree.html.

Sloane, N. J. A. Sequences A001131, A001137, and A001138 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

© 1996-9

1999-05-25