How many binary trees are there, if the leafs's order from left to right is fixed?

Question

Let's represent the tree via list.

If the number of the leafs is two, A and B. Then there is only one tree (A B).

If the number of the leafs is three, A, B and C. Then there are two trees ((A B) C) and (A (B C)).

So if there are N leafs, how many trees are there?

Answer 1

Let the number of binary trees with N leaves be T(N).

We have T(1) = T(2) = 1, as can be immediately seen, and for N > 2 we can split at the root, obtaining two subtrees with fewer leaves. Or, equivalently, we can assemble a binary tree with N leaves from two non-empty binary trees with k and N-k leaves respectively. The condition that both subtrees are non-empty translates to 1 <= k <= N-1. So we have the recursion

      N-1
T(N) = ∑  T(k) * T(N-k)
      k=1

If the recursion is not yet known, it is not difficult to compute the first few values

1,1,2,5,14,42,132,429,1430,4862,16796

and google them. One finds that these are the Catalan numbers,

C(n) = (2*n)! / (n! * (n+1)!)

offset by one, so

T(N) = C(N-1)

which can be computed much faster than the recursion.