Let \(k\in \mathbb{N}\) and \(\Pi_k\) be the set of pairings of \(\{1,\ldots ,2k\}\). Two pairs \(\{a,A\}\), \(\{b,B\}\), of a pairing \(\pi\in \Pi_k\) with \(a< A\) and \(b< B\), are crossed if
\[ a < b < A < B \quad \text{or} \quad b < a < B < A, \]and nested if
\[ a < b < B < A \quad \text{or} \quad b < a < A < B. \]The complexity of a pairing \(\pi\in \Pi_k\) is defined by
\[ \mathcal{C}(\pi) = C + 2N, \]where \(C\) is the number of crossed pairs in \(\pi\) and \(N\) is the number of nested pairs in \(\pi\).
Example
Consider the pairing \(\pi=(1~~6)(2~~4)(3~~5)\).
Visualization of the pairing \((1~~6)(2~~4)(3~~5)\)
This pairing has one crossed pair, namely \(\{2,4\}\) and \(\{3,5\}\), and 2 nested pairs, since \(\{1,6\}\) is nested with \(\{2,4\}\) and \(\{3,5\}\). Therefore,
\[ \mathcal{C}\bigl((1~~6)(2~~4)(3~~5)\bigr)=5. \]
Remarks
- By definition follows \(\mathcal{C}(\pi)\ge 0\) for every pairing \(\pi\).
- Positive adjacent transpositions increase the pairing complexity by one, while negative adjacent transpositions reduce it by one (see (0x68980e37) ).
- The pairing complexity of a pairing \(\pi\) corresponds to the number of positive adjacent transpositions needed to obtain \(\pi\) when starting with the minimal pairing (see (0x687552d6) ).
- The pairing complexity satisfies \[ \mathcal{C}(\pi)\in [0,4k^2-2k], \] for all pairings \(\pi\). Only the maximal and minimal pairings attain the border cases (see (0x68984230) ).