## Friday, February 13, 2009

### Banks Merging and Acquisition (M&A)

Bank system is going crazy. One solution is to merge all of them together under a central authority. You have N banks at the beginning and they are combined into a single bank at the end. How many different configurations of merging are possible?

1. Inductively, if I know how to merge N-1 banks, there are ( N 2 ) way of combining those merges. Therefore:

Merge(N) = ( N 2 ) * Merge (N -1) =
( N 2 )*( N-1 2 )*( N-2 2 )*...*(2 2) =
N!/(N-2)!2 * (N-1)!/(N-3)!2 *
(N-2)!/(N-3)!2 *... *2/1*2 =
N! (N-1)! / 2 ^ (N-1)

Since the first two numerators are not simplified and there are N-1 times 2 at the denominator.

Note that in this solution, the M&A operations appen one at a time _and_ the order of the merges matters.

2. If the order or M&A is not important than the solution is given by the Catalan numbers, since problem is equivalent to the problem of counting the number of different trees with n+1 leaves

http://en.wikipedia.org/wiki/Catalan_number

We have n leaves so the answer is C_{n-1}