En combinatoria , la suma asimétrica y la suma directa de permutaciones son dos operaciones para combinar permutaciones más cortas en más largas. Dada una permutación π de longitud my la permutación σ de longitud n , la suma de sesgo de π y σ es la permutación de la longitud m + n definida por
y la suma directa de π y σ es la permutación de la longitud m + n definida por
Ejemplos de
La suma sesgada de las permutaciones π = 2413 y σ = 35142 es 796835142 (las últimas cinco entradas son iguales a σ , mientras que las primeras cuatro entradas provienen de desplazar las entradas de π ) mientras que su suma directa es 241379586 (las primeras cuatro entradas son igual a π , mientras que los últimos cinco provienen de desplazar las entradas de σ ).
Sumas de permutaciones como matrices
Si M π y M σ son las matrices de permutación correspondientes a π y σ , respectivamente, entonces la matriz de permutación correspondiente a la suma sesgada es dado por
- ,
y la matriz de permutación correspondiente a la suma directa es dado por
- ,
donde aquí el símbolo "0" se utiliza para representar bloques rectangulares de entradas cero. Siguiendo el ejemplo de la sección anterior, tenemos (suprimiendo las 0 entradas) que
- , ,
y
- .
Papel en la evitación de patrones
Las sumas de permutaciones sesgadas y directas aparecen (entre otros lugares) en el estudio de la evitación de patrones en las permutaciones. Dividir permutaciones como sesgos y / o sumas directas de un número máximo de partes (es decir, descomponerse en partes indecomponibles) es una de las varias técnicas posibles que se utilizan para estudiar la estructura de, y así enumerar, clases de patrones. [1] [2] [3]
Las permutaciones cuya descomposición por sesgo y sumas directas en un número máximo de partes, es decir, pueden construirse a partir de las permutaciones (1), se denominan permutaciones separables ; [4] surgen en el estudio de la teoría de ordenabilidad, y también se pueden caracterizar como permutaciones que evitan los patrones de permutación 2413 y 3142.
Propiedades
Las sumas sesgadas y directas son asociativas pero no conmutativas , y no se asocian entre sí (es decir, para las permutaciones π , σ y τ normalmente tenemos).
Dadas las permutaciones π y σ , tenemos
- y .
Dada una permutación ω , defina su rev inversa ( ω ) como la permutación cuyas entradas aparecen en el orden opuesto a las de ω cuando se escriben en notación de una línea ; por ejemplo, el reverso de 25143 es 34152. (Como matrices de permutaciones, esta operación es una reflexión a través de un eje horizontal). Entonces la asimetría y las sumas directas de permutaciones están relacionadas por
- .
Referencias
- ^ Michael Albert y MD Atkinson, clases de patrones y colas de prioridad, arXiv : 1202.1542v1
- ^ MD Atkinson, Bruce E. Sagan , Vincent Vatter, Contando (3 + 1) - Evitar permutaciones, European Journal of Combinatorics, arXiv : 1102.5568v1
- ^ Albert, MH y Atkinson, MD Permutaciones simples y permutaciones de patrones restringidos. Matemáticas discretas. 300, 1-3 (2005), 1-15.
- ↑ Kitaev (2011) p.57
- Kitaev, Sergey (2011). Patrones en permutaciones y palabras . Monografías en Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . ISBN 978-3-642-17332-5. Zbl 1257.68007 .