特定の順列クラスの列挙

順列パターンの研究において、特定の順列類、特に基底元が比較的少ない順列類を列挙することには大きな関心が寄せられてきました。この研究分野では、一見無関係に見える2つの順列類が、それぞれの長さの順列の数が同じであるという、ウィルフ同値性の予期せぬ例が明らかになりました。

長さ3のパターンを1つ避けるクラス

長さ 3 の単一順列には、 2 つの対称クラスと 1 つのWilf クラスがあります。

β	Av _n (β)を列挙するシーケンス	OEIS	シーケンスの種類	正確な列挙参照
123 231	1、2、5、14、42、132、429、1430、…	A000108	代数的（非有理的）gf カタラン数	マクマホン（1916）クヌース（1968）

長さ4のパターンを1つ避けるクラス

長さ 4 の単一順列には、7 つの対称クラスと 3 つの Wilf クラスがあります。

β	Av _n (β)を列挙するシーケンス	OEIS	シーケンスの種類	正確な列挙参照
1342 2413	1、2、6、23、103、512、2740、15485、…	A022558	代数的（非有理的）gf	ボナ（1997）
1234 1243 1432 2143	1、2、6、23、103、513、2761、15767、...	A005802	ホロノミック（非代数的）GF	ゲッセル（1990）
1324	1、2、6、23、103、513、2762、15793、…	A061552

1324-回避順列を数える非再帰的公式は知られていない。再帰的公式はMarinov & Radoičić (2003)によって与えられた。関数方程式を用いたより効率的なアルゴリズムはJohansson & Nakamura (2014)によって与えられ、これはConway & Guttmann (2015)によって改良され、さらにConway, Guttmann & Zinn-Justin (2018)によって改良され、列挙の最初の50項が与えられた。Bevan et al. (2020)は現在、このクラスの成長率の下限と上限を厳密に確立した最良の方法を持っており、この成長率は区間 [10.271, 13.5] にあることを確立した。

長さ3の2つのパターンを避けるクラス

対称性クラスは 5 つ、ウィルフクラスは 3 つあり、それらはすべてSimion & Schmidt (1985)に列挙されています。

B	Av _nを列挙するシーケンス(B)	OEIS	シーケンスの種類
123, 321	1、2、4、4、0、0、0、0、...	該当なし	有限
213、321	1、2、4、7、11、16、22、29、...	A000124	多項式、 ${n \choose 2}+1$
231, 321 132, 312 231, 312	1、2、4、8、16、32、64、128、...	A000079	有理数gf、 $2^{n-1}$

長さ3のパターンと長さ4のパターンを避けるクラス

対称性類は18種類、ウィルフ類は9種類存在し、すべて列挙されている。これらの結果については、Atkinson (1999)またはWest (1996)を参照のこと。

B	Av _nを列挙するシーケンス(B)	OEIS	シーケンスの種類
321, 1234	1、2、5、13、25、25、0、0、...	該当なし	有限
321, 2134	1、2、5、13、30、61、112、190、...	A116699	多項式
132, 4321	1、2、5、13、31、66、127、225、...	A116701	多項式
321, 1324	1、2、5、13、32、72、148、281、…	A179257	多項式
321, 1342	1、2、5、13、32、74、163、347、...	A116702	有理数系ガールフレンド
321, 2143	1、2、5、13、33、80、185、411、...	A088921	有理数系ガールフレンド
132, 4312 132, 4231	1、2、5、13、33、81、193、449、…	A005183	有理数系ガールフレンド
132, 3214	1、2、5、13、33、82、202、497、...	A116703	有理数系ガールフレンド
321、2341 321、3412 321、3142 132、1234 132、4213 132、4123 132、3124 132、2134 132、3412	1、2、5、13、34、89、233、610、...	A001519	有理数ff、交互フィボナッチ数列

長さ4の2つのパターンを避けるクラス

対称類は56種類、ウィルフ同値類は38種類存在する。これらのうち、番号が付けられていないのは3種類だけであり、それらの生成関数はいかなる代数微分方程式（ADE）も満たさないとAlbertら（2018）によって予想されている。特に、彼らの予想は、これらの生成関数がD有限ではないことを意味する。

