Talk:TADM2E 2.49

Two answers were provided that are incorrect. I have edited the page to show the original answer, and will keep the other two here. I wil give a comment about where mistakes were made.

Mistaken Answer 1

With 2 companies {a,b}, there's only one way to merge: [ab]

With three companies {a,b,c}, we need to find the number of ways that the three companies can become two companies, and for every one of those possibilities, the two remaining companies can be reduced to one in only 1 way (because we've already solved the case of two companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b}, {bc,a}], or 3.

Now we see a pattern emerging. For n companies, the answer is $ f(n - 1) * g(n) $, where g(n) is the number of ways to reduce n companies to n - 1 companies. g(n) is the sum from 1 to n - 1 of n, which is $ n(n - 1)/2 $. Thus, the answer is $ f(n - 1) * n(n - 1)/2 $.

Where mistake was made

This is close to being correct, but it is not true that "g(n) is the sum from 1 to n - 1 of n." In fact, g(n) is the number of ways to choose 2 companies out of n companies, or $ n \choose 2 $. The correct recurrence is $ f(n) = f(n - 1) * {n \choose 2} $

Mistaken Answer 2

Let's $ f(n) $ denotes the number of ways $ n $ company can merge. We have (assume that merge in this problem doesn't mean acquire as the later is not commutative)

- $ f(2) = 1 $. - $ f(3) = 3 $. From 3 companies, we can first merge any 2 to reduce the size of set to 2. Then, we can merge the 2 new companies. There're 3 ways to select 2 companies from 3. - $ f(n) = \binom{n}{n-1}f(n-1) $. We can merge $ n $ companies by first merge $ n-1 $ ones of them, and then merge the last 2 remaining companies. There're $ \binom{n}{n-1} = n $ ways to select a sub set of $ n-1 $ items from $ n $ items. And we already know that there're $ f(n-1) $ ways to merge the subset (with $ n \ge 3 $.

So, our final function is:

$ f(n) = n.f(n-1) = n(n-1)(n-2)\ldots 3 = \frac{n!}{2} $

Note: my answer is different with the old answer by another wiki editor. I don't know if my understanding about the problems is correct. It's up to the next editor to justify and edit this page again.

My argument is the old solution has some duplication in the way the companies merge together, while my solution is not. Consider $ n=4 $.

The old solution first select 2 companies to merge, reduce the size of set from 4 to 3, and then select 2 companies in new set to merge. So, some thing like the following might happen:

{a,b,c,d}
-> {ab, c, d}, {a, b, cd}
-> {ab, cd} and {ab, cd} // This is a duplication, thus, the result is invalid.

Meanwhile, my solution first try to combine $ n-1 $ companies. And because all subset is different with each other, there's no duplication appear.

Where mistake was made

It is true that the sets {ab, c, d} and {a, b, cd} can both be reduced to {ab, cd}. But this is a decision tree, which means that the number of reductions of {ab, cd} should be counted twice, since there are 2 ways of reaching it.

A similar flawed argument would be to say the number of possible 3-digit numbers is the same as the number of possible 4-digit numbers, because we don't want to count the possibilities of the remaining 3 digits more than once, for each of the fourth digit..