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 Template:Harvtxt and given their name by Template:Harvtxt.

Characterization

The two smallest permutations that cannot be partitioned into an increasing and a decreasing sequence are 3412 and 2143. Template:Harvtxt 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 Template:Harvtxt).

Enumeration

For $n=1,2,3,\dots$ the number of skew-merged permutations of length $n$ is

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ... Template:OEIS.

Template:Harvtxt was the first to show that the generating function of these numbers is

$\frac{1-3x}{(1-2x)\sqrt{1-4x}},$

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

$(\genfrac{}{}{0ex}{}{2n}{n})\sum _{m=0}^{n-1}{2}^{n-m-1}(\genfrac{}{}{0ex}{}{2m}{m})$

and that these numbers obey the recurrence relation

$P_n=\frac{(9n-8)P_{n-1}-(26n-46)P_{n-2}+(24n-60)P_{n-3}}{n}.$

Another derivation of the generating function for skew-merged permutations was given by Template:Harvtxt.

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 Template:Harvtxt.

References

• Template:Citation.

• Template:Citation.

• Template:Citation. See also the attached comment by Volker Strehl.

• Template:Citation

• Template:Cite OEIS

• Template:Citation. See in particular Theorem 2.9, pp. 303–304.