Sumas oblicuas y directas de permutaciones

En combinatoria , la suma oblicua y la suma directa de permutaciones son dos operaciones para combinar permutaciones más cortas en otras más largas. Dada una permutación π de longitud m y la permutación σ de longitud n , la suma oblicua de π y σ es la permutación de longitud m  +  n definida por

${\displaystyle (\pi \ominus \sigma )(i)={\begin{cases}\pi (i)+n&{\text{for }}1\leq i\leq m,\\\sigma (i-m)&{\text{for }}m+1\leq i\leq m+n,\end{cases}}}$

y la suma directa de π y σ es la permutación de longitud m  +  n definida por

${\displaystyle (\pi \oplus \sigma )(i)={\begin{cases}\pi (i)&{\text{for }}1\leq i\leq m,\\\sigma (i-m)+m&{\text{for }}m+1\leq i\leq m+n.\end{cases}}}$

Ejemplos

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 iguales a π , mientras que las últimas cinco provienen de desplazar las entradas de σ ).

Sumas de permutaciones comomatrices

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 está dada por ${\displaystyle M_{\pi \ominus \sigma }}$ ${\displaystyle \pi \ominus \sigma }$

${\displaystyle M_{\pi \ominus \sigma }={\begin{bmatrix}0&M_{\pi }\\M_{\sigma }&0\end{bmatrix}}}$,

y la matriz de permutación correspondiente a la suma directa está dada por ${\displaystyle M_{\pi \oplus \sigma }}$ ${\displaystyle \pi \oplus \sigma }$

${\displaystyle M_{\pi \oplus \sigma }={\begin{bmatrix}M_{\pi }&0\\0&M_{\sigma }\end{bmatrix}}}$,

donde aquí se utiliza el símbolo "0" para representar bloques rectangulares de cero entradas. Siguiendo el ejemplo de la sección anterior, tenemos (suprimiendo todas las entradas 0) que

${\displaystyle M_{2413}={\begin{bmatrix}&1&&\\&&&1\\1&&&\\&&1&\end{bmatrix}}}$, , ${\displaystyle M_{35142}={\begin{bmatrix}&&1&&\\&&&&1\\1&&&&\\&&&1&\\&1&&&\end{bmatrix}}}$

${\displaystyle M_{2413\ominus 35142}=M_{796835142}={\begin{bmatrix}&&&&&&1&&&\\&&&&&&&&1\\&&&&&1&&&\\&&&&&&&1&\\&&1&&&&&&\\&&&&1&&&&\\1&&&&&&&&\\&&&1&&&&&\\&1&&&&&&&\end{bmatrix}}}$

y

${\displaystyle M_{2413\oplus 35142}=M_{241379586}={\begin{bmatrix}&1&&&&&&&\\&&&1&&&&&\\1&&&&&&&&\\&&1&&&&&&\\&&&&&&1&&\\&&&&&&&&1\\&&&&1&&&&\\&&&&&&&1&\\&&&&&1&&&\end{bmatrix}}}$.

Papel en la evitación de patrones

Las sumas oblicuas y directas de permutaciones aparecen (entre otros lugares) en el estudio de la evitación de patrones en permutaciones. Descomponer las permutaciones en sumas oblicuas y/o directas de un número máximo de partes (es decir, descomponerlas en partes indecomponibles) es una de las diversas técnicas posibles que se utilizan para estudiar la estructura de las clases de patrones y, por lo tanto, enumerarlas. ^{[1] [2] [3]}

Las permutaciones cuya descomposición por sumas oblicuas y 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 clasificabilidad, y también pueden caracterizarse como permutaciones que evitan los patrones de permutación 2413 y 3142.

Propiedades

Las sumas oblicuas y directas son asociativas pero no conmutativas , y no se asocian entre sí (es decir, para las permutaciones π , σ y τ normalmente tenemos ). ${\displaystyle \pi \oplus (\sigma \ominus \tau )\neq (\pi \oplus \sigma )\ominus \tau }$

Dadas las permutaciones π y σ , tenemos

${\displaystyle (\pi \oplus \sigma )^{-1}=\pi ^{-1}\oplus \sigma ^{-1}}$   y   . ${\displaystyle (\pi \ominus \sigma )^{-1}=\sigma ^{-1}\ominus \pi ^{-1}}$

Dada una permutación ω , defina su reverso rev( ω ) como la permutación cuyas entradas aparecen en el orden opuesto a las de ω cuando se escribe en notación de una línea ; por ejemplo, el reverso de 25143 es 34152. (Como matrices de permutación, esta operación es una reflexión a través de un eje horizontal). Entonces, las sumas oblicua y directa de las permutaciones están relacionadas por

${\displaystyle \pi \oplus \sigma =\operatorname {rev} (\operatorname {rev} (\sigma )\ominus \operatorname {rev} (\pi ))}$.

Referencias

1. Michael Albert y MD Atkinson, Clases de patrones y colas de prioridad, arXiv :1202.1542v1
2. MD Atkinson, Bruce E. Sagan , Vincent Vatter, Contando (3+1) - Evitando permutaciones, European Journal of Combinatorics, arXiv :1102.5568v1
3. Albert, MH y Atkinson, MD Permutaciones simples y permutaciones restringidas por patrones. Matemáticas discretas. 300, 1-3 (2005), 1–15.
4. Kitaev (2011) pág. 57

• Kitaev, Sergey (2011). Patrones en permutaciones y palabras . Monografías en informática teórica. Serie EATCS. ​​Berlín: Springer-Verlag . ISBN. 978-3-642-17332-5.Zbl 1257.68007  .