TADM2E 2.49

With 2 companies {a,b}, there's only one way to merge: [ab]

With three companies {a,b,c}, we need to find the number of ways that the three companies can become two companies, and for every one of those possibilities, the two remaining companies can be reduced to one in only 1 way (because we've already solved the case of two companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b}, {bc,a}], or 3.

Now we see a pattern emerging. For n companies, the answer is $ f(n - 1) * g(n) $, where g(n) is the number of ways to reduce n companies to n - 1 companies. g(n) is the sum from 1 to n - 1 of n, which is $ n(n - 1)/2 $. Thus, the answer is $ f(n - 1) * n(n - 1)/2 $.

Another answer: Assuming pairwise merges (no k-way merges) we have $ n-1 $ 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 $ \binom{n}{2} $ 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:

$ \prod_{i=2}^{n} \frac{i(i-1)}{2} = \frac{n! (n-1)!}{2^{n-1}} $

Proof by induction follows easily as long as we agree with the counting process for first non-trivial basis (i.e. $ n=3 $ 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:

$ 2^{n-1} \rightarrow 2^{n-2} $ to get six steps.