4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Something is wrong with your recurrence: it never terminates (as $n^2-n$ is larger than $n$). Double-check your recurrence, as it looks very suspicious. If you're absolutely sure it is correct, try writing $T(n^2-n)=T(n)/T(n/2)$ and then work from there, but I find it hard to believe that's going to give you the right answer. $\endgroup$
    – D.W. ♦
    Nov 24, 2015 at 6:24
  • $\begingroup$ Regarding your original problem, I recomment you find other ways to represent the quantity you are looking for $\endgroup$
    – Raphael ♦
    Nov 24, 2015 at 8:33

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.