Skew and direct sums of permutations

In combinatorics, the skew sum and direct sum of permutations are two operations to combine shorter permutations into longer ones. Given a permutation π of length m and the permutation σ of length n, the skew sum of π and σ is the permutation of length m + n defined by

${\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}}}$

and the direct sum of π and σ is the permutation of length m + n defined by

${\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}}}$

Examples

The skew sum of the permutations π = 2413 and σ = 35142 is 796835142 (the last five entries are equal to σ, while the first four entries come from shifting the entries of π) while their direct sum is 241379586 (the first four entries are equal to π, while the last five come from shifting the entries of σ).

Sums of permutations as matrices

If M_π and M_σ are the permutation matrices corresponding to π and σ, respectively, then the permutation matrix ${\displaystyle M_{\pi \ominus \sigma }}$ corresponding to the skew sum ${\displaystyle \pi \ominus \sigma }$ is given by

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

and the permutation matrix ${\displaystyle M_{\pi \oplus \sigma }}$ corresponding to the direct sum ${\displaystyle \pi \oplus \sigma }$ is given by

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

where here the symbol "0" is used to represent rectangular blocks of zero entries. Following the example of the preceding section, we have (suppressing all 0 entries) that

${\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}}}$

and

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

Role in pattern avoidance

Skew and direct sums of permutations appear (among other places) in the study of pattern avoidance in permutations. Breaking permutations down as skew and/or direct sums of a maximal number of parts (that is, decomposing into indecomposable parts) is one of several possible techniques used to study the structure of, and so to enumerate, pattern classes.[1][2][3]

Permutations whose decomposition by skew and direct sums into a maximal number of parts, that is, can be built up from the permutations (1), are called separable permutations;[4] they arise in the study of sortability theory, and can also be characterized as permutations avoiding the permutation patterns 2413 and 3142.

Properties

The skew and direct sums are associative but not commutative, and they do not associate with each other (i.e., for permutations π, σ and τ we typically have ${\displaystyle \pi \oplus (\sigma \ominus \tau )\neq (\pi \oplus \sigma )\ominus \tau }$).

Given permutations π and σ, we have

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

Given a permutation ω, define its reverse rev(ω) to be the permutation whose entries appear in the opposite order of those of ω when written in one-line notation; for example, the reverse of 25143 is 34152. (As permutation matrices, this operation is reflection across a horizontal axis.) Then the skew and direct sums of permutations are related by

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

References

1. Michael Albert and M. D. Atkinson, Pattern classes and priority queues, arXiv:1202.1542v1
2. M. D. Atkinson, Bruce E. Sagan, Vincent Vatter, Counting (3+1) - Avoiding permutations, European Journal of Combinatorics, arXiv:1102.5568v1
3. Albert, M.H. and Atkinson, M.D. Simple permutations and pattern restricted permutations. Discrete Math. 300, 1-3 (2005), 1–15.
4. Kitaev (2011) p.57

• Kitaev, Sergey (2011). Patterns in permutations and words. Monographs in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-642-17332-5. Zbl 1257.68007.