Count the Symmetric Binary Trees

Let $C_n = \frac{1}{n+1} \binom{2n}{n}$ be the $n$ -th Catalan number . We claim that the number of symmetric binary trees of $2n+1$ nodes is $C_n$ .

First, we need one node as the root. Since the tree is symmetric, constructing the left subtree completely decides the right subtree; just mirror the whole thing. If the left subtree has $k$ nodes, then so as the right subtree, so the total number of nodes is $2k+1$ . Thus we need $k = n$ .

Now, whatever the left subtree is gives exactly one symmetric tree. So all we need to do is to compute the number of binary trees of $n$ nodes; this number is equal to the number of symmetric binary trees of $2n+1$ nodes. This number is $C_n$ , as proved in the wiki article linked above.

The problem asks for $n = 5$ , thus the answer is $C_5 = \frac{1}{6} \binom{10}{5} = \boxed{42}$ .