The two smallest permutations that cannot be partitioned into an increasing and a decreasing sequence are 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)).
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 Albert & Vatter (2013).