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.