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

---

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

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

Если M _π и M _σ — матрицы перестановок, соответствующие π и σ соответственно, то матрица перестановок, соответствующая косой сумме , имеет вид${\ Displaystyle М _ {\ пи \ оминус \ сигма}}$${\ Displaystyle \ пи \ оминус \ сигма}$

а матрица перестановок, соответствующая прямой сумме , имеет вид${\ Displaystyle М _ {\ пи \ оплюс \ сигма}}$${\ Displaystyle \ пи \ оплюс \ сигма}$

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

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

---