特定の順列クラスの列挙

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

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

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

1324 を回避する順列を数える非再帰的公式は知られていない。再帰的公式は Marinov と Radoičić (2003) によって与えられた。関数方程式を使用するより効率的なアルゴリズムは Johansson と Nakamura (2014) によって与えられ、これは Conway と Guttmann (2015) によって強化され、その後 Conway、Guttmann、Zinn-Justin (2018) によってさらに強化され、列挙の最初の 50 項が与えられた。Bevan ら (2017) は、このクラスの成長の下限と上限を提供している。

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

対称クラスは 18 個、ウィルフクラスは 9 個あり、すべて列挙されています。これらの結果については、Atkinson (1999) または West (1996) を参照してください。

対称性類は 56 個、ウィルフ同値類は 38 個あります。これらのうち番号が付けられていないのは 3 つだけで、その生成関数はAlbert ら (2018) によって代数微分方程式(ADE)を満たさないと推測されています。特に、この推測はこれらの生成関数がD 有限ではないことを意味します。

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

• バクスター順列
• リフルシャッフル順列

• アルバート、マイケル H. ; エルダー、マレー; レヒニッツァー、アンドリュー; ウェストコット、P.; ザブロッキ、マイク (2006)、「4231 回避順列のスタンレー・ウィルフ限界とアラティア予想について」、応用数学の進歩、36 (2): 96–105、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。
• Albert, Michael H. ; Atkinson, MD; Brignall, Robert (2012)、「モノトーン グリッド クラスを使用した 3 つのパターン クラスの列挙」、Electronic Journal of Combinatorics、19 (3​​): 論文 20、34 pp、doi : 10.37236/2442、MR  2967225。
• アルバート、マイケル H. ; アトキンソン、MD; ヴァッター、ヴィンセント (2009)、「1324 と 4231 を回避する順列の計算」、電子組合せ論ジャーナル、16 (1): 論文 136、9 pp、arXiv : 1102.5568、doi :10.37236/225、​​MR  2577304。
• Albert, Michael H. ; Atkinson, MD; Vatter, Vincent (2014)、「幾何学的グリッドクラスのインフレーション: 3 つのケーススタディ」(PDF)、Australasian Journal of Combinatorics、58 (1): 27–47、MR  3211768。
• Albert, Michael H. ; Homberger, Cheyne; Pantone, Jay; Shar, Nathaniel; Vatter, Vincent (2018)、「制限付きコンテナによる順列の生成」、Journal of Combinatorial Theory、シリーズ A、157 : 205–232、arXiv : 1510.00269、doi :10.1016/j.jcta.2018.02.006、MR  3780412。
• アトキンソン、MD (1998)、「増加部分列と減少部分列の和集合である順列」、電子組合せ論ジャーナル、5：論文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) 回避順列の計算」、ヨーロッパ組合せ論ジャーナル、33 : 49–61、doi : 10.1016/j.ejc.2011.06.006、MR  2854630。
• ベヴァン、デイビッド（2015）、「1324 を回避する順列と Łukasiewicz パスのパターン」、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）：14pp、arXiv：1510.06328、doi：10.46298/dmtcs.1309。
• ベヴァン、デイビッド、ブリグナル、ロバート、エルベイ・プライス、アンドリュー、パントン、ジェイ（2017）、Av（1324）の構造特性とその成長率の新しい限界、arXiv：1711.10325、Bibcode：2017arXiv171110325B。
• ブルーム、ジョナサン、ヴァッター、ヴィンセント (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：論文31、12 pp、doi：10.37236/1369、MR  1626487。
• ボナ、ミクローシュ(2015)、「1324 を回避する順列の新記録」、ヨーロッパ数学ジャーナル、1 (1): 198–206、arXiv : 1404.4033、doi :10.1007/s40879-014-0020-6、MR  3386234。
• Callan, David (2013a)、「{1243, 2134} を回避する順列の数」、離散数学と理論計算機科学、arXiv : 1303.3857、Bibcode :2013arXiv1303.3857C、doi :10.46298/dmtcs.5287。
• Callan, David (2013b)、「4321 と 3241 を避ける順列には代数生成関数がある」、Discrete Mathematics & Theoretical Computer Science、arXiv : 1306.3193、Bibcode :2013arXiv1306.3193C、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、MR  3194205。
• クヌース、ドナルド E. (1968)、コンピュータプログラミングの芸術第 1 巻、ボストン: Addison-Wesley、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 : 論文 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。
• マイナー、サム (2016)、2×4クラスの列挙、arXiv : 1610.01908、Bibcode :2016arXiv161001908M。
• マイナー、サム; パントン、ジェイ (2018)、2x4順列クラスの構造分析の完了、arXiv : 1802.00483、Bibcode :2018arXiv180200483M。
• パントン、ジェイ (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 (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が管理する「順列パターン回避のデータベース」には、比較的少ない基底要素を持つ他の多くの順列クラスの列挙の詳細が含まれています。