wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Ways to merge
        
(Message started by: mad on Feb 9th, 2008, 5:09pm)
Title: Ways to merge
Post by mad on Feb 9th, 2008, 5:09pm
You have given N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

Eg. merge 1&2, then the resut with 3 and then with 4 etc..
Title: Re: Ways to merge
Post by Icarus on Feb 9th, 2008, 8:16pm
Do mergers need to be between pairs of companies, or can 3 or more companies merge at once?

If the mergers can only be between pairs of companies, then I believe the answer is http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gifk=2..N C(k,2) = N!(N-1)!/2N-1.
Title: Re: Ways to merge
Post by Hippo on Feb 10th, 2008, 9:28am
I am not sure with that....
If I merge A with B than C with D than both AB and CD together.
Is this same as if I merge C with D than A with B than both AB and CD together?

For pairwise merging I would expect something like (N-2)th Catalan number divided by 2^(N-1).

Write merges in polish notation, arguments can be switched without influencing result...
Title: Re: Ways to merge
Post by Icarus on Feb 10th, 2008, 12:33pm
Actually there are two separate questions here: Is merging a commutative operation? And, is merging an associative operation?

I.e., Is Pepsico-Microsoft considered to be the same merged company as Microsoft-Pepsico? I assumed this was the case.

Second, is Pepsico-(Microsoft-Walmart) the same company as (Pepsico-Microsoft)-Walmart?

My calculation assumes both answers are "yes".
Title: Re: Ways to merge
Post by Hippo on Feb 10th, 2008, 3:08pm
:) I have expected comutativity and nonassociativity, but I don't specify "an order of merging in independent branches." So I can write (A+B)+(C+D).
It seems to me you count (A+1B)+3(C+2D) and  (A+2B)+3(C+1D) as distinct expressions.
Title: Re: Ways to merge
Post by Icarus on Feb 11th, 2008, 3:54pm
Actually, the problem becomes trivial if you have both commutativity and associativity: Then there is only 1 way of forming the company!

You're right, my count differentiates based on order of merger for subordinate companies, which is clearly inappropriate.
Title: Re: Ways to merge
Post by towr on Feb 12th, 2008, 12:31am

on 02/11/08 at 15:54:30, Icarus wrote:
Actually, the problem becomes trivial if you have both commutativity and associativity: Then there is only 1 way of forming the company!
The question is in how many ways you can arrive at the end result, not how many different end results there are.
Merging A+B, then AB+C, is a qualitatively different way from A+C and then AC+B, even though they both yield ABC.
Title: Re: Ways to merge
Post by Grimbal on Feb 12th, 2008, 1:47am
As I see it, there are (2N-2)/2 ways to do the last merger.  Just split the companies in 2 subsets.  Each of these cases must be multiplied by the number of ways to merge each subset into one company each.

So, the formula would be:
W(1) = 1
W(N) = sumk=1..N-1 C(N,k)/2*W(k)*W(N-k)
W(N) = N!/2 sumk=1..N-1 W(k)/k! · W(N-k)/(N-k)!
W(N)/N! = 1/2 sumk=1..N-1 W(k)/k! · W(N-k)/(N-k)!

If we write W(n) = w(n)·n!/2n-1 we have

w(1) = 1
w(N) = sumk=1..N-1 w(k)·w(N-k)

w(n) is cn-1, the (n-1)th catalan number.

W(N) = cN-1·N!/2N-1

[edit]added a line for educational purposes[/edit]
Title: Re: Ways to merge
Post by Hippo on Feb 12th, 2008, 2:42am
Grimbal: It looks well.
For teaching purposes I would show how whe w(N) expression was found. ... divide both sides by N! to make them look almost equal.

Now you get F(N)=1/2\sum F(k)F(N-k). There is constant factor on right side and there is F in 2nd power on the right side while in 1st on left ... multiply both sides by factor^N ... you obtain F(N)/2^N=1/2\sum F(k)/2^k F(N-k)/2^(N-k).
Now you can easily merge the factor into "function name" ... divide by the factor ...
F(N)/2^(N-1)=\sum F(k)/2^(k-1) F(N-k)/2^(N-k-1) and call w(N)=F(N)/2^(n-1).
Title: Re: Ways to merge
Post by Icarus on Feb 12th, 2008, 5:54pm

on 02/12/08 at 00:31:37, towr wrote:
The question is in how many ways you can arrive at the end result, not how many different end results there are.
Merging A+B, then AB+C, is a qualitatively different way from A+C and then AC+B, even though they both yield ABC.


And that is the point. If the merging process is commutative (so that AB is not qualitatively different from BA) and associative (so that AB+C is not qualitatively different from A + BC), then no matter how you merge the companies together, there is no qualitative difference. Hence there would be effectively only one way of merging. Thus I was answering one of my own questions from my previous post (after the way was pointed by Hippo). The merging process should not be considered associative.

The commutative question remains unanswered, though. Is it really the same if Microsoft does a hostile takeover of Podunk Computers, or if Gates kicks the bucket, leaves all his stock to his old childhood friend Jeff Podunk, and suddenly Podunk Computers finds itself owning Microsoft?
Title: Re: Ways to merge
Post by towr on Feb 13th, 2008, 2:04am

on 02/12/08 at 17:54:22, Icarus wrote:
And that is the point. If the merging process is commutative (so that AB is not qualitatively different from BA) and associative (so that AB+C is not qualitatively different from A + BC), then no matter how you merge the companies together, there is no qualitative difference. Hence there would be effectively only one way of merging. Thus I was answering one of my own questions from my previous post (after the way was pointed by Hippo). The merging process should not be considered associative.
Can a process ever be associative? A process is temporal in nature, so doing one step before the next is always different than the reverse. Associativity seems to me like a typical thing that only applies with respect to values of expressions.
I'm open to any counter examples though..
Title: Re: Ways to merge
Post by Icarus on Feb 13th, 2008, 6:43pm
Umm... How about that process called "addition", then? or the one called "multiplication". a + (b + c) means that you add b and c first, temporally, then add a to the result.
Title: Re: Ways to merge
Post by towr on Feb 14th, 2008, 12:17am

on 02/13/08 at 18:43:00, Icarus wrote:
Umm... How about that process called "addition", then? or the one called "multiplication". a + (b + c) means that you add b and c first, temporally, then add a to the result.
In those cases the result is the same, but the ways of calculating isn't.
Proceeding along the steps (1+2)+3 = 3+3 = 6 is not the same process as doing 1+(2+3) = 1+5 = 6. Associativity says the result is the same in every case, not that the process is the same.
Title: Re: Ways to merge
Post by Grimbal on Feb 14th, 2008, 1:29am

on 02/13/08 at 02:04:09, towr wrote:
Can a process ever be associative? A process is temporal in nature, so doing one step before the next is always different than the reverse. Associativity seems to me like a typical thing that only applies with respect to values of expressions.
I'm open to any counter examples though..

In some sense, yes.
Doing
   (A followed by B) followed by C
is exactly the same as
   A followed by (B followed by C)


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board