For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.
An excellent reference is Analytic Combinatorics by the late <PERSON> and <PERSON>. It is available from the link above.
The late <PERSON>’s book generatingfunctionology is another free source.
And of course Concrete Mathematics by GKP is a treasure trove.
For binary trees it goes like this: First you need a clear definition of the tree.
A binary tree is a rooted tree in which every non-leaf node has degree 2 exactly.
Next we have to agree what we want to call the size of a tree.
On the left all nodes are equal. In the middle we distinguish the leaves and non-leaves. On the right we have a pruned binary tree where the leaves have been removed. Notice that it has unary branches of two types (left and right)!
Now we have to derive a description of how these combinatorial objects are built. 433
In the case of binary trees a recursive decomposition is possible.
Let $\mathcal{A}$ be the set of all binary trees of the first type then symbolically we have:
It reads as: “An object of the class of binary trees is either a node or a node followed by two binary trees.” This can be written as equation of sets:
$$\mathcal{A}={\bullet}\cup\bigl({\bullet}\times\mathcal{A}\times\mathcal{A}\bigr)$$
By introducing the generating function $A(z)$ that enumerates this class of combinatorial objects we can translate the set equation into an equation involving the generating function.
$$A(z)=z+zA^2(z)$$
Our choice of treating all nodes equally and taking the number of nodes in the tree as notion of its size is expressed by “marking” the nodes with the variable $z$.
We can now solve the quadratic equation $zA^2(z)-A(z)+z=0$ for $A(z)$ and get, as usual, two solutions, the explicit closed form of the generating function:
$$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$$
Now we simply need <PERSON>’s (generalized) Binomial Theorem:
$$(1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k$$
with $a=1/2$ and $x=-4z^2$ to expand the closed form of the generating function back into a power series. We do this because, the coefficient at $z^n$ is just the number of combinatorial objects of size $n$, typically written as $[z^n]A(z)$. But here our notion of “the size” of the tree forces us to look for the coefficient at $z^{2n+1}$. After a little bit of juggling with binomials and factorials we get:
$$[z^{2n+1}]A(z)=\frac{1}{n+1}\binom{2n}{n}.$$
If we start with the second notion of the size the recursive decomposition is:
We get a different class of combinatorial objects $\mathcal{B}$. It reads: “An object of the class of binary trees is either a leaf or a interal node followed by two binary trees.”
We can use the same approach and turn $\mathcal{B}={\square}\cup\bigl({\bullet}\times\mathcal{B}\times\mathcal{B}\bigr)$ into $\mathcal{B}=1+zB^2(z)$. Only this time the variable $z$ only marks the internal nodes, not the leaves, because the definition “the size“ is different here. We get a different generating function as well:
$$B(z)=\frac{1-\sqrt{1-4z}}{2z}$$
Extracting the coefficient yields
$$[z^n]B(z)=\frac{1}{n+1}\binom{2n}{n}. 743