This question already has an answer here:

This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's.

Let $G=(V,E)$ be a graph. An edge ordering of $E$ (or $G$) is a bijection $\phi$ from $\{1,\dots,|E|\}$ to $E$. Let $G_k$ be the graph induced by the edge set $E_k=\{\phi(i)|1\leq i \leq k\}$. An edge ordering is connected if $G_k$ is connected for all $1\leq k\leq |E|$.

How many connected edge orderings are there for $G=K_n$, the complete graph on $n$ vertices?

Asymptotics would be fine, but I suspect there might be a nice closed-form expression:

For $K_{m,n}$ (the complete bipartite graph on sets of $m$ and $n$ vertices) the conjectured answer is $m!n!(mn)!/(m+n-1)!$, from "Number of collinear ways to fill a grid". This is because there's a bijection between connected edge orderings of $K_{m,n}$ and collinear $m\times n$ grid fillings (take the row and column sets to be the vertex sets of $K_{m,n}$ and grid squares to be the edges).


As Richard Stanley points out (and as I could have deduced if I'd looked at the earlier questions of Sebastien Palcoux), connected edge orderings of a graph are the same as shellings of that graph viewed as a 1D simplicial complex.

Here are SageMath implementations of user44191's recursion formula in the comments and Richard Stanley's formula in his answer (removing the factor of $n!/2$ coming from different orderings of the vertices).

def partialrecursionformula(m,n):
    if [m,n] == [1,0]:
        return 1
    elif n<m-1 or m==0:
        return 0
        return ((m*(m-1)/2 - i)*partialrecursionformula(m,i)
                + (m-1)*partialrecursionformula(m-1,i))

def recursionformula(m):
    return partialrecursionformula(m,m*(m-1)/2)

def stanleyformula(m):
    f = [rising_factorial(i*m - i*(i+1)/2 + 1, m-i-2) for i in range(m-2)]
    return factorial(m-1)*prod(f)

Numerically, they agree at least up to $K_{8}$ (I am convinced that they both count the connected edge orderings correctly for all $n$, so this was just a check that there are no typos).

The sequence of the number of shellings of $K_n$ that reach the vertices in order thus begins 1, 1, 2, 48, 34560, 1383782400, 4914953551872000, 2256176006302688870400000, and it's easy to get more values with Richard Stanley's formula.

edit 2: Fedor Petrov points out in the comments that this question (phrased in terms of probabilities) has already been asked and answered here.


marked as duplicate by j.c., Community Apr 12 '18 at 12:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ You have a similar recursion relation. Let $g(m, n)$ be the number of partial connected edge orderings with $n$ edges on $K_m$ that have reached every vertex. Your specific answer is $g(m, \frac{m (m + 1)}{2})$. Let $\tilde{g}(m, n) = 2 \frac{g(m, n)}{m!}$. This represents the number of partial connected edge orderings that reach every vertex in $K_m$ in order (with ambiguity allowed for the first two vertices). Then we have the following recursion relation: $\tilde{g}(m, n + 1) = (\frac{m(m + 1)}{2} - n) \tilde{g}(m, n) + (m - 1) \tilde{g}(m - 1, n)$ $\endgroup$ – user44191 Apr 9 '18 at 20:40
  • 2
    $\begingroup$ @user44191 I believe your recursion should be $\tilde{g}(m,n+1)=(\frac{m(m-1)}{2}-n)\tilde{g}(m,n)+(m-1)\tilde{g}(m-1,n)$, and the number I'm asking about is actually $g(m,\frac{m(m-1)}{2})$. With those corrections, it agrees with Richard Stanley's formula (at least up to $n=8$ with my slow sage code). $\endgroup$ – j.c. Apr 10 '18 at 12:07
  • $\begingroup$ @jc You are, of course, correct. $\endgroup$ – user44191 Apr 10 '18 at 22:01
  • 3
    $\begingroup$ mathoverflow.net/questions/199342/… is it the same question? looks so $\endgroup$ – Fedor Petrov Apr 11 '18 at 18:08
  • $\begingroup$ @FedorPetrov Great! $\endgroup$ – j.c. Apr 11 '18 at 20:59

Write $\langle m\rangle_i=m(m+1)\cdots (m+i-1)$. There are $\frac 12 n!$ ways to choose the order in which new vertices are attached (since at the first step we attach two at once). There are $(n-1)!$ ways to choose the vertex that each new vertex is attached to. Suppose we have made these choices. Now there are $(n-2)!=\langle 1\rangle_{n-2}$ ways to choose the order in which we add the $n-2$ additional edges incident to the last attached vertex. Then there are $\langle n\rangle_{n-3}$ ways to specify how to add the additional $n-3$ edges adjacent to the next-to-last attached vertex. Then there are $\langle 2n-2\rangle_{n-4}$ ways to specify how to add the additional $n-4$ edges adjacent to the third-from-last attached vertex. Continuing in this way shows that the total number of edge orderings is $$ \frac 12n!\,(n-1)!\prod_{i=0}^{n-3} \left\langle in-\binom{i+1}{2}+1\right\rangle_{n-i-2} = \frac{2^n n! (n - 1)! \binom{n}{2}!}{4 (2n - 2)!} \text{ (see comments)}$$ Perhaps I have made a computational error, but I think the method is correct.

I can also point out, though irrelevant to the solution, that you are asking for the number of shellings of the complete graph, regarded as a one-dimensional simplicial complex.

  • 1
    $\begingroup$ The formula can be made shorter, by rewriting the $\langle m \rangle_i$ as a fraction of factorials, and using the fact that the sequence telescopes (after adding in a term to each factorial). If I'm not wrong, the answer is equal to $\frac{n! (n - 1)! \binom{n}{2}!}{2 \prod_{i = 0}^{n - 2} n (i + 1) - \binom{i + 2}{2}}$. $\endgroup$ – user44191 Apr 10 '18 at 22:57
  • 3
    $\begingroup$ And that expression can be further simplified; $n (i + 1) - \binom{i + 2}{2} = (i + 1)(n - \frac{i + 2}{2})$, so the product is $(n - 1)! \prod_{i = 0}^{n - 2} n - \frac{i + 2}{2} = \frac{1}{2^{n - 1}} (n - 1)! \prod_{i = 0}^{n - 2} 2n - i - 2 = \frac{2}{2^n} (n - 1)! \frac{(2n - 2)!}{(n - 1)!}$, so the fully simplified formula is $\frac{2^n n! (n - 1)! \binom{n}{2}!}{4 (2n - 2)!}$ $\endgroup$ – user44191 Apr 10 '18 at 22:59
  • $\begingroup$ @user44191: your comment is a nice complement to Richard Stanley's answer. You should ask him whether you can edit his answer, or you should write a complementary answer. Do you think that your conjecture for $K_{m,n}$ can be proved by: first an analogous of Richard Stanley's argument and then an analogous of your simplification? $\endgroup$ – Sebastien Palcoux Apr 11 '18 at 15:56
  • $\begingroup$ @SebastienPalcoux If it could be proven analogously, my guess is that it would extend to a proof for any edge-transitive graph. $\binom{n}{2}$ is the size of the automorphism group of the whole graph, while $n! (n - 1)!$ can be related to the number of "flags" (vertex-edge pairs); I'm not sure what relevant thing $\frac{4 (2n - 2)!}{2^n}$ expresses, but there should be some symmetry that gets it. $\endgroup$ – user44191 Apr 11 '18 at 16:28
  • $\begingroup$ Err, $\binom{n}{2}$! is the number of orders of the edges, rather. $\endgroup$ – user44191 Apr 11 '18 at 20:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.