Let \(k\in \mathbb{N}\) and \(\Pi_k\) be the set of pairings of \(\{1,\ldots ,2k\}\). If we start from the minimal pairing \(\pi_{k,\min }\), we can obtain every pairing in \(\Pi_k\) by a finite sequence of positive adjacent transpositions . Similarly, we can reach every pairing by applying a finite sequence of negative adjacent transpositions if we start from the maximal pairing \(\pi_{k,\max }\).
Let \(\pi\in \Pi_k\). If \(\pi\) is not the minimal paring there is a negative adjacent transposition \(\tau_a\) with respect to \(\pi\) with some \(a\in \{1,\ldots ,2k-1\}\), and the pairing complexity of \(\pi\) satisfies \(\mathcal{C}(\pi)=m>0\) .
We consider \(\tau_a(\pi)\). Since negative adjacent transpositions reduce the pairing complexity by one, it is \(\mathcal{C}(\tau_a(\pi))=m-1\). If \(m-1=0\), then \(\tau_a(\pi)\) is the minimal pairing and we obtain \(\pi\) by applying \(\tau_a\) on \(\pi_{k,\min }\). Note, that \(\tau_a\) is positive with respect to \(\pi_{k,\min }\).
Otherwise, we find another negative adjacent transposition \(\tau_b\) with respect to \(\tau_a(\pi)\), which reduces the pairing complexity of \(\tau_a(\pi)\) by one. We repeat this procedure until we reach the minimal pairing, i.e. until the pairing complexity of the resulting pairing is 0. On the way, we use \(m\) adjacent transpositions, and reversing the order gives us the claimed sequence of positive adjacent transpositions needed to reach \(\pi\).
Similarly, we obtain a sequence of negative adjacent transpositions needed to reach \(\pi\), if we start from \(\pi_{k,\max }\).