techInterview Discussion

Well, it seems that merging companies is now in vogue, so here's my contribution.

How many distinct patterns are there of N companies merging, two at a time (resulting in a single company), where the order is not significant?  More formally, a merger pattern is the set of all companies (original, intermediate and final) formed in the process.  Since it is defined as a set, there is no order, even though the merging process is a sequence.

For example, if A and B merge, then C and D merge, and then AB merges with CD, the corresponding pattern would be { A, B, C, D, AB, CD, ABCD }.
The same pattern would emerge if C and D merged first, then A and B, and finally AB and CD.  However, a different pattern, namely { A, B, C, D, AB, ABC, ABCD } emerges when A and B merge, then AB and C, and then ABC and D.

There are

C_{n-1} n! = (2n-2)!/(n-1)!

fully parenthesized expressions on n distinct variables (the sequence C is the Catalan numbers) and a symmetry group of order 2^{n-1} that acts freely, for a total of

(2n-3)!!

merges.

How did you get from C(n-1)n!/2^{n-1} to (2n-3)!! ?

Ah.  Wasn't familiar the double factorial notation.