Number of company mergers - explanation rather than proof

One of the famous problems in combinatorics that interests a comp.sci. enthusiast - is the Catalan's problem - that talks about finding the number of binary bracketings of n elements. For example, if we consider three elements 1, 2 and 3. We have :

((1 2)3)
(1(2 3))

as the binary brackets, in that order of 1,2 and 3. If we consider 4 elements, say, 1, 2, 3 and 4. The number of binary brackets in that order is 5 - and they are:

(((1 2) 3)4)
((1 (2 3))4)
((1 2)(3 4))
(1((2 3) 4))
(1(2 (3 4)))

Imagine 1,2,3 and 4 to be 4 elements held in the computer memory. In the above example, we have fixed order of retrieval of the elements, i.e 1,2,3 and 4.

Catalan has proved that this number is given by the formula:
C(n-1) = 1/n * (2n-2 C n-1) , where (n C k) is n choose k - or the kth binomial co-efficient.

It is easy to see that, this number also exactly gives the number of un-ordered full-binary trees of n-leaves (or n-1 internal nodes).

    o      0                0       0         0        0       0 
   / \    / \              / \     / \      /   \     / \     / \
  0   3  1   0            0   4   0   4    0     0   1   0   1   0
 / \        / \          / \     / \      / \   / \     / \     / \
1   2      2   3        0   3   1   0    1   2 3   4   0   4   2   0
                       / \         / \                / \         / \
                      1   2       2   3              2   3       3   4

Leaving this at that, let's look at a related interesting problem of counting various possible ways to merge N companies. This is related to the above problem because, in essence we are counting binary bracketings of companies. But here, the differnce is that, order matters. Since there are N companies - the merger process can be viewed as a full binary tree with N leaves. The number of such un-ordered trees is given by the formula mentioned above.

The points that effect the count are
1) The permutations of this set of companies and
2) Whether the A merging with B - must be treated same as B merging with A (commutativity). To view it differently, if A is a merger of K companies, and B is a merger of m companies, should we take into consideration the chronology of the events, because of which A->B is different from B->A.

Taking point 1, we have N! permutations of N companies.
Now consider point 2. Because of the properties of full binary tree, there are N-1 internal nodes with a tree with N leaves. Commutativity can be simply viewed as a mirror rotation of the tree (subtree) at an internal node. For example.

    O                                    O
   / \    == Mirror Rotation on O ==    / \
  A   B                                B   A

Since there are 2 degrees of freedom the number of such combinations possible for N-1 internal nodes is 2^(N-1) . This is easily seen if you view the two possible postions at an internal node as 0 and 1, and then count the number of N-1 length binary strings.

With this prologue, lets look at the two problems of company mergers:
1) Where the timing does matter: In this case only the first point (about permutations) need to be considered and so - the answer turns out to be :
T(N) = C(N-1) = N!/N * (2N-2 C N-1) , where (n C k) is n choose k - or the kth binomial co-efficient.

2) Where timing doesn't matter -- i.e. A->B is considered same as B->A, we need to nullify the effect of the mirror trees, because of which a division by 2^(N-1) is required. SO the formula turns out to be:
T(N) = C(N-1) = 1/2^(N-1) * N!/N * (2N-2 C N-1) , where (n C k) is n choose k - or the kth binomial co-efficient.

OR

T(N) = C(N-1) = (N-1)!/2^(N-1) * (2N-2 C N-1) , where (n C k) is n choose k - or the kth binomial co-efficient.

There is a simple proof that the number is second formula is nothing but (2N-3) !! (double factorial).