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?
Pubblicato da a
Reazioni: 

2 comments:

  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.

    ReplyDelete

  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}

    ReplyDelete

Subscribe to: Post Comments (Atom)