Косые и прямые суммы перестановок

В комбинаторике , то перекос сумма и прямая сумма из перестановок две операции , чтобы объединить короткие перестановки в длинные. Учитывая перестановку π длины m и перестановку σ длины n , косая сумма π и σ является перестановкой длины m  +  n, определенной формулой

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

а прямая сумма π и σ - это перестановка длины m  +  n, определяемая формулой

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

Примеры [ править ]

Асимметричная сумма перестановок π = 2413 и σ = 35142 равна 796835142 (последние пять записей равны σ , в то время как первые четыре записи происходят от сдвига элементов π ), а их прямая сумма составляет 241379586 (первые четыре записи равны равно π , а последние пять - в результате сдвига элементов σ ).

Суммы перестановок в виде матриц [ править ]

Если M _π и M _σ - матрицы перестановок, соответствующие π и σ , соответственно, то матрица перестановок, соответствующая асимметричной сумме , задается формулой${\displaystyle M_{\pi \ominus \sigma }}$${\displaystyle \pi \ominus \sigma }$

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

а матрица перестановок, соответствующая прямой сумме, имеет вид${\displaystyle M_{\pi \oplus \sigma }}$${\displaystyle \pi \oplus \sigma }$

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

где здесь символ «0» используется для представления прямоугольных блоков нулевых записей. Следуя примеру предыдущего раздела, мы имеем (подавляя все 0 записей), что

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

а также

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

Роль в избегании шаблонов [ править ]

Косые и прямые суммы перестановок появляются (среди прочего) при изучении избегания паттернов при перестановках. Разбиение перестановок на перекосы и / или прямые суммы максимального числа частей (то есть разложение на неразложимые части) - один из нескольких возможных методов, используемых для изучения структуры и, таким образом, для перечисления классов шаблонов. ^{[1] [2] [3]}

Перестановки, разложение которых косой и прямой суммой на максимальное количество частей, т. Е. Могут быть построены из перестановок (1), называются сепарабельными перестановками ; ^[4] они возникают при изучении теории сортировки, а также могут быть охарактеризованы как перестановки, избегающие шаблонов перестановок 2413 и 3142.

Свойства [ править ]

Косая и прямая суммы ассоциативны, но не коммутативны , и они не связываются друг с другом (т. Е. Для перестановок π , σ и τ, которые мы обычно имеем ).${\displaystyle \pi \oplus (\sigma \ominus \tau )\neq (\pi \oplus \sigma )\ominus \tau }$

Для перестановок π и σ имеем

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

Для данной перестановки ω определим ее обратную rev ( ω ) как перестановку, элементы которой появляются в порядке, обратном порядку записей ω при записи в однострочном виде ; например, обратное 25143 - 34152. (Что касается матриц перестановок, эта операция является отражением по горизонтальной оси.) Тогда перекос и прямые суммы перестановок связаны соотношением

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

Ссылки [ править ]

• Китаев, Сергей (2011). Паттерны в перестановках и словах . Монографии по теоретической информатике. Серия EATCS. Берлин: Springer-Verlag . ISBN 978-3-642-17332-5. Zbl  1257.68007 .