In the theory of

permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...

s, a skew-merged permutation is a

permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...

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 In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be ...

is a

split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have m ...

, a graph that can be partitioned into a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

(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 subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

s 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 ).

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, ... . was the first to show that the

generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...

of these numbers is :

\frac,

from which it follows that the number of skew-merged permutations of length

n

is given by the formula :

\binom\sum_^2^\binom

and that these numbers obey the

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...

P_n=\frac.

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

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 .

References

*. *. *. See also the attached comment by Volker Strehl. * * *{{citation , last = Stankova , first = Zvezdelina E. , authorlink = Zvezdelina Stankova , doi = 10.1016/0012-365X(94)90242-9 , issue = 1-3 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 1297387 , pages = 291–316 , title = Forbidden subsequences , volume = 132 , year = 1994, doi-access = free . See in particular Theorem 2.9, pp. 303–304. Permutation patterns