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} $