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

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

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

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

$(\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 _σ — матрицы перестановок, соответствующие π и σ соответственно, то матрица перестановок $M_{\pi \ominus \sigma }$ что соответствует косой сумме $\pi \ominus \sigma$ дается

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

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

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

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

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

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

и

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

Роль в избегании шаблонов

Асимметрия и прямые суммы перестановок появляются (среди прочего) при изучении избегания шаблонов в перестановках. Разложение перестановок на асимметричные и/или прямые суммы максимального числа частей (то есть разложение на неразложимые части) — это один из нескольких возможных методов, используемых для изучения структуры классов шаблонов и, следовательно, для их перечисления.

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

Характеристики

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

Учитывая перестановки π и σ , мы имеем

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

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

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

Ссылки

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