We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, after the $k$th edge in the list is placed, the so-far created graph will have exactly $k$ edges).

Let $H_k$ be the graph induced by the first $k$ edges. Let $p(n)$ be probability that $H_k$ is connected for all $k \in \{1,2,\dots,{n \choose 2}\}$.

As a corollary to a completely different problem I'm working on, and through a very round-about way, we were able to show that the answer for $p(n)$ is beautiful. Indeed, it is simply

$$\frac{2^{n-2}}{C_{n-1}},$$ where $C_{m}$ is the $m$th Catalan number.

I'd like to find a good combinatorial reason why this is the answer.

(This is the easiest case of a more general problem I'm working on. I do have one semi-combinatorial argument but unfortunately it doesn't generalize well.)

Any thoughts would be appreciated! Thanks!!

1more comment