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

edit

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 & Wang (1996)).

Enumeration

edit

For   the number of skew-merged permutations of length   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

 

from which it follows that the number of skew-merged permutations of length   is given by the formula

 

and that these numbers obey the recurrence relation

 

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

Computational complexity

edit

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 et al. (2016).

References

edit
  • 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, arXiv:1301.3122, doi:10.37236/3058, MR 3084586.