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

В комбинаторике косая сумма и прямая сумма перестановок — это две операции по объединению более коротких перестановок в более длинные. Если даны перестановка π длины m и перестановка σ длины n , косая сумма π и σ — это перестановка длины m  +  n, определяемая как

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

а прямая сумма π и σ — это перестановка длины 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" используется для представления прямоугольных блоков нулевых записей. Следуя примеру предыдущего раздела, мы имеем (подавление всех нулевых записей), что

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

Ссылки

1. Майкл Альберт и МД Аткинсон, Классы шаблонов и очереди приоритетов, arXiv :1202.1542v1
2. М. Д. Аткинсон, Брюс Э. Саган , Винсент Ваттер, Подсчет (3+1) — Избегание перестановок, Европейский журнал комбинаторики, arXiv :1102.5568v1
3. Альберт, М. Х. и Аткинсон, М. Д. Простые перестановки и перестановки с ограничениями по шаблону. Дискретная математика. 300, 1-3 (2005), 1–15.
4. Китаев (2011) стр.57

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