Šikmý a přímý součet obměn - Skew and direct sums of permutations

v kombinatorika, šikmá suma a přímý součet z obměny jsou dvě operace, které kombinují kratší permutace do delších. Vzhledem k obměně π délky m a obměna σ délky n, šikmý součet π a σ je permutace délky m + n definován

${ displaystyle ( pi ominus sigma) (i) = { začátek {případy} pi (i) + n & { text {pro}} 1 leq i leq m, sigma (im) & { text {for}} m + 1 leq i leq m + n, end {případy}}}$

a přímý součet π a σ je permutace délky m + n definován

${ displaystyle ( pi oplus sigma) (i) = { začít {případy} pi (i) & { text {pro}} 1 leq i leq m, sigma (im) + m & { text {for}} m + 1 leq i leq m + n. end {případy}}}$

Příklady

Zkosený součet permutací π = 2413 a σ = 35142 je 796835142 (posledních pět položek se rovná σ, zatímco první čtyři položky pocházejí z posunutí položek z π), zatímco jejich přímý součet je 241379586 (první čtyři položky se rovnají π, zatímco posledních pět pochází z posunu položek σ).

Součty permutací jako matice

Li M_π a M_σ jsou permutační matice souhlasí s π a σ, respektive pak permutační matice ${ displaystyle M _ { pi ominus sigma}}$ odpovídající součtu zkosení ${ displaystyle pi ominus sigma}$ darováno

${ displaystyle M _ { pi ominus sigma} = { begin {bmatrix} 0 & M _ { pi} M _ { sigma} & 0 end {bmatrix}}}$,

a permutační matice ${ displaystyle M _ { pi oplus sigma}}$ odpovídající přímému součtu ${ displaystyle pi oplus sigma}$ darováno

${ displaystyle M _ { pi oplus sigma} = { begin {bmatrix} M _ { pi} & 0 0 & M _ { sigma} end {bmatrix}}}$,

kde zde symbol "0" slouží k reprezentaci obdélníkových bloků nulových záznamů. V návaznosti na příklad z předchozí části to máme (potlačení všech 0 položek)

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

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

a

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

Role ve vyhýbání se vzorům

Šikmé a přímé sumy permutací se objevují (mimo jiné) při studiu vyhýbání se vzorům v permutacích. Rozdělení permutací jako zkosení a / nebo přímé součty maximálního počtu částí (tj. Rozložení na nerozložitelné části) je jednou z několika možných technik používaných ke studiu struktury a výčtu tříd vzorů.^[1][2][3]

Permutace, jejichž rozklad zešikmením a přímými součty na maximální počet částí, to znamená, že mohou být vytvořeny z permutací (1), se nazývají oddělitelné obměny;^[4] vznikají při studiu teorie tříditelnosti a lze je také charakterizovat jako permutace vyhýbající se permutační vzory 2413 a 3142.

Vlastnosti

Šikmý a přímý součet jsou asociativní ale ne komutativní, a nespojují se navzájem (tj. pro permutace π, σ a τ obvykle máme ${ Displaystyle pi oplus ( sigma ominus tau) neq ( pi oplus sigma) ominus tau}$).

Vzhledem k obměnám π a σ, my máme

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

Vzhledem k obměně ω, definovat jeho zvrátit rev (ω) být permutace, jejíž položky se objevují v opačném pořadí než v ω když je napsán v jednorázová notace; například reverz 25143 je 34152. (Jako permutační matice je tato operace odrazem přes vodorovnou osu.) Potom jsou šikmé a přímé součty permutací spojeny

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

Reference

• Kitaev, Sergey (2011). Vzory v permutacích a slovech. Monografie v teoretické informatice. Řada EATCS. Berlín: Springer-Verlag. ISBN  978-3-642-17332-5. Zbl  1257.68007.