In the theory of

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

s, a skew-merged permutation is a

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

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 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 , where they called these ...

, a graph that can be partitioned into a

clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

(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 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. Definition Formally, let G=(V,E) ...

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 representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...

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