tag:blogger.com,1999:blog-6314876008291942531.post5482366471945306314..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Banks Merging and Acquisition (M&A)Unknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-6314876008291942531.post-82309173221539570222009-02-12T06:35:00.000-08:002009-02-12T06:35:00.000-08:00If the order or M&A is not important than the ...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<BR/><BR/>http://en.wikipedia.org/wiki/Catalan_number<BR/><BR/>We have n leaves so the answer is C_{n-1}codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-2843119197813372292009-02-12T06:32:00.000-08:002009-02-12T06:32:00.000-08:00Inductively, if I know how to merge N-1 banks, the...Inductively, if I know how to merge N-1 banks, there are ( N 2 ) way of combining those merges. Therefore:<BR/><BR/>Merge(N) = ( N 2 ) * Merge (N -1) = <BR/>( N 2 )*( N-1 2 )*( N-2 2 )*...*(2 2) = <BR/>N!/(N-2)!2 * (N-1)!/(N-3)!2 * <BR/>(N-2)!/(N-3)!2 *... *2/1*2 = <BR/>N! (N-1)! / 2 ^ (N-1)<BR/><BR/>Since the first two numerators are not simplified and there are N-1 times 2 at the denominator.<BR/><BR/>Note that in this solution, the M&A operations appen one at a time _and_ the order of the merges matters.codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.com