How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$

Question

I am basically trying to solve the following question:

Given a set $P = \{\{1\},\{2\},\dots,\{n\}\}$ of $n$ sets of elements, our aim is to merge these elements into one set.

At each step, sets can be only merged pairwise.

How many different ways can this merge happen?

For instance, given $P = \{\{a\},\{b\},\{c\},\{d\}\}$:

After the first step we can end up with three different combinations: \begin{array}{c} P_{11} = \{\{a,b\}, \{c,d\}\}\\ P_{12} = \{\{a,c\}, \{b,d\}\}\\ P_{13} = \{\{a,d\}, \{b,c\}\}\\ \end{array}

And all the sets will be merged after the second step: \begin{array}{c} P_{2} = \{\{a,b,c,d\}\}\\ \end{array} All the examples I could find about recurrences is summation of two recurring functions such as

$T(n) = T(n) + T(n/2) + \Theta(n)$

However, I want to solve a recurrence relation where recurring function is multiplied by itself:

$T(n) = T(n^2-n)*T(n/2)$

I am not sure that I write the recursion correct but this is what I want:

\begin{array}{l} n\\ \dfrac{n(n-1)}{2}*\dfrac{n}{2}\\ \dfrac{n(n-1)}{2}*\dfrac{n}{2}*\dfrac{\frac{n}{2}\left(\frac{n}{2}-1\right)}{2}*\dfrac{n}{4}\\ \end{array}

At first sight, the number of nodes in the recursion tree grows like $O(n) \rightarrow O(n^3) \rightarrow O(n^6) \dots$ at each level, which can be formulated as $n^{2k}$.

Since the size of the problem is reduced by a factor of 2, we have $\log n$ depth in the recursion tree. Therefore, $n^{2k} = \log n$ and $2k = \log_{n}\log n$ which does not seem a reasonable size.

Where am I mistaken?

Answer 1

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 < 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.