En matemáticas combinatorias , una permutación separable es una permutación que se puede obtener a partir de la permutación trivial 1 mediante sumas directas y sumas oblicuas . [1] Las permutaciones separables se pueden caracterizar por los patrones de permutación prohibidos 2413 y 3142; [2] también son las permutaciones cuyos gráficos de permutación son cografos y las permutaciones que realizan los órdenes parciales serie-paralelo . Es posible probar en tiempo polinomial si una permutación separable dada es un patrón en una permutación más grande, o encontrar el subpatrón común más largo de dos permutaciones separables.
Bose, Buss y Lubiw (1998) definen una permutación separable como una permutación que tiene un árbol separador : un árbol binario con raíz en el que los elementos de la permutación aparecen (en orden de permutación) en las hojas del árbol, y en el que los descendientes de cada nodo del árbol forman un subconjunto contiguo de estos elementos. Cada nodo interior del árbol es un nodo positivo en el que todos los descendientes del hijo izquierdo son más pequeños que todos los descendientes del nodo derecho, o un nodo negativo en el que todos los descendientes del nodo izquierdo son más grandes que todos los descendientes del nodo derecho. Puede haber más de un árbol para una permutación dada: si dos nodos que son adyacentes en el mismo árbol tienen el mismo signo, entonces pueden ser reemplazados por un par diferente de nodos utilizando una operación de rotación de árbol .
Cada subárbol de un árbol separador puede interpretarse como si representara una permutación separable más pequeña, cuyos valores de los elementos están determinados por la forma y el patrón de signos del subárbol. Un árbol de un nodo representa la permutación trivial, un árbol cuyo nodo raíz es positivo representa la suma directa de las permutaciones dadas por sus dos subárboles hijos, y un árbol cuyo nodo raíz es negativo representa la suma oblicua de las permutaciones dadas por sus dos subárboles hijos. De esta manera, un árbol separador es equivalente a una construcción de la permutación mediante sumas directas y oblicuas, a partir de la permutación trivial.
Como demuestran Bose, Buss y Lubiw (1998), las permutaciones separables también pueden caracterizarse en términos de patrones de permutación : una permutación es separable si y sólo si no contiene ni 2413 ni 3142 como patrón. [2]
Las permutaciones separables también tienen una caracterización de la geometría algebraica : si una colección de polinomios reales distintos tienen todos valores iguales en algún número x , entonces la permutación que describe cómo cambia el orden numérico de los polinomios en x es separable, y cada permutación separable puede realizarse de esta manera. [3]
Las permutaciones separables se enumeran mediante los números de Schröder . Es decir, hay una permutación separable de longitud uno, dos de longitud dos y, en general, el número de permutaciones separables de una longitud dada (empezando por la longitud uno) es
Este resultado fue demostrado para una clase de matrices de permutación equivalentes a las permutaciones separables por Shapiro y Stephens (1991), utilizando una forma canónica del árbol separador en el que el hijo derecho de cada nodo tiene un signo diferente al del nodo mismo y luego aplicando la teoría de funciones generadoras a estos árboles. Otra prueba que se aplica más directamente a las permutaciones separables fue dada por West (1995). [4]
Bose, Buss y Lubiw (1998) demostraron que es posible determinar en tiempo polinomial si una permutación separable dada es un patrón en una permutación más grande, en contraste con el mismo problema para permutaciones no separables, que es NP-completo .
El problema de encontrar el patrón separable más largo que sea común a un conjunto de permutaciones de entrada se puede resolver en tiempo polinomial para un número fijo de permutaciones de entrada, pero es NP-difícil cuando el número de permutaciones de entrada puede ser variable, y sigue siendo NP-difícil incluso cuando todas las entradas son separables. [5]
Las permutaciones separables surgieron por primera vez en el trabajo de Avis y Newborn (1981), quienes demostraron que son precisamente las permutaciones que se pueden ordenar mediante un número arbitrario de pilas emergentes en serie, donde una pila emergente es una forma restringida de pila en la que cualquier operación emergente extrae todos los elementos a la vez.
Shapiro y Stephens (1991) volvieron a considerar las permutaciones separables en su estudio de la percolación bootstrap , un proceso en el que una matriz de permutación inicial se modifica cambiando repetidamente a uno cualquier coeficiente de matriz que tenga dos o más vecinos ortogonales iguales a uno. Como muestran, la clase de permutaciones que se transforman mediante este proceso en la matriz todo-uno es exactamente la clase de permutaciones separables.
El término "permutación separable" fue introducido más tarde por Bose, Buss y Lubiw (1998), quienes las consideraron por sus propiedades algorítmicas.
Cada permutación puede usarse para definir un grafo de permutación , un grafo cuyos vértices son los elementos de la permutación y cuyos bordes son las inversiones de la permutación. En el caso de una permutación separable, la estructura de este grafo puede leerse a partir del árbol de separación de la permutación: dos vértices del grafo son adyacentes si y solo si su ancestro común más bajo en el árbol de separación es negativo. Los grafos que pueden formarse a partir de árboles de esta manera se denominan cografos (abreviatura de grafos reducibles por complemento) y los árboles a partir de los cuales se forman se denominan coárboles. Por lo tanto, las permutaciones separables son exactamente las permutaciones cuyos grafos de permutación son cografos. [6] La caracterización de grafo prohibido de los cografos (son los grafos sin camino inducido de cuatro vértices ) corresponde a los dos patrones prohibidos de cuatro elementos de las permutaciones separables.
Las permutaciones separables también están estrechamente relacionadas con los órdenes parciales serie-paralelo , los conjuntos parcialmente ordenados cuyos gráficos de comparabilidad son los cografos. Al igual que con los cografos y las permutaciones separables, los órdenes parciales serie-paralelo también pueden caracterizarse por subórdenes prohibidos de cuatro elementos. Cada permutación define un orden parcial cuya dimensión de orden es dos, en el que los elementos a ordenar son los elementos de la permutación, y en el que x ≤ y siempre que x tenga un valor numérico menor que y y quede de él en la permutación. Las permutaciones para las que este orden parcial es serie-paralelo son exactamente las permutaciones separables.
Las permutaciones separables también pueden utilizarse para describir particiones jerárquicas de rectángulos en rectángulos más pequeños (los llamados "planos de división", utilizados por ejemplo en el diseño de circuitos integrados ) utilizando los signos positivos y negativos del árbol de separación para describir divisiones horizontales y verticales de un rectángulo en rectángulos más pequeños. [7]
Las permutaciones separables incluyen como caso especial las permutaciones ordenables por pila , que evitan el patrón 231.