右側には、 Albert et al. (2024)による、非有限クラスの各ヒートマップが示されています。各クラスには辞書式最小対称性が用いられ、クラスは辞書式順序で並べられています。各ヒートマップを作成するために、長さ300の順列100万個がクラスから一様にランダムに抽出されました。点の色は、インデックスに値を持つ順列の数を表しています。より高解像度のバージョンはPermPalで入手できます。 $(i,j)$ $j$ $i$

B	Av _nを列挙するシーケンス(B)	OEIS	シーケンスの種類	正確な列挙参照
4321, 1234	1、2、6、22、86、306、882、1764、...	A206736	有限	エルデシュ・シェケレスの定理
4312, 1234	1、2、6、22、86、321、1085、3266、…	A116705	多項式	クレメルとシウ (2003) ;ヴァッター (2006)
4321, 3124	1、2、6、22、86、330、1198、4087、…	A116708	有理数系ガールフレンド	クレメルとシウ (2003) ;ヴァッター (2006)
4312, 2134	1、2、6、22、86、330、1206、4174、…	A116706	有理数系ガールフレンド	クレメルとシウ (2003) ;ヴァッター (2006)
4321, 1324	1、2、6、22、86、332、1217、4140、…	A165524	多項式	ヴァッター（2012）
4321, 2143	1、2、6、22、86、333、1235、4339、...	A165525	有理数系ガールフレンド	アルバート、アトキンソン＆ブリグナル（2012）
4312, 1324	1、2、6、22、86、335、1266、4598、…	A165526	有理数系ガールフレンド	アルバート、アトキンソン＆ブリグナル（2012）
4231, 2143	1、2、6、22、86、335、1271、4680、…	A165527	有理数系ガールフレンド	アルバート、アトキンソン＆ブリグナル（2011）
4231, 1324	1、2、6、22、86、336、1282、4758、…	A165528	有理数系ガールフレンド	アルバート、アトキンソン、ヴァッター (2009)
4213, 2341	1、2、6、22、86、336、1290、4870、…	A116709	有理数系ガールフレンド	クレメルとシウ (2003) ;ヴァッター (2006)
4312, 2143	1、2、6、22、86、337、1295、4854、…	A165529	有理数系ガールフレンド	アルバート、アトキンソン＆ブリグナル（2012）
4213, 1243	1、2、6、22、86、337、1299、4910、…	A116710	有理数系ガールフレンド	クレメルとシウ (2003) ;ヴァッター (2006)
4321, 3142	1、2、6、22、86、338、1314、5046、…	A165530	有理数系ガールフレンド	ヴァッター（2012）
4213, 1342	1、2、6、22、86、338、1318、5106、…	A116707	有理数系ガールフレンド	クレメルとシウ (2003) ;ヴァッター (2006)
4312, 2341	1、2、6、22、86、338、1318、5110、…	A116704	有理数系ガールフレンド	クレメルとシウ (2003) ;ヴァッター (2006)
3412, 2143	1、2、6、22、86、340、1340、5254、…	A029759	代数的（非有理的）gf	アトキンソン（1998）
4321, 4123 4321, 3412 4123, 3214 4123, 2143	1、2、6、22、86、342、1366、5462、…	A047849	有理数系ガールフレンド	クレマー＆シウ（2003）
4123, 2341	1、2、6、22、87、348、1374、5335、...	A165531	代数的（非有理的）gf	アトキンソン、セーガン、ヴァッター (2012)
4231, 3214	1、2、6、22、87、352、1428、5768、…	A165532	代数的（非有理的）gf	マイナー（2016）
4213, 1432	1、2、6、22、87、352、1434、5861、…	A165533	代数的（非有理的）gf	マイナー（2016）
4312, 3421 4213, 2431	1、2、6、22、87、354、1459、6056、…	A164651	代数的（非有理的）gf	Le (2005)はWilf同値性を証明し、Callan (2013a)は gfを確立した。
4312, 3124	1、2、6、22、88、363、1507、6241、…	A165534	代数的（非有理的）gf	パントン（2017）
4231, 3124	1、2、6、22、88、363、1508、6255、…	A165535	代数的（非有理的）gf	アルバート、アトキンソン、ヴァッター (2014)
4312, 3214	1、2、6、22、88、365、1540、6568、...	A165536	代数的（非有理的）gf	マイナー（2016）
4231, 3412 4231, 3142 4213, 3241 4213, 3124 4213, 2314	1、2、6、22、88、366、1552、6652、…	A032351	代数的（非有理的）gf	ボナ（1998）
4213, 2143	1、2、6、22、88、366、1556、6720、…	A165537	代数的（非有理的）gf	ベヴァン（2016b）
4312, 3142	1、2、6、22、88、367、1568、6810、…	A165538	代数的（非有理的）gf	アルバート、アトキンソン、ヴァッター (2014)
4213, 3421	1、2、6、22、88、367、1571、6861、…	A165539	代数的（非有理的）gf	ベヴァン（2016a）
4213, 3412 4123, 3142	1、2、6、22、88、368、1584、6968、...	A109033	代数的（非有理的）gf	ル（2005）
4321, 3214	1、2、6、22、89、376、1611、6901、…	A165540	代数的（非有理的）gf	ベヴァン（2016a）
4213, 3142	1、2、6、22、89、379、1664、7460、…	A165541	代数的（非有理的）gf	アルバート、アトキンソン、ヴァッター (2014)
4231, 4123	1、2、6、22、89、380、1677、7566、…	A165542	ADEを満たさないと推測される。Albert et al. (2018)を参照。
4321, 4213	1、2、6、22、89、380、1678、7584、…	A165543	代数的（非有理的）gf	Callan (2013b) ; Bloom & Vatter (2016)も参照
4123, 3412	1、2、6、22、89、381、1696、7781、…	A165544	代数的（非有理的）gf	マイナー＆パントン（2018）
4312, 4123	1、2、6、22、89、382、1711、7922、…	A165545	ADEを満たさないと推測される。Albert et al. (2018)を参照。
4321, 4312 4312, 4231 4312, 4213 4312, 3412 4231, 4213 4213, 4132 4213, 4123 4213, 2413 4213, 3214 3142, 2413	1、2、6、22、90、394、1806、8558、…	A006318	シュレーダー数代数的（非有理的）gf	クレマー（2000）；クレマー（2003）も参照
3412, 2413	1、2、6、22、90、395、1823、8741、…	A165546	代数的（非有理的）gf	マイナー＆パントン（2018）
4321, 4231	1、2、6、22、90、396、1837、8864、…	A053617	ADEを満たさないと推測される。Albert et al. (2018)を参照。

