2.53

Some incorrect answers were reached. These have been moved to the discussion, with explanation of where the argument goes wrong.

The correct answer: Assuming pairwise merges (no k-way merges) we have [math]\displaystyle{ n-1 }[/math] merge stages where each set of companies is generated from the previous stage (the merged pair being one company). If we characterize each complete merge as different if two companies merge at different stages then we are looking at combinations. In the first stage we have [math]\displaystyle{ \binom{n}{2} }[/math] ways to choose a merge pair and a new set for the next stage. Thus, we have the Cartesian product of each stage set and we can calculate the size as:

[math]\displaystyle{ \prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}} }[/math]

Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. [math]\displaystyle{ n=3 }[/math] where our formula indicates there are three different possible merges):

{a,b,c} -> {ab, c} -> {abc}
        -> {a, bc} -> {abc}
        -> {ac, b} -> {abc}

And, since we have three paths we can say that's three merges -- this counts a merge step as the same if it results in the same set of companies going on to the next stage. But, instead if we count the actual merge operations:

{a, b, c} -> {a+b, c}, {(a+b) + c}, {a, b+c}, {a + (b+c)},
             {a+c, b}, {(a+c) + b}

then we need to change the denominator in our previous formula:

[math]\displaystyle{ 2^{n-1} \rightarrow 2^{n-2} }[/math] to get six steps.

__________________________________________________________________________________

Solution above is correct given its assumptions but this problem can be more interesting. According to the examples above, {a, b, c, d} -> {ab, c, d} -> {ab, cd} is different from {a, b, c, d} -> {a, b, cd} -> {ab, cd}. I would argue that the two paths are the same. I would define two path to be the same if each employee of each company sees their own company merging sequentially with the same companies in both paths. In the example above, the employees of company c see that they merged with d and then with ab in both paths to full merger. Think about this. It is kinda complicated. So if we write down an individual merge sequence for each of the companies, then two paths are equal if all of their individual merge sequences are equal. Now how to calculate the number of paths?

Pick company number N and assume it's IBM. Now consider IBM's individual merging path. It could be {IBM} -> {IBM, DELL}, or {IBM} -> {IBM, DELL, Apple} or {IBM} -> {IBM, Google, Netflix, Amazon}. The aspect I'm emphasizing here is that in its first merger, IBM could merge with 1 to n-1 many companies. We can compute all of the paths by adding up these scenarios. So let's say IBM will be merging with i companies in its first merger. How many paths would we have now. Let's define f(n) to be the number of merger paths for n companies (the number we are trying to find). Then there are [math]\displaystyle{ {n-1 \choose i} }[/math] ways to pick the i companies IBM will be merging with. Those companies have to merge only with each other before they merge with IBM and there are f(i) ways to do that. After IBM has merge with the i companies, then we have n-i companies left to merge (counting the big set of i companies as one company), and there are f(n-i) ways to do that. So we get the recursive equation: [math]\displaystyle{ f(n) = \sum^{n-1}_{i=1} f(i)f(n-i){n-1 \choose i} }[/math].

Back to Chapter 2