# Given n distinct keys, how many different 2-3/Red-black trees can be constructed?

## Memory refresher/My understanding:

A 2-3 tree is a balanced search tree that allows two types of nodes.

1. 2-node: Normal node with two children.

• LChild < Parent and RChild > Parent
2. 3-node: Node with two parents and three children.

• Parent1 < Parent2
• LChild < Parent1, Parent1 < MChild < Parent2, RChild >Parent2

A 2-3 tree is always balanced, and grows when the root raises the height of the tree by one.

http://en.wikipedia.org/wiki/2%E2%80%933_tree

My question is then as follows, given n distinct keys, how many different 2-3 trees can one construct?

My math skills are poor, so if anyone knows how I should "math" in order to approach an answer, then that would be awesome! :)

Let `T[n]` be the number of 2-3-trees with `n` keys. We have:
• `T[n]` = sum with `k` from 1 to `n` of `T[k - 1] * T[n - k]`, because we can make a 2-node with the key `k`, with left tree with keys `1, ..., k - 1` and right tree with keys `k + 1, ..., n`. For each arrangement of the left tree, we have the arrangements of the right tree, so we must multiply the two. This counts the case when we're dealing with 2-nodes;
• `T[n]` += sum with `k` from 1 to `n` of sum with `p` from `k + 1` to `n` of `T[k - 1] * T[p - k - 1] * T[n - p]`. This counts the case when we're dealing with 3-nodes;
Base case is `T = 1`.