Random (Union Find) Spanning Tree, probability of resulting with two unconnected halves before the last step? Let N be a large even positive integer.
We start with a set of singletons from {1}, {2} ... to {N}.
In each step we randomly pick two integers and merge the sets that contain them. We continue until only one set with all numbers 1 ... N remains. What is the probability that we'll be left with two sets of equal size before the last step?
I am thinking (assuming we skip steps that don't affect the structure which obviously affects this result) that it is like choosing edges in a graph such that no edges between two even group of vertices are picked.
So we get something along the lines of:
Choose(N/2, N) * Choose(N/2 - 1, (N/2) ^ 2)^2 / Chose(N - 1, N^2)...
Is this about right?

Number of ways to break the set $\{1,2,\dots ,n\}$ into singletons (exactly the reverse process of what is asked) is
$$a_n=\prod_{k=2}^{n}\binom{k}{2}=\frac{n!(n-1)!}{2^{n-1}}$$
corresponds with this sequence (as David Callan's comment on the page suggests)
This comes from the recursion: $a_n=\binom{n}{2}a_{n-1}$ and assuming $a_1=1$
In the first step, we choose a pair of singletons and merge them. From second step onwards, the pair may be thought as a one entity as they are not going to be separated ever. This leaves us with $n-1$ objects to operate with.
If $n$ is even, the required probability is $$\frac{\frac{1}{2}\binom{n}{\frac{n}{2}}\left( a_{\frac{n}{2}} \right)^2 \binom{n-2}{\frac{n}{2}-1}}{a_n}$$
The factor of $\binom{n-2}{\frac{n}{2}-1}$ is present to count the all orderings between two $\frac{n}{2}$ sized 'build ups'.
