3. Every red node has both of its children colored black.

4. Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.

Let
be the number of internal nodes of a red-black tree. Then the number of red-black
trees for ,
2, ... is 2, 2, 3, 8, 14, 20, 35, 64, 122, ... (OEIS A001131).
The number of trees with black roots and red roots are given by OEIS A001137
and OEIS A001138, respectively.

Let
be the generating function for the number
of red-black trees of black-height indexed by the number of tree leaves.
Then

(1)

where .
If is the generating
function for the number of red-black trees, then

(2)

(Ruskey). Let
be the number of red-black trees with tree leaves, the number of red-rooted trees, and the number of black-rooted trees. All three of the quantities
satisfy the recurrence relation