順列の歪と直和

組合せ論では、順列の歪和と直和は、短い順列を長い順列に結合する2つの演算である。長さmの順列πと長さnの順列σが与えられたとき、 πとσの歪和は、次のように定義される 長さm  +  nの順列である。

${\displaystyle (\pi \ominus \sigma )(i)={\begin{cases}\pi (i)+n&{\text{for }}1\leq i\leq m,\\\sigma (im)&{\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 (im)+m&{\text{for }}m+1\leq i\leq m+n.\end{cases}}}$

順列π = 2413 とσ = 35142 の歪度合計は 796835142 です (最後の 5 つのエントリはσに等しく、最初の 4 つのエントリはπのエントリをシフトしたものになります)。一方、それらの直和は 241379586 です (最初の 4 つのエントリはπに等しく、最後の 5 つのエントリはσのエントリをシフトしたものになります)。

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つです。^{[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シリーズ。ベルリン：シュプリンガー・フェアラーク。ISBN 978-3-642-17332-5.ZBL1257.68007  。​