How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$
If you have a recurrence involving only multiplication, take the logarithm:
$$
\log T(n) = \log T(n^2-n) + \log T(n/2).
$$
This converts it into an additive recursion. In your case this is not really a recursion since it defines $T(n^2-n)$ in terms of $T(m)$ for $m &lt; n^2-n$, but not every integer is of the form $n^2-n$.

Regarding your original question, try to relate it somehow to binary trees, which are known to be counted by the Catalan numbers.