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 and given their name by.
Characterization
The two smallest permutations that cannot be partitioned into an increasing and a decreasing sequence are 3412 and 2143. 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 and an independent set. 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.
Enumeration
For the number of skew-merged permutations of length iswas 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.