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}