How many Red-Black trees?

Given $n$, how many red-black trees exist with $n$ nodes?

Can you give an algorithm to compute that value? Hopefully polynomial in $n$.

Note: I haven't tried solving this problem myself, so it is a little open ended and don't expect to see a solution!

[Possible Solution]