Misplaced Pages

Skew-merged permutation

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

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

For n = 1 , 2 , 3 , … {\displaystyle n=1,2,3,\dots } the number of skew-merged permutations of length n {\displaystyle n} 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

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

from which it follows that the number of skew-merged permutations of length n {\displaystyle n} is given by the formula

( 2 n n ) ∑ m = 0 n − 1 2 n − m − 1 ( 2 m m ) {\displaystyle {\binom {2n}{n}}\sum _{m=0}^{n-1}2^{n-m-1}{\binom {2m}{m}}}

and that these numbers obey the recurrence relation

P n = ( 9 n − 8 ) P n − 1 − ( 26 n − 46 ) P n − 2 + ( 24 n − 60 ) P n − 3 n . {\displaystyle 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 Albert & Vatter (2013).

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 Albert et al. (2016).

References

Category: