# How many ways to merge N companies into one big company: Bell or Catalan?

There's a famous interview question variously credited to Microsoft, Google and Yahoo:

Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are there to merge them?

Assuming you can merge as many companies as you like in a single step, I thought this boils down to "find the number of partitions of a set with N elements", in which case the answer is the Bell number $B_{n}$. This can be computed with this handy recursion cribbed shamelessly from Wikipedia:

$B_{n+1}=\sum_{k=0}^{n}{{n \choose k}B_k}$

$1, 1, 2, 5, 15, 52, 203...$

And you have to substract one since you're already starting from one of the possible sets: $B_{2}=2$, but there's only one way to combine A and B into AB.

However, there are a lot of sources on the net which claim that the correct solution is the Catalan number:

$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\mbox{ for }n\ge 0$

$1, 1, 2, 5, 14, 42, 132...$

Which is correct, and why? Or are they both correct depending on the assumptions you make about the somewhat vague problem statement?

-
Reading your question, I only see one solution: There's only one way to do it, and that's to put them all together. There's definitely something vague about the problem formulation. – Raskolnikov Oct 15 '12 at 10:32
I think this is ambiguous as well. Does "eventually" mean that you can take multiple steps? If so, at least how many companies do I have to merge in each step? I could simply choose not to do anything for an arbitrary number of steps, giving me an answer of $\infty$. – wj32 Oct 15 '12 at 10:43
Yes, my understanding is that you can take multiple steps, and you can merge as many as you like (including all) in a single step. So for N=3, the valid ways to merge them would be A,B,C -> (AB,C | AC,B | BC,A) -> ABC plus A,B,C -> ABC, for a total of 4 paths. – jpatokal Oct 15 '12 at 10:48
Given the explanation, it would seem that the number of partitions of a set does not give the right answer: it just counts the possibilities do merge any of them into a partition on the first step (including the possibility to keep them singletons), and then merge them all to one company in one fell sweep on the second step (including the possibility that they were already made into one company in the first step). – Marc van Leeuwen Oct 15 '12 at 11:38
Note that $4$ (apparently the answer for $N=3$) is neither a Bell number nor a Catalan number... – Marc van Leeuwen Oct 15 '12 at 11:44

My first interpretation is that a way of merging the $n$ companies corresponds to a sequence $\langle P_k:k=0,\dots m\rangle$ such that:

1. $P_0=\{1,\dots,n\}$;
2. $P_{k+1}$ is a partition of $P_k$ for $k=0,\dots,m-1$;
3. $|P_{k+1}|<|P_k|$ for $k=0,\dots,m-1$; and
4. $|P_m|=1$.

These sequences evidently correspond to rooted trees with $n$ labelled leaves. The immediate correspondence between the partition sequences and the trees allows the latter to have internal vertices with only one child, so that each $P_k$ corresponds to a level of the tree, and requires that the leaves all be on the same level, but we can clearly collapse the non-branching branches and instead count rooted trees with $n$ labelled leaves in which every internal vertex has at least two children.

Let $M(n)$ be the number of such partition sequences or trees. Clearly $M(1)=M(2)=1$, and $M(3)=\binom32+\binom33=4$.

Edit2: In fact the correct numbers are $1,1,4,26,236,2752$, OEIS A000311, the number of phylogenetic trees with $n$ vertices. $M(n)$ is the sum over all partitions $\sum_{i=1}^mn_ip_i=n$, where the $p_i$ are distinct positive integers, of the terms $$\frac{n!}{\prod_{i=1}^mp_i!^{n_i}n_i!}\cdot\prod_{i=1}^mM(p_i)^{n_i}=\frac{n!}{n_1!n_2!\dots n_m!}\prod_{i=1}^m\left(\frac{M(p_i)}{p_i!}\right)^{n_i}\;;$$ verifying this is a matter of fairly straightforward counting. OEIS gives the much nicer recurrence $$M(n+1)=(n+2)M(n)+2\sum_{k=2}^{n-1}\binom{n}kM(k)M(n-k+1)\;,$$ among several others.

Restricting to binary mergers yields the sequence $1,1,3,15,105$, which appears to be A001147, $(2n-3)!!$. The OEIS entry says that $a_n$ is the number of distinct products of $n=1$ variables with commutative, non-associative multiplication, and those would appear to correspond to the binary merger trees.

-
I suspect you are missing a large number: what about $(ab)c(de)$? i.e. merge $a$ and $b$, merge $d$ and $e$ aand then merge the three remianing? – Henry Oct 15 '12 at 12:45
@Henry: You’re right: I seem to have shifted to binary mergers part way through. That’s may be a good thing, since I really didn’t like the numbers that I was getting. – Brian M. Scott Oct 15 '12 at 12:49
Could someone please explain the first (n+2)*M(n) term in second equation of Edit2? M(n+1) = (n+2)M(n) + ... Shouldn't it be simply M(n) as it corrresponds to the case when firstly all n elements are merged together then the n+1th element is merged in possibly only one way. – srbh.kmr Nov 15 '12 at 13:58
@srbh.kmr: That’s simply taken from the OEIS entry; I didn’t try to analyze it, though I did have to adjust the indices to match my starting point. – Brian M. Scott Nov 15 '12 at 21:01

So turns out the question probably originates from Steven Skiena's The Algorithms Design Manual, whose answer wiki gives the solution as:

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

Unlike Christian's answer, this assumes "pairwise" (only two companies at a time) non-simultaneous mergers.

-

According to jpatokal's comment there are two notions:

Given a set $S$ of $n\geq1$ distinguishable objects a merger consists in selecting an arbitrary $k$-subset $A\subset S$, $2\leq k\leq n$, and forming the new set $S':=(S\setminus A)\cup\{A\}$ containing $n-k+1<n$ elements.

Given a finite set $S_0$ a merger history is a sequence of mergers $S_0\to S_1\to S_2\to \ldots\to S_r$ whereby $|S_r|=1$. (We do not consider the case that at the same instant two disjoint subsets $A_1$, $A_2\subset S$ are merged into two different amalgams $\{A_1\}, \ \{A_2\}$.)

The problem is to determine the number of possible merger histories for a starting set $S$ containing $n\geq1$ elements. Denote this number by $H(n)$. Then $H(1)=H(2)=1$, and the $H(n)$ satisfy the following recursion:

$$H(n)=\sum_{k=2}^n {n\choose k} H(n-k+1)\qquad (n\geq3)\ .$$

The first few values are $$1,1,4,29,336,5687,132294,4047969,157601068, \ldots\quad\ .$$ OEIS does not list such a sequence.

-
Interesting, but Brian M. Scott's answer, particularly the parallel to phylogenetic trees, seems more convincing. Can you spot a flaw in his argument... or in yours? – jpatokal Oct 16 '12 at 11:15
@jpatokal: The difference is that in Brian M. Scott's setup there can be simultaneous mergers of disjoint subsets (that's why he is talking about partitions), whereas in my setup mergers happen one at a time. – Christian Blatter Oct 16 '12 at 12:59