参照

参考文献

アルバート、マイケル・H. ; エルダー、マレー; レヒニッツァー、アンドリュー; ウェストコット、P.; ザブロッキ、マイク (2006)、「4231回避順列のスタンレー・ウィルフ限界とアラティア予想について」、応用数学の進歩、36 (2): 96– 105、arXiv : math/0502504、doi : 10.1016/j.aam.2005.05.007、hdl : 10453/98769、MR 2199982。
アルバート、マイケル・H. ;アトキンソン、MD ; ブリグナル、ロバート (2011)、「2143 と 4231 を避ける順列の列挙」(PDF)、純粋数学と応用、22 : 87– 98、arXiv : 1108.0989、MR 2924740。
アルバート、マイケル H. ;アトキンソン、MD ; ブリグナル、ロバート (2012)、「単調グリッドクラスを用いた3つのパターンクラスの列挙」、Electronic Journal of Combinatorics、19 (3): Paper 20、34 pp、doi : 10.37236/2442、MR 2967225。
アルバート、マイケル H. ;アトキンソン、MD ; ヴァッター、ヴィンセント (2009)、「1324, 4231 の順列の回避」、Electronic Journal of Combinatorics、16 (1): Paper 136、9 pp、arXiv : 1102.5568、doi : 10.37236/225、MR 2577304。
アルバート、マイケル H. ;アトキンソン、MD ; ヴァッター、ヴィンセント (2014)、「幾何学的グリッドクラスのインフレーション：3つのケーススタディ」（PDF）、オーストラレーシア・ジャーナル・オブ・コンビナトリクス、58 (1): 27– 47、MR 3211768。
Albert, Michael H. ; Bean, Christian; Claesson, Anders; Nadeau, Émile; Pantone, Jay; Ulfarsson, Henning (2024)「組み合わせ探索：列挙のためのアルゴリズムフレームワーク」arXiv : 2202.07715 [ math.CO ]。
Albert, Michael H. ; Homberger, Cheyne ; Pantone, Jay ; Shar, Nathaniel ; Vatter, Vincent (2018)「制限付きコンテナによる順列生成」、Journal of Combinatorial Theory, Series A , 157 : 205– 232, arXiv : 1510.00269 , doi : 10.1016/j.jcta.2018.02.006 , MR 3780412。
アトキンソン, MD (1998)、「増加部分列と減少部分列の和集合である順列」、Electronic Journal of Combinatorics、5 R6: Paper 6、13 pp、doi : 10.37236/1344、MR 1490467。
アトキンソン, MD (1999)、「制限付き順列」、離散数学、195 ( 1– 3): 27– 38、doi : 10.1016/S0012-365X(98)00162-9、MR 1663866。
アトキンソン, MD ;セーガン, ブルース E. ; ヴァッター, ヴィンセント (2012)、「(3+1) を避ける順列の計算」、European Journal of Combinatorics、33 : 49–61、doi : 10.1016/j.ejc.2011.06.006、MR 2854630。
ベヴァン、デイヴィッド（2015）「1324を避ける順列とウカシェヴィチ経路のパターン」、J. London Math. Soc.、92（1）：105– 122、arXiv：1406.2890、doi：10.1112/jlms/jdv020、MR 3384507。
ベヴァン、デイビッド（2016a）、「順列クラスAv（1234,2341）とAv（1243,2314）」（PDF）、オーストラレーシア・ジャーナル・オブ・コンビナトリクス、64（1）：3– 20、MR 3426209。
ベヴァン、デイヴィッド（2016b）、「順列クラスAv（4213,2143）」、離散数学と理論計算機科学、18（2）1309：14pp、arXiv：1510.06328、doi：10.46298/dmtcs.1309。
ベヴァン、デイビッド；ブリグナル、ロバート；エルベイ・プライス、アンドリュー；パントン、ジェイ（2020）「Av(1324)の構造的特徴づけとその成長率の新たな限界」、European Journal of Combinatorics、88 103115: 1– 29、arXiv : 1711.10325、doi : 10.1016/j.ejc.2020.103115。
ブルーム、ジョナサン; ヴァッター、ヴィンセント (2016)、「フルルーク配置に関する2つのビネット」(PDF)、オーストラレーシア・ジャーナル・オブ・コンビナトリクス、64 (1): 77– 87、MR 3426214。
Bóna, Miklós (1997)、「1342回避順列の正確な列挙：ラベル付き木と平面写像との密接な関係」、Journal of Combinatorial Theory、シリーズA、80 (2): 257– 272、arXiv : math/9702223、doi : 10.1006/jcta.1997.2800、MR 1485138。
Bóna, Miklós (1998)、「滑らかな類と同数の順列類」、Electronic Journal of Combinatorics、5 R31: Paper 31、12 pp、doi : 10.37236/1369、MR 1626487。
Bóna, Miklós (2015)、「1324回避順列の新記録」、European Journal of Mathematics、1 (1): 198– 206、arXiv : 1404.4033、doi : 10.1007/s40879-014-0020-6、MR 3386234。
Callan, David (2013a)、「{1243, 2134}-回避順列の数」、離散数学と理論計算機科学5287、arXiv : 1303.3857、doi : 10.46298/dmtcs.5287。
Callan, David (2013b)、「4321と3241を避ける順列は代数的生成関数を持つ」、Discrete Mathematics & Theoretical Computer Science 5286、arXiv : 1306.3193、doi : 10.46298/dmtcs.5286。
コンウェイ、アンドリュー；グットマン、アンソニー（2015）「1324回避順列について」応用数学の進歩、64：50-69、doi：10.1016/j.aam.2014.12.004、MR 3300327。
コンウェイ、アンドリュー；グットマン、アンソニー；ジン＝ジャスティン、ポール（2018）「1324回避順列の再考」応用数学の進歩、96：312–333、arXiv：1709.01248、doi：10.1016/j.aam.2018.01.002。
ゲッセル、アイラ・M.（1990）「対称関数とP再帰性」、組合せ理論ジャーナル、シリーズA、53（2）：257-285、doi：10.1016/0097-3165（90）90060-A、MR 1041448。
ヨハンソン, フレドリック; ナカムラ, ブライアン (2014)、「関数方程式を用いた1324回避順列の列挙」、応用数学の進歩、56 : 20–34、arXiv : 1309.7117、doi : 10.1016/j.aam.2014.01.006、MR3194205 。
クヌース、ドナルド E. (1968)、『コンピュータプログラミングの芸術』第1巻、ボストン：アディソン・ウェスレー、ISBN 978-0-201-89683-1、MR 0286317、OCLC 155842391。
クレマー、ダーラ（2000）「禁制部分列を持つ順列と一般化シュレーダー数」、離散数学、218（1-3）：121-130、doi：10.1016/S0012-365X（99）00302-7、MR 1754331。
クレマー、ダーラ（2003）「追記：「禁制部分列を持つ順列と一般化シュレーダー数」離散数学, 270 ( 1– 3): 333– 334, doi : 10.1016/S0012-365X(03)00124-9 , MR 1997910。
クレマー、ダーラ; シウ、ワイ・チー (2003)、「長さ4のパターンのペアを回避する順列の有限遷移行列」、離散数学、268 ( 1– 3): 171– 183、doi : 10.1016/S0012-365X(03)00042-6、MR 1983276。
Le, Ian (2005)、「長さ4の順列ペアのWilf類」、Electronic Journal of Combinatorics、12 R25：論文25、27 pp、doi：10.37236/1922、MR 2156679。
マクマホン、パーシー・A.（1916）、組み合わせ分析、ロンドン：ケンブリッジ大学出版局、MR 0141605。
マリノフ、ダーコ。 Radoičić、Radoš (2003)、「Counting 1324-avoiding permutations」、Electronic Journal of Combinatorics、9 (2): Paper 13、9 pp、doi : 10.37236/1685、MR 2028282。
Miner, Sam (2016)、「2行4列の複数のクラスの列挙」、arXiv : 1610.01908 [ math.CO ]。
マイナー、サム; パントン、ジェイ (2018)「2x4順列クラスの構造解析の完了」arXiv : 1802.00483 [ math.CO ]。
パントン、ジェイ（2017）、「3124と4312を避ける順列の列挙」、Annals of Combinatorics、21（2）：293-315、arXiv：1309.0832、doi：10.1007/s00026-017-0352-2。
シミオン、ロディカ; シュミット、フランク W. (1985)、「制限付き順列」、ヨーロッパ組合せ論ジャーナル、6 (4): 383– 406、doi : 10.1016/s0195-6698(85)80052-4、MR 0829358。
Vatter, Vincent (2006)、「有限ラベル付き生成木と制限付き順列」、Journal of Symbolic Computation、41 (5): 559– 572、arXiv : math/0309238、doi : 10.1016/j.jsc.2005.10.003、MR 2209164。
Vatter, Vincent (2012)、「順列クラスに対する正規挿入エンコーディングの探索」、Journal of Symbolic Computation、47 (3): 259– 265、arXiv : 0911.2683、doi : 10.1016/j.jsc.2011.11.002、MR 2869320。
ウェスト、ジュリアン（1996）、「生成木と禁制部分列」、離散数学、157（1-3）：363-374、doi：10.1016/S0012-365X（96）83023-8、MR 1417303。

外部リンク

Bridget Tennerが管理する順列パターン回避のデータベースには、比較的少ない基底要素を持つ他の多くの順列クラスの列挙の詳細が含まれています。