Use the analytic method. Your class is a root connected to a non-empty set of trees, or a leaf. Use $\mathcal{Z}$ (and $z$) for inner nodes, $\mathcal{Y}$ (and $y$) for leaves; use $\mathcal{E}$ for the class with one empty object:
$$
\mathcal{T}
= \mathcal{Z} \star (\mathfrak{S}(\mathcal{T}) \smallsetminus \mathcal{E})
+ \mathcal{Z} \mathcal{Y}
$$
This translates to:
$$
T(z, y) = z (e^{T(z, y)} - 1) + z y
$$
Just need to get $T(z, y)$ (or the coefficients) out of this...
The number of ways to fully parenthesize a string of $n$ letters, $C_{n-1}$, obeys the following recurrence:
$$
C_{n-1} = \sum_{i=1}^{n-1}C_{i-1}C_{n-i-1}
$$
To see this, consider the two "shallowest" groups in the parenthesization. Namely, ignoring the leftmost (
and the rightmost )
, look at the parenthesis matching the leftmost (
. This will surround the first $i$ letters in the string, which can be further paranthesized in $C_{i-1}$ ways, while the latter $n-i$ letters can be parenthesized in $C_{n-i-1}$ ways. For example when $n=5$, the $*$ illustrates all of the break points:
(1 * (2 (3 (4 5)))) C(0) * C(4) strings where the break point
(1 * (2 ((3 4) 5))) is after i=1
(1 * ((2 3) (4 5)))
(1 * ((2 (3 4)) 5))
(1 * (((2 3) 4) 5))
((1 2) * (3 (4 5))) C(1) * C(2) strings where the break point
((1 2) * ((3 4) 5)) is after i=2
((1 (2 3)) * (4 5)) C(2) * C(1) strings where the break point
(((1 2) 3) * (4 5)) is after i=3
((1 (2 (3 4))) * 5) C(4) * C(0) strings where the break point
((1 ((2 3) 4)) * 5) is after i=4
(((1 2) (3 4)) * 5)
(((1 (2 3)) 4) * 5)
((((1 2) 3) 4) * 5)
This recurrence gives you a quickly computable bijection from the first $C_{n-1}$ non-negative integers to binary trees. You are given an integer $k$ for which $0\le k\le C_{n-1}-1$. Compute the partial sums
$$
\sum_{i=1}^{s-1} C_{i-1}C_{n-i-1}
$$
to find the largest number $s\ge 1$ for which that partial sum is at most $k$. Then, insert parentheses into the list of numbers (1 2 3 ... n)
as follows:
((1 2 ... s) (s+1 s+2 ... n))
If $s=1$, you can omit the parentheses around (1)
, and similarly when $s=n-1$ around (n)
.
Then, letting $$e=k - \Big(\sum_{i=1}^{s-1}C_{i-1}C_{n-i-1}\Big),$$ and letting \begin{align}k_1&=e\pmod {C_{s-1}}\\k_2&=\lfloor e/C_{s-1}\rfloor,\end{align} you will have $0\le k_1\le C_{s-1}-1$ and $0\le k_2\le C_{n-s-1}-1$, and you can recursively apply the bijections for $k_1$ to the list (1 2 ... s)
and for $k_2$ to the list (s+1 s+2 ... n)
.
Edit: There was a "bug" in my bijection which I just fixed. You can test that it works here.
Edit2: I just fixed another off-by-one error.
Best Answer
Since $B(z)$ is an exponential generating function $B(z) = \sum_n b_n \frac{z^n}{n!}$, and not $\sum_n b_n z^n$.
With correct definition the series expansion for $B(z)$ should read:
$$ B(z) \sim z+\frac{z^2}{2}+\frac{z^3}{2}+\frac{5 z^4}{8}+\frac{7 z^5}{8}+\frac{21 z^6}{16}+\frac{33 z^7}{16}+O\left(z^8\right) $$ and this satisfies the recurrence equation: