Merging _n_ companies into one

I found the following problem in the popular “The Algorithm and Design Manual” book by Skiena. I didn’t think solving puzzles would be so fun, so I’ve decided to incorporate them in the blog (until I get bored).

Preamble aside, here’s the puzzle description:

Suppose we start with n companies that eventually merge into one big company. How many different ways are there for them to merge?

At face value it immediately sounded like a combinatorics problem. The giveaway was the statement

How many different ways are there for them to merge?

I was hoping there’d no be catch and that the solution was going to be as straightforward as the description. The last thing I want to do on a Sunday afternoon is to think too hard.

Solution Link to heading

I’ll assume pairwise merging? Why? Because I’ve never heard of three-way mergers. Three-way or k-way monopoly breakups yes (looking at you Standard Oil), but I’ve never heard of it happening the other way round (if you have hit me up), so I’ll assume merging means joining two companies into one.

So we have a $ n \choose k $ problem, where $ n $ is the number of initial companies, and $ k $ is 2. Yet this merging process needs to be repeated $ n - 1 $ times to obtain one (big bad evil) corp. So the final solution will have to use the combination formula iteratively (or recursively – please don’t fight me):

$$ {n \choose 2} {n - 1 \choose 2} {n - 2 \choose 2} … {2 \choose 2}$$

That can be rewritten in iterative form as

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

Which runs in $ O(n) $ time.