Counting the Number of Binary Total Partitions? On page 15 here, a binary total partition is defined. In other words, it is the number of ways to partition the set $\{1,2,...n\}$ into two subsets at each steps until only singleton sets remain. One can see that the answer is $(2n-3)!!$; the book gives a solution using generating functions, and I can easily see that the sequence satisfies the relation:
$b(n)=\frac{\sum _1 ^{n-1} \binom{n}{i} b(i)b(n-i)}{2}$.
My question is, is there a nice bijection or simple way to see the answer is $(2n-3)!!$? It seems so nice that there should be, or at least a solution without generating functions or such an ugly reccurence...
 A: There is a bijection between the number of binary total partitions and the number of rooted binary trees (RBT) on $n$ nodes.
Now, to compute the number of rooted binary trees we use generating functions. Given a RBT, say $T$, we see that it has two subtrees, namely $T(l)$ and $T(r)$, where $l$ and $r$ are the children of the root of $T$.
Let $B(n)$ be the number of RBT with $n$ nodes, $X$ a set of size $n$ and $X_{l}, X_{r}$ the left-right partitions of $X$, with sizes $n_{l}$ and $n_{r}$ respectively. It follows that
$$
B(n) = \frac{1}{2}\sum_{n_{r}, n_{l}} | B(n_{l}) | |B(n_{r}) |.
$$
(The $1/2$ is there because there are two ways to designate $r$ and $l$ as children of the root of $T$.) Then,
$$
B(n) = \frac{1}{2}\sum_{i=1}^{n-1} {n \choose i} B(i)B(n-i).
$$
Letting $b(n) = \sum_{i=1}^{\infty}B(i)n^i/i!$ we can rewrite the recursion as $$
b(n) = n + \frac{b(n)^2}{2}.
$$
Can you finish the proof from here?
A: There are two (actually more) ways to represent a binary total partition of the set {1,2,...,n}:
i) a binary tree
ii) putting 2n-2 balls into n-1 urns such that each urn contains two balls
First, the number of ways to do ii) is (2n-3)!!
To see that:
 - the ways of putting 2 balls into a 1st urn = Comb(2n-2,2)
 - the ways of putting 2 balls into a 2nd urn = Comb(2n-4,2)
 - ...
 - the the last urn, the (n-1)th, = Comb(2,2)
But the urns are unordered, it doesn't matter if I represent that for {{1,2},{3,4}} or {{3,4},{1,2}}, so you have to divide by (n-1)!
Then, denoting the number of ways to do ii) by o(n), we have:
o(n) = [Comb(2n-2,2)Comb(2n-4,2)...Comb(2,2)]/(n-1)!
     = [(2n-2)!/2^(n-1)]/(n-1)!
     = (2n-2)!/2^(n-1)(n-1)!
     =* (2n-3)!!
*in the Wikpedia (https://en.wikipedia.org/wiki/Double_factorial) you can see this identity.
Now, to see that there is a bijection between the two representations i) and ii), use the answer above, labeling the nodes in a such way that you guarantee that for each i) you have only one ii) and vice-versa.
