Jump to content

Skew-merged permutation

From Wikipedia, the free encyclopedia

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.