Question taken from Q4 of this handout: here.
Let $S$ be a set of $n$ elements. Let $f(n)$ be the number of ways to completely partition $S$. Here, a complete partition is defined as follows: If S has more than one element, partition $S$ into two disjoint nonempty subsets $S_1$ and $S_2$. Then take one of the sets $S_1, S_2$ with more than one element, and partition it into two disjoint nonempty subsets $S_3$ and $S_4$, then take one of the sets with more than one element and partition it into two disjoint nonempty subsets, etc., until only one-element subsets remain. We call this a complete partition of $S$. The order in which the sets are split is important.
Example. Let $S={1,2,3}$. For simplicity, write $S$ as $123$. Then there are 3 possible partitions. $$123 \to 1, 23 \to 1, ,2 ,3$$ $$123 \to 2, 13 \to 2, ,1 ,3$$ $$123 \to 3, 12 \to 3, ,1 ,2$$
The order of the partitioning matters. For example, if you have $S = 1234$, then $$ 1234 \to 12, 34 \to 1,2, 34 \to 1,2,3,4 $$ $$ 1234 \to 12, 34 \to 12, 3,4 \to 1,2,3,4 $$ are two separate ways to completely partition $S$.
The first few values of $f(n)$ are
- $f(1) = 1$
- $f(2) = 1$
- $f(3) = 3$
- $f(4) = 18$
I have thought of a recursive way to compute these values. I imagine things as going in reverse, i.e. $f(n)$ is counting the number of ways to combine $n$ singleton sets into a single set of size $n$. Then to compute $f(n+1)$, there are $n+1 \choose 2$ possible first steps, because you choose any two singleton sets to combine together. Thus, $f(n+1) = {n+1 \choose 2}f(n)$. Solving the reccurence, I get $$ f(n) = \frac{(n)! (n-1)!}{2^{n-1}} $$ From this, I can compute $$ f(5) = 180, \quad f(6) = 2700, ...$$
However, the handout actually encourages searching for a nonrecursive solution. Is there a some combinatorial way to get the same answer? Or some way of interpreting this closed form, so that it is more clear why this closed form gives the answer.
Thanks for the help, and if there is any problems with my reasoning please let me know too.
Any complete partition is completely described by the following: arrange the numbers in a line ($n!$ possibilities), order the gaps between the $n$ terms ($(n-1)!$ possibilities). Then each partition simply cuts at the next gap.
Clearly you have counted each complete partition $2^{n-1}$ times, as for each of the $n-1$ partitions you could have placed the pieces either side of each other.