Skew-merged permutation

In the theory of permutation patterns, a skew-merged permutation is a permutation that can be partitioned into an increasing sequence and a decreasing sequence. They were first studied by (Stankova 1994) and given their name by (Atkinson 1998).

Characterization

The two smallest permutations that cannot be partitioned into an increasing and a decreasing sequence are 3412 and 2143. (Stankova 1994) was the first to establish that a skew-merged permutation can also be equivalently defined as a permutation that avoids the two patterns 3412 and 2143.

A permutation is skew-merged if and only if its associated permutation graph is a split graph, a graph that can be partitioned into a clique (corresponding to the descending subsequence) and an independent set (corresponding to the ascending subsequence). The two forbidden patterns for skew-merged permutations, 3412 and 2143, correspond to two of the three forbidden induced subgraphs for split graphs, a four-vertex cycle and a graph with two disjoint edges, respectively. The third forbidden induced subgraph, a five-vertex cycle, cannot exist in a permutation graph (see (Kézdy Snevily)).

Enumeration

For [math]\displaystyle{ n=1,2,3,\dots }[/math] the number of skew-merged permutations of length [math]\displaystyle{ n }[/math] is

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ... (sequence A029759 in the OEIS).

(Atkinson 1998) was the first to show that the generating function of these numbers is

[math]\displaystyle{ \frac{1-3x}{(1-2x)\sqrt{1-4x}}, }[/math]

from which it follows that the number of skew-merged permutations of length [math]\displaystyle{ n }[/math] is given by the formula

[math]\displaystyle{ \binom{2n}{n}\sum_{m=0}^{n-1}2^{n-m-1}\binom{2m}{m} }[/math]

and that these numbers obey the recurrence relation

[math]\displaystyle{ P_n=\frac{(9n-8)P_{n-1} - (26n-46)P_{n-2} + (24n-60)P_{n-3}}{n}. }[/math]

Another derivation of the generating function for skew-merged permutations was given by (Albert Vatter).

Computational complexity

Testing whether one permutation is a pattern in another can be solved efficiently when the larger of the two permutations is skew-merged, as shown by (Albert Lackner).

References

• Albert, Michael; Vatter, Vincent (2013), "Generating and enumerating 321-avoiding and skew-merged simple permutations", Electronic Journal of Combinatorics 20 (2): Paper 44, 11 pp., http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i2p44 .

• Albert, Michael; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "The complexity of pattern matching for 321-avoiding and skew-merged permutations", Discrete Mathematics & Theoretical Computer Science 18 (2): P11:1–17, Bibcode: 2015arXiv151006051A, https://dmtcs.episciences.org/2607 .

• Atkinson, M. D. (1998), "Permutations which are the union of an increasing and a decreasing subsequence", Electronic Journal of Combinatorics 5: RP6:1–13, https://www.combinatorics.org/Volume_5/Abstracts/v5i1r6.html . See also the attached comment by Volker Strehl.

• Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996), "Partitioning permutations into increasing and decreasing subsequences", Journal of Combinatorial Theory, Series A 73 (2): 353–359, doi:10.1016/S0097-3165(96)80012-4 

• Sloane, N. J. A., ed. "Sequence A029759". OEIS Foundation. https://oeis.org/A029759. 

• "Forbidden subsequences", Discrete Mathematics 132 (1-3): 291–316, 1994, doi:10.1016/0012-365X(94)90242-9 . See in particular Theorem 2.9, pp. 303–304.