counting the number of ordered pairs in a permutohedron

Question

Recall that a permutohedron is a graph on the set of permutations $S_n$ with an edge between $\sigma$ and $\tau$ if they differ by one adjacent transposition: $\tau = (i,i+1) \circ \sigma$ for some $i \in [n-1]$. $\tau < \sigma$ if $\sigma(i) < \sigma(i+1)$, that is, if $\tau$ has one more disarranged pair than $\sigma$. This relation can be extended to a maximal partial order on $S_n$ in the obvious manner. So for instance, $1234 \geq \sigma \geq 4321$ for any $\sigma \in S_4$. This is essentially the metric $b_4$ in this paper, modified to allow only corrections of type $b_3$; but this is not important.

I would like to compute the number of pairs $(\sigma_1,\sigma_2) \in S_n^2$ for which $\sigma_1 > \sigma_2$. This allows me to know the number of pairs that are incomparable. Intuitively, $\sigma_1 > \sigma_2$ are comparable if one can traverse the permutohedron from $\sigma_1$ to $\sigma_2$ in a strictly descending path as show in wikipedia here.

Answer 1

Recall that a permutation $\sigma$ of order $n$ is uniquely determined by its inversion table: $T(\sigma)=(t_1,\dots,t_n)$, where $t_k$ is the number of integers larger than $k$ appearing in $\sigma$ ahead of $k$. The range for $t_k$ in the inversion table is $[0,n-k]$. In particular, the inversion table for the identity permutation is zero vector, while $T((n,n-1,\dots,1)) = (n-1,n-2,\dots,0,0)$.

Claim. If $\sigma_1 > \sigma_2$, then $T(\sigma_1)$ is dominated (component-wise) by $T(\sigma_2)$.

Proof. First consider two permutations that are one transposition away from each other. If $\sigma_2$ is obtained from $\sigma_1$ by exchanging $\sigma_1(i)$ and $\sigma_1(i+1)$, then:

• if $\sigma_1(i) > \sigma_1(i+1)$, then $T(\sigma_2)$ is the same as $T(\sigma_1)$, except for the $\sigma_1(i+1)$-th element which is one less than in $T(\sigma_1)$;

• if $\sigma_1(i) < \sigma_1(i+1)$, then $T(\sigma_2)$ is the same as $T(\sigma_1)$, except for the $\sigma_1(i)$-th element which is one more than in $T(\sigma_1)$.

That is, $\sigma_1 > \sigma_2$ if and only if in $T(\sigma_1)$ one element is decreased by one as compared to $T(\sigma_2)$.

If $\sigma_1 > \sigma_2$ and they are $k$ transpositions away from each other, then $T(\sigma_1)$ can be obtained from $T(\sigma_2)$ by $k$ decrements of its elements, which implies that $T(\sigma_1)$ is dominated by $T(\sigma_2)$. QED

Now, every pair of permutations $\sigma_1 \geq \sigma_2$ from $S_n$ corresponds to a vector of 2-combinations with repetitions (composed from the corresponding elements of their inversion tables), where the $k$-th 2-combination is chosen from the range $[0,n-k]$. The number of such vectors is $$\binom{n+1}{2}\cdot \binom{n}{2} \cdots \binom{2}{2} = \frac{(n+1)\cdot n!^2}{2^n}$$ and this gives an upper bound for the number of such pairs of permutations.