I'm trying to find a recurrence relation for how many full binary trees there are with n nodes. However, once I get to n = 11, it's there's a lot of trees to keep track of. I've written out the cases for $$n \in [1,9] $$ where n is odd but I can't figure out the pattern.
At n=1, I have 1.
n = 3, I have 1
n = 5 : 2 /// n = 7 : 5 /// n = 9 : 14
Basically I took the leaves from the previous nth tree I created and added 2 nodes to each leaf for all possible full binary trees then got rid of duplicates. I.e for n = 7, I took leaves from n = 5, which is 3 and added 2 nodes to each leaf from all the fbts possible when n = 5 (which is 2) and so I end up with 6 fbts, but there's 1 duplicate so I subtract 1 to end up with 5 distinct fbts.
Any help on figuring out the pattern or atleast how many distinct fbts with n nodes?
See: Catalan Numbers
You can use the number $C_n$ to describe the number of binary trees with $n+1$ leaf nodes, that is, $2n + 1$ nodes total.
EDIT: Here's the full reasoning.
We have $C_0 = 1$, and suppose we have $C_0, \ldots, C_n$, the number of full binary trees with up to $n + 1$ leaf nodes, and we want $C_{n+1}$. Given a root node, we just need $k$ leaf nodes on one side, and $n + 1 - k$ leaf nodes on the other, for all values of $k$ from $1$ to $n$. Since there's $C_k$ ways of choosing trees for one side, and $C_{n+1-k}$ on the other, there's a total of $C_k \cdot C_{n -k}$ trees for a given $k$.
Solve for this recurrence:
$$ C_0 = 1, \qquad C_{n+1} = \sum_{k=0}^{n}C_kC_{n-k}$$
The solution is the Catalan Numbers $C_n = \frac{(2n)!}{(n+1)!n!}$.