En la teoría de patrones de permutación , una permutación fusionada por desviación es una permutación que se puede dividir en una secuencia creciente y una secuencia decreciente. Fueron estudiadas por primera vez por Stankova (1994) y recibieron su nombre de Atkinson (1998).
Las dos permutaciones más pequeñas que no se pueden dividir en una secuencia creciente y una decreciente son 3412 y 2143. Stankova (1994) fue la primera en establecer que una permutación fusionada sesgada también se puede definir de manera equivalente como una permutación que evita los dos patrones 3412 y 2143.
Una permutación se fusiona de forma sesgada si y solo si su grafo de permutación asociado es un grafo dividido , un grafo que se puede dividir en una camarilla (que corresponde a la subsecuencia descendente) y un conjunto independiente (que corresponde a la subsecuencia ascendente). Los dos patrones prohibidos para permutaciones fusionadas de forma sesgada, 3412 y 2143, corresponden a dos de los tres subgrafos inducidos prohibidos para grafos divididos, un ciclo de cuatro vértices y un grafo con dos aristas disjuntas, respectivamente. El tercer subgrafo inducido prohibido, un ciclo de cinco vértices, no puede existir en un grafo de permutación (véase Kézdy, Snevily y Wang (1996)).
Para el número de permutaciones de longitud fusionadas de forma sesgada es
Atkinson (1998) fue el primero en demostrar que la función generadora de estos números es
de lo cual se deduce que el número de permutaciones de longitud fusionadas de forma sesgada viene dado por la fórmula
y que estos números obedecen a la relación de recurrencia
Albert y Vatter (2013) dieron otra derivación de la función generadora para permutaciones fusionadas sesgadas.
La prueba de si una permutación es un patrón en otra se puede resolver de manera eficiente cuando se realiza una fusión sesgada de la mayor de las dos permutaciones, como lo demuestran Albert et al. (2016).
