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?