On a question about pattern avoidance of cyclic permutations

この論文は、Archer らによって未解決となっていた、特定の減少パターンを回避する巡回置換がさらに別の長さ 4 のパターン（1432）をそのすべての巡回表現で回避するケースについて、巡回表現の構造解析と Dilworth の定理を用いて明示的な公式を導出することで解決したものである。

要約

この論文は、数学の「組み合わせ論」という分野で、**「数字の並び方のルール」と「輪っか（円）の並び方のルール」**という、2 つの異なる世界で同時に「禁止されたパターン」を避けることができる数字の並べ方を数え上げるという、とても面白いパズルを解いたものです。

専門用語を抜きにして、日常の例え話を使って解説しましょう。

1. 舞台設定：数字の並べ方と「禁止ルール」

まず、1 から n までの数字を並べることを考えます。

• 直線の並び（1 行表記）: 数字を「1, 3, 5, 2, 4」のように一列に並べます。
• 輪っかの並び（巡回置換）: 数字を「(1, 3, 5, 2, 4)」のように円環状に並べます。円なので、どこから始めても同じ並びとみなされます（例：(3, 5, 2, 4, 1) も同じ）。

この論文では、2 つの「禁止ルール」を同時に守る並べ方を数えています。

1. ルール A（直線のルール）: 「5, 4, 3, 2, 1」のように、数字がどんどん小さくなる長い列を作ってはいけない。
   • 例：k=3 なら「3, 2, 1」は NG。k=4 なら「4, 3, 2, 1」は NG。
2. ルール B（輪っかのルール）: 輪っかのどの位置から読み始めても、「1, 4, 3, 2」のような特定の形を作ってはいけない。
   • この形は、小さい数字（1）の次に、一番大きい数字（4）が来て、その後に中くらいの数字（3, 2）が降ってくるような「山」の形です。

2. 過去の挑戦と今回のゴール

以前、他の研究者たちが「ルール A」を「3, 2, 1」が禁止の場合（k=3）と「4, 3, 2, 1」が禁止の場合（k=4）で解き明かしました。しかし、「1, 4, 3, 2」という形を避ける場合だけは、答えが出せない「難問」として残っていました。

今回の論文は、この最後の難問（k=3, 4, 5 以上すべての場合）を解決し、答えの公式を見つけ出したという報告です。

3. 解き方のコツ：2 つの魔法

彼らはこの難問を解くために、2 つの強力な「魔法（数学的定理）」を使いました。

魔法①：「階段と壁」の考え方（ダイルワースの定理）

「直線の並びで、3 つ以上連続して下り坂（3, 2, 1）を作らない」というルールは、実は**「数字をいくつかの『上り坂（階段）』に分けて並べれば良い」**と言い換えることができます。

• 例：数字を「1 つの階段」と「もう 1 つの階段」に分けて並べれば、3 つ連続で下ることはなくなります。
• この「階段の数」を制限することで、複雑な条件を単純な計算に変換しました。

魔法②：「輪っかの形」の分解

「輪っかの並びで、どの位置から読んでも『1, 4, 3, 2』を作らない」という条件は、実は**「輪っかの形が非常にシンプルで、整然としている」**ことを意味していました。

• 具体的には、数字が「1, 2, 3...」と順に並んでいる部分と、少し飛び飛びになっている部分だけしか許されない、という**「厳格な構造」**が見つかりました。
• これにより、無数にある並べ方の中から、条件に合うものだけをピンポイントで数え上げることができました。

4. 発見された答え（公式）

彼らは、n（数字の個数）が 5 以上の場合、答えは以下のようになると突き止めました。

• k=3 の場合（3, 2, 1 が NG）:
  答えは「n の二乗に似た形」で表せます。数字が増えると、許される並べ方はゆっくりと増えます。
• k=4 の場合（4, 3, 2, 1 が NG）:
  答えは「2 の n 乗」に近い形です。数字が増えると、許される並べ方が急激に増えます。
• k=5 以上の場合（5, 4, 3, 2, 1 が NG）:
  ここが面白い点です。「5 連続で下り坂」を避けるルールは、実は「輪っかの形がシンプルである」という条件と組み合わさると、「5 連続」を避ける必要が自動的に満たされてしまうことが分かりました。
  つまり、k=5 以上のルールは、k=4 の場合と同じ答えになります。

まとめ：なぜこれがすごいのか？

この研究は、「複雑に見えるルール（輪っかの形と直線の形の両方）」が、実は「非常にシンプルな構造」に隠されていたことを発見した点で画期的です。

• イメージ: 迷路の入り口が複雑そうに見えても、実は「右に曲がれば一直線」という単純なルールで抜けられることが分かったようなものです。
• 応用: この「パターン回避」の考え方は、データの整理、暗号の設計、あるいは DNA の配列解析など、現実世界の様々な「順序」を扱う問題に応用できる可能性があります。

要するに、この論文は**「数字の並べ方というパズルで、誰も解けなかった最後の難問を、数学の『魔法』を使って見事に解き明かした」**という物語なのです。

技術概要

1. 問題設定 (Problem Statement)

この研究は、Archer らが以前に提起した未解決問題を解決することを目的としています。
具体的には、以下の二つの条件を同時に満たす $n$ 次巡回置換 $\pi \in S_n$ の個数を数え上げる問題です。

