Random commentary about Machine Learning, BigData, Spark, Deep Learning, C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

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?

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

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

ReplyDeleteMerge(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.

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

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

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