Sum of permutations

Permutation matrices of the direct sum (left) and the skewed sum (right) of two permutations

In combinatorics, a sum of permutations is a link between two permutations , which creates a new permutation. The length of the result permutation corresponds to the sum of the lengths of the two initial permutations. A distinction is made between two ways of summing, the direct sum and the skewed sum . In the case of the direct sum, the second permutation is shifted and appended to the first; in the case of the skewed sum, the first permutation is shifted before the second. The associated permutation matrices have a corresponding block structure .

The formation of purely direct or purely skewed sums of permutations is associative , but the associative law does not generally apply to mixed direct and skewed sums. Sums of complementary or reverse permutations can be represented by sums of the initial permutations. The inverse of a sum of permutations also results as the sum of inverses. Direct and skew sums of permutations play an important role in the decomposition of permutations into their basic building blocks and in the characterization of separable permutations .

definition

Is the symmetric group of permutations of the length and and two permutations in Tupelschreibweise not necessarily the same length, then direct their sum ( English direct sum ) by ${\displaystyle S_{n}}$ ${\displaystyle n}$ ${\displaystyle \pi =(\pi (1),\ldots ,\pi (m))\in S_{m}}$ ${\displaystyle \sigma =(\sigma (1),\ldots ,\sigma (n))\in S_{n}}$

${\displaystyle \pi \oplus \sigma =(\pi (1),\ldots ,\pi (m),~\sigma (1)+m,\ldots ,\sigma (n)+m)\in S_{m+n}}$

and their oblique sum ( English skew sum ) by

${\displaystyle \pi \ominus \sigma =(\pi (1)+n,\ldots ,\pi (m)+n,~\sigma (1),\ldots ,\sigma (n))\in S_{m+n}}$.

Are defined. In tuple notation, the second permutation is attached to the first with a shift of a direct sum and, with a skewed sum, the first permutation is shifted in front of the second. ${\displaystyle m}$ ${\displaystyle n}$

Examples

The direct sum of the two identical permutations and results in ${\displaystyle \pi =(1,2,3,4)\in S_{4}}$ ${\displaystyle \sigma =(1,2,3)\in S_{3}}$

${\displaystyle \pi \oplus \sigma =(1,2,3,4,5,6,7)\in S_{7}}$,

while their crooked sum by

${\displaystyle \pi \ominus \sigma =(4,5,6,7,1,2,3)\in S_{7}}$

given is.

Matrix display

If the permutation matrix belonging to the permutation is , then the permutation matrix is ​​the direct sum of two permutations and a block matrix of the form ${\displaystyle P_{\pi }\in \{0,1\}^{n\times n}}$ ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \pi \in S_{m}}$ ${\displaystyle \sigma \in S_{n}}$

${\displaystyle P_{\pi \oplus \sigma }={\begin{pmatrix}P_{\pi }&0\\0&P_{\sigma }\end{pmatrix}}}$

and the permutation matrix of the corresponding skew sum is a block matrix of the form

${\displaystyle P_{\pi \ominus \sigma }={\begin{pmatrix}0&P_{\pi }\\P_{\sigma }&0\end{pmatrix}}}$.

Here each stands for a zero matrix of the appropriate size. For example, if and , then results ${\displaystyle 0}$ ${\displaystyle \pi =(3,1,2)\in S_{3}}$ ${\displaystyle \sigma =(2,1)\in S_{2}}$

${\displaystyle P_{\pi \oplus \sigma }={\begin{pmatrix}0&0&1&~0&0\\1&0&0&~0&0\\0&1&0&~0&0\\[2mm]0&0&0&~0&1\\0&0&0&~1&0\\\end{pmatrix}}}$   and   . ${\displaystyle P_{\pi \ominus \sigma }={\begin{pmatrix}0&0&~0&0&1\\0&0&~1&0&0\\0&0&~0&1&0\\[2mm]0&1&~0&0&0\\1&0&~0&0&0\\\end{pmatrix}}}$

properties

Associativity

Associativity of direct sums of permutations

The formation of purely direct and purely skewed sums is associative , i.e. for permutations , and applies ${\displaystyle \pi \in S_{m}}$ ${\displaystyle \sigma \in S_{n}}$ ${\displaystyle \tau \in S_{k}}$

${\displaystyle (\pi \oplus \sigma )\oplus \tau =\pi \oplus (\sigma \oplus \tau )}$

and

${\displaystyle (\pi \ominus \sigma )\ominus \tau =\pi \ominus (\sigma \ominus \tau )}$.

For mixed direct and skew sums, however, the associative law does not generally apply, as in the example

${\displaystyle ((1)\oplus (1))\ominus (1))=(2,3,1)\neq (1,3,2)=(1)\oplus ((1)\ominus (1))}$

shows. The commutative law is also generally not fulfilled.

Symmetries

Horizontal and vertical reflections of the sum of the permutations (3,2,1) and (1,2,3)

The permutation complementary to a permutation is . For the complement of the sum of two permutations and holds ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$ ${\displaystyle \pi \in S_{m}}$ ${\displaystyle \sigma \in S_{n}}$

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

such as

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

Correspondingly, the permutation is reverse to a permutation . For the reverse of the sum of two permutations and applies ${\displaystyle \pi \in S_{n}}$ ${\displaystyle \pi '=(\pi (n),\pi (n-1),\ldots ,\pi (1))}$ ${\displaystyle \pi \in S_{m}}$ ${\displaystyle \sigma \in S_{n}}$

${\displaystyle (\pi \oplus \sigma )'=\sigma '\ominus \pi '}$

such as

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

The associated permutation matrices are mirrored accordingly on a horizontal or vertical axis.

Inverse

For the inverse of the sum of two permutations and results ${\displaystyle \pi \in S_{m}}$ ${\displaystyle \sigma \in S_{n}}$

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

such as

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

The associated permutation matrices are mirrored, i.e. transposed , on the main diagonal .

use

Block structuring of the permutation matrix of the separable permutation (4,3,5,1,2,7,8,6)

In combinatorics, direct and skewed sums play an important role in breaking down permutations into their basic building blocks. However, due to the associativity of the summation, such a decomposition is not necessarily unique. Those permutations that can be represented completely as a direct or skewed sum of trivial permutations are called separable permutations . The number of separable permutations of the length is indicated by the (large) Schröder numbers (sequence A006318 in OEIS ). Separable permutations are characterized by a special recursive block structure of the associated permutation matrices. They are examined , among other things, in sorting theory. ${\displaystyle n}$ ${\displaystyle S_{n}}$

Direct and oblique totals also occur in the study of Permutationsmustern ( English permutation pattern on). The decomposition of permutations into partial permutations that cannot be further decomposed allows the characterization and enumeration of certain pattern classes.

See also

• Direct sum of vector spaces
• Direct product of groups and other algebraic structures

literature

• Miklós Bóna : Combinatorics of Permutations (=  Discrete Mathematics and Its Applications . No. 72 ). 2nd Edition. CRC Press, 2012, ISBN 1-4398-5051-8 .
• Sergey Kitaev: Patterns in Permutations and Words (=  Monographs in theoretical computer science ). Springer, 2011, ISBN 978-3-642-17333-2 .

Individual evidence

1. ^ S. Kitaev: Patterns in Permutations and Words . Springer, 2011, p. 57 .
2. ↑ D. Avis, M. Newborn: On pop stacks in series . In: Utilitas Mathematica . No. 19 , 1981, p. 129-140 .
3. ^ P. Bose, JF Buss, A. Lubiw: Pattern matching for permutations . In: Information Processing Letters . tape 65 , 1998, pp. 277-283 .