1. 1 行表記（one-line notation）の制約: 置換 $\pi$ の 1 行表記が、減少パターン $\delta_k = k(k-1)\cdots 21$ を含まない（回避する）。
2. 標準巡回形（standard cycle form）の制約: $\pi$ の標準的な巡回形 $C(\pi) = (1, c_2, \dots, c_n)$ のすべての巡回回転（cyclic rotations）が、長さ 4 のパターン $\tau$ を含まない。

Archer らは、$\tau$ として長さ 4 のパターンを考慮する際、対称性と巡回回転を考慮して 3 つのケース（$\tau = 1324, 1342, 1432$）に分類し、$\tau = 1324$ と $\tau = 1342$ の場合については解を導出していました。しかし、$\tau = 1432$ の場合は未解決（open question）として残されていました。
本論文は、この未解決ケース $\tau = 1432$ に対して、明示的な公式を導出することを主目的としています。

2. 手法とアプローチ (Methodology)

著者らは、以下の数学的ツールと論理的な構造分析を組み合わせて問題を解決しました。

• 構造の同値変換:
  巡回形における「すべての回転が $1432$を回避する」という条件を、標準巡回形$C(\pi)$ におけるより単純な条件に帰着させました。

  • 命題 2.1: 標準巡回形 $C(\pi)$ が $321$パターンと$2143$パターンの両方を回避することと、すべての巡回回転が$1432$を回避することは同値であることが示されました。これにより、問題が「$C(\pi)$が$321$と$2143$を回避し、かつ 1 行表記が$\delta_k$ を回避する」置換の列挙に簡素化されました。

• ディルワースの定理（Dilworth's Theorem）の応用:
  1 行表記における減少部分列（$\delta_k$）の存在を判定するために、置換を部分順序集合（poset）として解釈し、ディルワースの定理を利用しました。

  • 1 行表記における長さ $k$ の減少部分列は、対応する poset におけるサイズ $k$ の反鎖（antichain）に相当します。
  • この poset が $k-1$ 本の鎖（chains）で被覆できれば、その置換は $\delta_k$ を回避します。この性質を用いて、特定の構造を持つ置換が $\delta_k$ を回避することを証明しました。

• 帰納的列挙と双射（Bijection）:
  置換の 2 番目の要素 $j = c_2$ の値に基づいてケースを分類し、$n$ と $n-1$ の間の双射を構成することで、漸化式を導出しました。

  • 特に $j=2$ の場合、$n$ 次から $n-1$ 次への双射が成立すること（Lemma 2.3, 3.2）を示しました。
  • $j \ge 3$ の場合、$C(\pi)$ の構造（$2$と$j$ の間の要素の順序など）を厳密に分析し、可能な配置パターンを数え上げました。

3. 主要な貢献と結果 (Key Contributions and Results)

本論文は、$n \ge 5$ および $k \ge 3$ に対して、$a^\circ_n(\delta_k; 1432)$（条件を満たす巡回置換の個数）の明示的な公式を導出しました。結果は $k$ の値によって 3 つの定理としてまとめられています。

定理 1.1: $k=3$ の場合 ($\delta_3 = 321$)

$n \ge 5$ に対して、以下の公式が成立します。
$$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2 + 7}{2} \right\rfloor - 2n$$
これは OEIS シリーズ A061925 に該当します。

定理 1.2: $k=4$ の場合 ($\delta_4 = 4321$)

$n \ge 5$ に対して、以下の公式が成立します。
$$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n - 5}{2} \right\rfloor$$
この結果は、$n=5$ の場合も検証済みです。

定理 1.3: $k \ge 5$ の場合

$n \ge 5$ に対して、以下の公式が成立します。
$$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$$
これは OEIS シリーズ A088921 に該当します。

重要な洞察 (Lemma 4.1):
$k \ge 5$ の場合、1 行表記での $\delta_k$ 回避条件は冗長であることが証明されました。つまり、標準巡回形が $321$と$2143$を回避するならば、自動的に 1 行表記は$\delta_5$（およびそれ以上の長さの減少パターン）を回避することが示されました。これにより、$k \ge 5$のケースは、単に$321$と$2143$ を回避する巡回置換の総数（Callan と Vella によって以前に求められた結果）に一致することが導かれました。

4. 意義 (Significance)

• 未解決問題の解決: Archer らによって提起された、パターン $1432$ に関する最後の未解決ケースを完全に解決し、この分野の知識を完成させました。
• 手法の確立: 巡回置換のパターン回避問題を解く際、標準巡回形の構造を $321$や$2143$ の回避条件に変換し、さらにディルワースの定理を適用して 1 行表記の制約を扱うという、強力なアプローチ手法を確立しました。
• 数列の特定: 導出された公式は既知の整数列（OEIS）と一致しており、組み合わせ論における既存の構造との関連性を示唆しています。
• 一般化: $k$ の値による振る舞いの違い（$k=3, 4$ では多項式的または指数関数的な複雑さを持つが、$k \ge 5$ では構造が単純化される）を明確にしました。

結論として、この論文は巡回置換のパターン回避理論において重要な一歩を踏み出し、特定の混合パターン条件に対する厳密な数え上げを達成した画期的な研究です。