Author |
Topic: Ways to merge (Read 1439 times) |
|
mad
Junior Member
Posts: 118
|
 |
Ways to merge
« on: Feb 9th, 2008, 5:09pm » |
 Quote  Modify
|
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..
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
|
Re: Ways to merge
« Reply #1 on: Feb 9th, 2008, 8:16pm » |
Quote Modify
|
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  k=2..N C(k,2) = N!(N-1)!/2N-1.
|
| « Last Edit: Feb 9th, 2008, 8:23pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Ways to merge
« Reply #2 on: Feb 10th, 2008, 9:28am » |
Quote Modify
|
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...
|
| « Last Edit: Feb 10th, 2008, 9:52am by Hippo » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Ways to merge
« Reply #3 on: Feb 10th, 2008, 12:33pm » |
Quote Modify
|
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".
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Ways to merge
« Reply #4 on: Feb 10th, 2008, 3:08pm » |
Quote Modify
|
 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.
|
| « Last Edit: Feb 10th, 2008, 3:10pm by Hippo » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Ways to merge
« Reply #5 on: Feb 11th, 2008, 3:54pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ways to merge
« Reply #6 on: Feb 12th, 2008, 12:31am » |
Quote Modify
|
on Feb 11th, 2008, 3:54pm, 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.
|
| « Last Edit: Feb 12th, 2008, 12:40am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Ways to merge
« Reply #7 on: Feb 12th, 2008, 1:47am » |
Quote Modify
|
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]
|
| « Last Edit: Feb 12th, 2008, 3:19am by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Ways to merge
« Reply #8 on: Feb 12th, 2008, 2:42am » |
Quote Modify
|
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).
|
| « Last Edit: Feb 12th, 2008, 3:00am by Hippo » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Ways to merge
« Reply #9 on: Feb 12th, 2008, 5:54pm » |
Quote Modify
|
on Feb 12th, 2008, 12:31am, 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?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ways to merge
« Reply #10 on: Feb 13th, 2008, 2:04am » |
Quote Modify
|
on Feb 12th, 2008, 5:54pm, 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..
|
| « Last Edit: Feb 13th, 2008, 2:08am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Ways to merge
« Reply #11 on: Feb 13th, 2008, 6:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Ways to merge
« Reply #12 on: Feb 14th, 2008, 12:17am » |
Quote Modify
|
on Feb 13th, 2008, 6:43pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Ways to merge
« Reply #13 on: Feb 14th, 2008, 1:29am » |
Quote Modify
|
on Feb 13th, 2008, 2:04am, 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)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print