techInterview Discussion

A part of answers to technical interview questions.

Your host: Michael Pryor

Yet another company merging question

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.
Thursday, June 03, 2010
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


d Send private email
Thursday, June 03, 2010
How did you get from C(n-1)n!/2^{n-1} to (2n-3)!! ?
Friday, June 04, 2010
Ah.  Wasn't familiar the double factorial notation.
Friday, June 04, 2010

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz