Loading article…
組み合わせ数学や理論計算機科学では、（古典的な）順列パターンは、より長い順列の部分順列です。任意の順列は、123... という数列に順列を適用した結果を表すエントリのシーケンスとして、 1 行の表記で記述できます。たとえば、213 という数列は、3 つの要素の順列で、要素 1 と 2 を入れ替える順列を表します。π と σ がこのように表現された 2 つの順列である場合 (これらの変数名は順列の標準であり、数piとは関係ありません)、π のエントリの何らかの部分列が σ のすべてのエントリと同じ相対順序を持つ場合、 π はパターンとして σを含んでいると言われます。
例えば、順列 π には、π 内に x ... y ... z の順序で現れる 3 つのエントリ x 、 y 、 z があり、それらの値が順列y < x < zの順序になっている場合、順列213にパターン 213 が含まれます。
5 つの要素からなる順列 32415 は、いくつかの異なる方法で 213 をパターンとして含んでいます。3··15、··415、32··5、324··、および·2·15 はすべて、213 と同じ順序のエントリの 3 つ組を形成します。エントリは連続している必要はありません。部分列 315、415、325、324、および 215 はそれぞれ、パターンのコピー、インスタンス、または出現と呼ばれます。π が σ を含むという事実は、より簡潔に σ ≤ πと記述されます。
順列πがパターンσを含まない場合、πはσを回避すると言われます。順列51342は213を回避します。この順列には3つの要素からなる10個の部分列がありますが、これらの10個の部分列のいずれも213と同じ順序ではありません。
順列パターンおよび関連トピックを専門とする国際会議が、2003年から毎年開催されており、「順列パターン」と呼ばれている。
パーシー・マクマホン（1915年）が「格子順列」の研究でこの分野における最初の結果を証明したと言えるだろう。 [ 1 ] 特にマクマホンは、2つの減少部分列に分割できる順列（つまり、123を避ける順列）はカタラン数で数えられることを示した。[ 2 ]
この分野におけるもう一つの初期の画期的な成果は、エルデシュ・セケレスの定理です。順列パターンの言語で言えば、この定理は、任意の正の整数aとbに対して、長さが少なくとも の順列はすべて である と述べています。パターンが含まれている必要がありますまたはパターン。
順列パターンの研究は、ドナルド・クヌースが1968年にスタックソートについて考察したことから本格的に始まった。 [ 3 ]クヌースは、順列πがスタック でソートできるのはπが231を避ける場合のみであり、スタックでソート可能な順列はカタラン数で列挙されることを示した。[ 4 ] クヌースはまた、デックによるソートについても疑問を呈した。特に、デックを使用してn個の要素の順列がいくつ得られるかというクヌースの疑問は未解決のままである。 [ 5 ] その後まもなく、ロバート・タージャン( 1972 )はスタックのネットワークによるソートを調査し、[ 6 ]ヴォーン・プラット( 1973 )は、すべてのkに対してπ が 5,2,7,4,...,4 k +1,4 k − 2,3,4 k ,1、および 5,2,7,4 ,...,4 k +3,4 k , 1,4 k +2,3 、そしてこれらのどちらかから最後の 2 つの要素または 1 と 2 を入れ替えることで得られるすべての順列を避ける場合に限り、順列 πをデックでソートできることを示した。 [ 7 ] この順列の集合は無限であるため (実際、これは無限の順列の反連鎖の最初の公表例である)、順列がデックでソートできるかどうかを判断するのにどれくらいの時間がかかるかはすぐには明らかではない。 ローゼンスティールとタージャン（1984）は後に、π をデックでソートできるかどうかを判定する線形時間（π の長さに対して）のアルゴリズムを発表した。[ 8 ]
プラットは論文の中で、この順列パターンの順序は「単純かつ自然な方法で生じる順列上の唯一の部分順序であるように思われる」と述べ、最後に「抽象的な観点から見ると」、順列パターンの順序は「我々が特徴付けていたネットワークよりもさらに興味深い」と結論付けている。[ 7 ]
順列パターンの研究における重要な目標は、固定された（そして通常は短い）順列または順列の集合を避ける順列を列挙することです。Av n (B) を、集合B内のすべての順列を避ける長さnの順列の集合とします。（ Bが単一集合、例えば { β }の場合、代わりに略語 Av n ( β ) を使用します。）上記のように、MacMahon と Knuth は、|Av n (123)| = |Av n (231)| = C n、n番目のカタラン数であることを示しました。したがって、これらは同型の組み合わせクラスです。
Simion & Schmidt (1985)は、列挙のみに焦点を当てた最初の論文でした。Simion と Schmidt は、他の結果の中でも、長さ 3 のパターンを避ける偶数順列と奇数順列の数を数え、長さ 3 の 2 つのパターンを避ける順列の数を数え、123 と 231 を避ける順列が同数であることを初めて全単射的に証明しました。[ 9 ] 彼らの論文以降、他の多くの全単射が与えられており、概説についてはClaesson & Kitaev (2008)を参照してください。 [ 10 ]
一般に、すべてのnに対して |Av n ( β )| = |Av n ( σ )|が成り立つ場合、βとσはWilf 同値であると言われます。多くの Wilf 同値は、すべての n に対して |Av n ( β )| = |Av n ( β − 1 )| = |Av n ( β rev )|が成り立つという自明な事実から生じます。ここで、β − 1はβの逆行列、β rev はβの逆行列を表します。（これらの 2 つの操作は、置換行列に自然な作用を持つ二面体群 D 8を生成します。）しかし、自明でない Wilf 同値の例も多数存在します（例えば、123 と 231 の間の同値など）。
これら2つのウィルフ同値性と逆対称性および反転対称性から、βの長さが4である3つの異なるシーケンス|Av n ( β )|が存在することがわかる。
1980年代後半、リチャード・スタンレーとハーバート・ウィルフは、任意の順列βに対して、|Av n ( β )| < K nとなる定数Kが存在すると予想した。これは、アダム・マーカスとガボール・タルドスによって証明されるまで、スタンレー・ウィルフ予想として知られていた。[ 16 ]
順列クラス（パターンクラス（主に古い文献で）とも呼ばれる）または単に順列のクラスは、順列パターン順序のダウンセットです。すべてのクラスは、そのクラス内に含まれない最小の順列、つまりその基底によって定義できます。したがって、スタックソート可能な順列の基底は {231} ですが、デックソート可能な順列の基底は無限であることが知られています。クラスの生成関数は Σ x |π|で、和はクラス内のすべての順列 π について取られます。
包含順序による順列の集合は半順序集合を形成するため、そのメビウス関数について問うのは自然なことであり、この目標はWilf (2002)によって初めて明示的に提示された。[ 17 ] このような研究の目標は、順列パターン半順序集合内の区間[σ, π]のメビウス関数の公式を、素朴な再帰的定義よりも効率的に見つけることである。このような最初の結果はSagan & Vatter (2006)によって確立され、彼らは階層化された順列の区間のメビウス関数の公式を与えた。[ 18 ] その後、Bursteinら(2011)はこの結果を分離可能な順列の区間に一般化した。[ 19 ]
漸近的に、長さnのすべての順列 π の少なくとも 39.95% がμ(1, π)=0 (つまり、主メビウス関数がゼロに等しい) を満たすことが知られています[ 20 ]。しかし、各nに対して、μ(1, π) がnの指数関数となるような順列 π が存在します[ 21 ]。
順列が与えられた場合（テキストと呼ばれる）長さそして別の順列長さ（パターンと呼ばれる）順列パターンマッチング（PPM）問題は、に含まれる両方そしては変数とみなされ、この問題はNP完全であることが知られており、そのような一致の数を数える問題は#P完全である。[ 22 ]しかし、 kが定数の場合、PPMは線形時間で解くことができる。実際、GuillemotとMarx [ 23 ]は、PPMは時間で解けることを示した。つまり、固定パラメータに関して扱いやすいということです。。
ブルーナーとラックナーが調査したように、PPM問題にはいくつかの変種が存在する。[ 24 ]例えば、一致が連続したエントリで構成される必要がある場合、この問題は多項式時間で解くことができる。[ 25 ]パターンを適切な順列クラスに制限すると、別の自然な変種が得られる。この問題は、-パターンPPMは、分離可能な順列に対して多項式時間で解けることが示されました。[ 22 ]後に、JelínekとKynčl [ 26 ]は、の複雑さを完全に解決しました。-パターンPPMが多項式時間で解けることを示す1、12、21、132、231、312、213のいずれかに等しく、それ以外の場合はNP完全である。
別のバリエーションとしては、パターンとテキストの両方が適切な順列クラスに制限されている場合がある。この場合、問題は-PPM。例えば、GuillemotとVialette [ 27 ]は、-PPMは解決できる時間。アルバート、ラックナー、ラックナー、ヴァッター[ 28 ]は後にこれを下げてそして、同じ境界が歪んだマージされた順列のクラスにも成り立つことを示した。さらに、-PPM問題は、固定されたすべての適切な順列クラスに対して多項式時間で解くことができる。この質問に対して、イェリネクとキンクルは否定的な回答を示し、-PPM は実際には NP 完全です。[ 26 ]その後、イェリネク、オプラー、ペカレク[ 29 ]は次のことを示した。-PPMは、いかなる場合でもNP完全である長さが少なくとも4であり、3412、3142、4213、4123、または41352のいずれとも対称ではない。
順列 π は、π と同じ長さのどの順列も β のコピーを多く含まない場合、 β最適であると言われます。1992 年の SIAM 離散数学会議での講演で、Wilf は長さkの順列 β の充填密度を次のように定義しました。
フレッド・ガルビンの未発表の議論によれば、この極限内の量はn ≥ kに対して非増加であり、したがって極限が存在する。β が単調である場合、その充填密度は明らかに 1 であり、充填密度は逆と反転によって生成される対称群の下で不変であるため、長さ 3 の順列には、非自明な充填密度が 1 つだけ存在する。ウォルター・ストロムクイスト (未発表) は、132 の充填密度が2 √ 3 − 3 、約 0.46410 であることを示すことでこの問題を解決した。
長さが4の順列βについては、（対称性により）考慮すべきケースが7つあります。
3 つの未知の順列については、境界と推測があります。Price (1997) は、 1324 の充填密度が約 0.244 であることを示唆する近似アルゴリズムを使用しました。 [ 30 ] Birzhan Batkeyev (未発表) は、1342 の充填密度が少なくとも 132 と 1432 の充填密度の積、約 0.19658 であることを示す順列の族を構築しました。これは、1342 の正確な充填密度であると推測されています。Presutti & Stromquist (2010)は、2413 の充填密度の下限を提供しました。この下限は、積分で表すことができ、約 0.10474 であり、真の充填密度であると推測されています。[ 32 ]
k-スーパーパターンとは、長さkのすべての順列を含む順列のことです。例えば、25314 は長さ 3 の 6 つの順列すべてを含むため、3-スーパーパターンです。k-スーパーパターンの長さは少なくともk 2 / e 2でなければならないことが知られています。ここでe ≈ 2.71828 はオイラー数です[ 33 ]。また、長さ ⌈( k 2 + 1)/2⌉ の k-スーパーパターンが存在することも知られています [ 34 ]。この上限は、低 次の項を除いて、可能な限り最良のものであると推測されています[ 35 ]。
上記で定義した、エントリが連続して出現する必要がないタイプのパターンは、古典的（順列）パターンと呼ばれます。エントリが連続して出現する必要があるパターンは、連続パターンと呼ばれます。
「パターン」という概念は、いくつかの方法で一般化されてきました。たとえば、連結パターンは、隣接するエントリのペアが連続して出現する必要がないことを示すダッシュを含む順列です。たとえば、順列 314265 には、エントリ 3426 と 3425 によって与えられるダッシュパターン 2 − 31 − 4 が 2 つ含まれています。ダッシュパターン β と任意の順列 π に対して、π 内の β のコピーの数を β(π) と書きます。したがって、π 内の反転の数は 2 − 1(π) であり、降下数は 21(π) です。さらに、 π 内の谷の数は 213(π) + 312(π) であり、ピークの数は231(π) + 132(π) です。これらのパターンは、 Babson & Steingrímsson (2000)によって導入され、既知のマホニアン統計のほぼすべてが、連結順列の観点から表現できることが示されました。[ 36 ] 例えば、 π のメジャー指数は 1 − 32(π) + 2 − 31(π) + 3 − 21(π) + 21(π)に等しくなります。
もう1つの一般化は、一部のエントリがバーで囲まれた バー付きパターンです。πがバー付きパターンβを回避するためには、βのバーなしエントリのコピーを形成するπのすべてのエントリの集合を拡張して、βのすべてのエントリのコピーを形成できる必要があります。West (1993)は、スタックを2回通過させることでソートできる順列の研究で、これらのタイプのパターンを導入しました。[ 37 ] (Westのスタックを2回通過させるという定義は、2つのスタックを直列に使用してソートすることと同じではないことに注意してください。) バー付きパターンのもう1つの例は、Bousquet-Mélou & Butler (2007)の研究に見られます。彼らは、 πに対応するシューベルト多様体が局所的に階乗であるのは、πが1324と21 3 54を回避する場合に限ることを示しました。[ 38 ]
