Denote when $k>2m$ $$f\_k(2m)=\sum\_{i=1,i\geq1}^m\binom{2m}{i}f\_k(i)f\_k(2m-i)$$
$$f\_k(2m+1)=\sum\_{i=1,i\geq1}^m\binom{2m+1}{i}f\_k(i)f\_k(2m+1-i)$$


$$f\_k(0)=1.$$
$$f\_k(1)=k.$$


1. What is a good bound for $f\_{2^{n+1}}(2^{n})$?
2. How does it compare with $\binom{2^{n+1}}{2^n}$? Is $f\_{2^{n+1}}(2^{n})>\binom{2^{n+1}}{2^n}$?



Is there a good bound for this double exponential recursion?
For brevity, rewrite the recursion as$$f\_k(n)=\sum\_{1\leqslant i\leqslant\frac n2}\binom nif\_k(i)f\_k(n-i).$$Now divide it by $n!k^n$ and rewrite like this:$$\frac{f\_k(n)}{n!k^n}=\frac1{n!}\sum\_{1\leqslant i\leqslant\frac n2}\binom nii!(n-i)!\frac{f\_k(i)}{i!k^i}\frac{f\_k(n-i)}{(n-i)!k^{n-i}}.$$
It follows that for$$g\_k(n):=\frac{f\_k(n)}{n!k^n}$$we get$$g\_k(n)=\sum\_{1\leqslant i\leqslant\frac n2}g\_k(i)g\_k(n-i),$$and $g\_k(1)=1$ (in particular $g\_k(n)$ does not depend on $k$).


This is the recursion for [A000992](http://oeis.org/A000992) (number of (unlabeled, rooted) ordered trees on $n-1$ vertices in which all outdegrees are $\leqslant2$ and, for each vertex of outdegree $2$, the sizes of its two subtrees are weakly increasing left to right ($n\geqslant2$)). That page contains some information about these numbers.


