Pattern Avoidance for Fibonacci Sequences using $k$-Regular Words

本論文は、$k$-正則語における特定のパターン回避が $a_k(n)$ および $b_k(n)$ という 2 つの $k$ 項フィボナッチ再帰数列と一致することを証明し、さらに特定の結合パターン回避数がフィボナッチ数の 2 乗になるという予想を提示するものである。

要約

この論文は、**「数字の並び方」と「禁止されたルール」**をテーマにした、数学的なパズルの話です。

想像してみてください。あなたは「数字のブロック」を並べる職人です。
この論文では、**「1 から n までの数字を、それぞれ k 回ずつ使って、長い列を作る」**というゲームを扱っています。
（例：n=2, k=2 なら、「1, 1, 2, 2」を並べる。n=3, k=2 なら「1, 1, 2, 2, 3, 3」を並べる）

そして、その並び方に**「禁止されたパターン（ルール）」**を設けます。
「121」という並び（小さい、大きい、小さい）や「123」という並び（小さい、中くらい、大きい）などが禁止されているとします。

この論文の核心は、**「どんなルール（禁止パターン）を設ければ、並べ方の総数が『有名な数列』になるか？」**という問いに答えたことです。

---

1. 2 つの新しい「並べ方」の発見

著者たちは、2 つの異なる「禁止ルール」を見つけ出し、それぞれが有名な数列と一致することを証明しました。

① 「フィボナッチ・k 数列」を作る並べ方

• ルール: 「121（小さい・大きい・小さい）」、「123（順調に上がる）」、「132（上がって下がる）」、「213（上がって下がる）」の 4 つを禁止する。
• 結果: このルールで並べられるパターンの数は、**「フィボナッチ・k 数列」**という数字の羅列とぴったり一致します。
• イメージ:
  • 普通のフィボナッチ数列（1, 1, 2, 3, 5...）は、前の 2 つを足して次の数字を決めます。
  • この「フィボナッチ・k」は、「前の 1 つの数字」に「k 倍した前の 2 つの数字」を足すという、少し太めのルールで成長します。
  • 例: k=2 の場合（Jacobsthal 数列と呼ばれるもの）、1, 1, 3, 5, 11... と増えます。これは、ブロックの並べ方が「前の状態」から「2 倍の選択肢」で広がっていくことを意味します。

② 「k-フィボナッチ数列」を作る並べ方

• ルール: 「122（小さい・同じ・同じ）」と「213（上がって下がる）」を禁止する。
• 結果: これは**「k-フィボナッチ数列」**（1, 1, 3, 7, 17...）という、また別の有名な数列と一致します。
• イメージ:
  • こちらは、**「前の 2 つの数字を足す」のではなく、「前の 1 つの数字を k 倍して、さらに前の 2 つの数字を足す」**という、もっと激しく成長するルールです。
  • k=2 の場合、ペル数列（Pell numbers）の仲間のような、1, 1, 3, 7, 17... と急激に増える数列になります。

なぜこれがすごいのか？
以前、数学者たちは「Stirling 順列（特殊な並び）」という難しい文脈で、①の結果を知っていました。しかし、この論文は**「もっとシンプルで直接的な方法」で証明し、さらに②という全く新しい並べ方**を発見しました。まるで、複雑な迷路の解き方を「最短ルート」で発見し、さらに「別の新しい迷路」も見つけたようなものです。

---

2. 「連続ルール」の魔法：フィボナッチの二乗

論文の最後には、さらに面白い発見があります。

• ルール変更: 禁止パターン「121」を、「連続して並んでいる 121」（つまり、真ん中の数字が隣り合っている状態）だけ禁止するように変えます。
• 結果: このルールで並べられるパターンの数は、「フィボナッチ数列の二乗」（1, 1, 4, 9, 25...）になります。

アナロジー:
普通のルールでは「121」がどこに現れてもアウトでしたが、新しいルールでは「121」が「くっついていない」場合は許されます。
この「少し緩いルール」にすることで、並べ方の総数が「フィボナッチ数列」の二乗（1×1, 1×1, 2×2, 3×3...）になるという、美しい対称性が生まれました。
まるで、パズルのピースを少しだけ自由に動かせるようにすると、組み合わせの数が「元の数の二乗」だけ増えるような魔法の現象です。

---

3. この研究の意義（まとめ）

この論文は、単に数字の数を数えただけではありません。

1. 単純化: 複雑な数学的な証明を、誰でも理解できるような「ブロックの並べ替え」の論理でシンプルにしました。
2. 発見: 「禁止ルール」を変えるだけで、自然界や数学でよく見られる「フィボナッチ数列」や「Jacobsthal 数列」といった有名な数字が、ブロックの並べ方から自然に現れることを示しました。
3. 未来への扉: 「k-regular words（k 回繰り返す並び）」という概念を使えば、もっと複雑な数列や、まだ見ぬ数学的なパターンを発見できるかもしれないと示唆しています。

一言で言うと：
「数字のブロックを並べるゲームで、『禁止ルール』を工夫すると、数学の教科書に載っている有名な数列が、自然と現れることがわかったよ！」という、数学的なパズルの新発見の報告です。

技術概要

論文「Pattern Avoidance for Fibonacci Sequences using k-Regular Words」の技術的概要

この論文は、離散数学および理論計算機科学の分野において、**$k$-正規語（k-regular words）を用いたパターン回避（pattern avoidance）**の研究を通じて、一般化されたフィボナッチ数列の組合せ論的解釈を提供するものです。著者らは、特定の禁止パターンを避ける $k$-正規語の数が、特定の漸化式を満たす数列（Fibonacci-$k$ 数列や $k$-Fibonacci 数列）と一致することを証明しました。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

---

1. 問題設定と背景

1.1 対象とする対象物

• $k$-正規語 ($k$-regular words): 集合 $[n] = \{1, 2, \dots, n\}$ の各要素がちょうど $k$ 回現れる長さ $kn$ の語。
• パターン回避: 語内の部分列（subword）が、指定されたパターン（例：123, 121 など）の相対的な順序（order isomorphic）と一致しないこと。
• 対象とする数列:
  1. Fibonacci-$k$ 数列 ($a_k(n)$): $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$、初期値 $a_k(0)=a_k(1)=1$。
  2. $k$-Fibonacci 数列 ($b_k(n)$): $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$、初期値 $b_k(0)=b_k(1)=1$。

1.2 既存研究との関係

• Simion と Schmidt (1985): 置換（$k=1$ の場合）において、パターン $\{123, 132, 213\}$ を避ける数はフィボナッチ数 $F_{n+1}$ であることを示した。
• Kuba と Panholzer (2012): スターリング置換（2-正規語で $212$を避けるもの）の文脈で、特定の 3 パターンを避ける場合の数を$k$-パラメータ付きで研究し、Jacobsthal 数列（$k=2$の$a_k(n)$）との関係を指摘したが、その証明は生成関数や複雑な分解を用いており、直感的ではなかった。
• 本論文の動機: $k$-正規語におけるパターン回避の結果を、より単純で直接的な組み合わせ論的証明（双射や帰納的分解）を用いて再定式化し、新たなパターン回避結果（$k$-Fibonacci 数列に対応するもの）を発見すること。

---

2. 主要な貢献と結果

著者らは以下の 3 つの主要な定理を証明しました。

定理 1: Fibonacci-$k$ 語の計数

• 主張: 長さ $kn$ の $k$-正規語のうち、パターン集合 $\{121, 123, 132, 213\}$ のすべてを避ける語の数は、Fibonacci-$k$ 数 $a_k(n)$ に等しい。
  $$|Av^k_n(121, 123, 132, 213)| = a_k(n)$$
• 意義:
  • $k=1$ の場合、Simion と Schmidt の古典的結果（$F_{n+1}$）を再現する。
  • $k=2$ の場合、Jacobsthal 数列（A001045）を導く。
  • Kuba と Panholzer の結果を、より単純な組み合わせ論的証明（Proposition 1 と帰納法）で再証明した。

定理 2: $k$-Fibonacci 語の計数（新規発見）

• 主張: 長さ $kn$ の $k$-正規語のうち、パターン集合 $\{122, 213\}$ のすべてを避ける語の数は、$k$-Fibonacci 数 $b_k(n)$ に等しい（$k \ge 2$ の場合）。
  $$|Av^k_n(122, 213)| = b_k(n)$$
• 意義:
  • これは定理 1 と対照的な結果であり、$k$-Fibonacci 数列の新しい組合せ論的解釈を提供する。
  • $k=2$ の場合、Pell 数列に近いが初期値が異なる数列（A001333）に対応する。
  • $k=1$ の場合は Catalan 数になるが、この定理は $k \ge 2$ で成立し、Catalan 数との連続性を示す重要なギャップを埋める。

定理 5: フィボナッチ二乗数列と結合パターン（Vincular Patterns）

• 主張: 2-正規語（$k=2$）において、パターン $\{123, 132, 213\}$ と、**結合パターン（consecutive pattern）**としての $121$（すなわち、$121$が連続した位置で現れること）を避ける語の数は、フィボナッチ数の二乗$c(n) = (F_{n+1})^2$ に等しい。
  $$|Av^2_n(\text{121}_{\text{vincular}}, 123, 132, 213)| = a_1(n)^2$$
• 意義:
  • 従来の「121 を避ける」という条件を「121 が連続して現れることを避ける」というより強い条件（結合パターン）に変更することで、Jacobsthal 数列からフィボナッチ二乗数列へ遷移することを示した。
  • この結果を証明するために、新しい漸化式（式 20）と「プレフィックス木（prefix-tree）」と呼ばれる構造を導入し、語の分解（標準分割）を行った。

---

3. 手法と証明の概要

3.1 帰納的分解と双射

• 定理 1 の証明:
  • 語の先頭部分の構造を分析し、最大値 $n$ の配置に基づいて語を分類する（Proposition 1）。
  • 語は、$n^k$ で始まる場合（$n-1$ の語から構成）と、$n^b(n-1)^k n^{k-b}$ のようなパターンで始まる場合（$n-2$ の語から構成）に分解できることを示す。
  • この分解が漸化式 $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$ と完全に一致することを示す。
• 定理 2 の証明:
  • 同様に、最大値 $n$ の配置を分析（Lemma 2, 3）。
  • $n$ のコピーが $n-1$ より右に複数現れると $122$パターンが発生するため、$n$ の配置に制約が生じる。
  • これにより、$n^{k-1}$ で始まる場合と、$n^{k-1}(n-1)^k n$ で始まる場合に分解され、漸化式 $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$ が導かれる。

3.2 標準分割とプレフィックス木（定理 5）

• 標準分割 (Standard Partition): 語 $\gamma$ を「付加部（annex）」$\alpha$ と「基底（base）」$\beta$ に分割する。基底は最も長い末尾の $k$-正規語部分であり、付加部は残りの部分。
• プレフィックス木 ($T_n$): 付加部 $\alpha$ の構造を記述するための木構造を定義した。この木のルートからリーフまでのパスが、有効な付加部に対応する。
• 証明: 有効な語の付加部は、このプレフィックス木上のパスか、4 つの特殊ケース（例：$nn$, $(n-1)(n-1)nn$ など）のいずれかであることを示し、これらがフィボナッチ二乗数の漸化式を満たすことを確認した。

---

4. 意義と今後の展望

4.1 学術的意義

1. 単純化された証明: 既存の複雑な生成関数を用いた証明を、直感的な組み合わせ論的分解に置き換え、結果の構造を明確にした。
2. 新しいパラダイム: $k$-正規語におけるパターン回避が、単なる置換の一般化ではなく、独自の数列（Jacobsthal, $k$-Fibonacci など）を生成する豊かな構造を持つことを示した。
3. 非古典的パターンの統合: 結合パターン（vincular patterns）を $k$-正規語の文脈で適用し、数列の性質（Jacobsthal からフィボナッチ二乗へ）を制御できることを示した。

4.2 今後の研究方向

• 他の一般化フィボナッチ数列: $(1, k)$ や $(k, 1)$ などの初期値を持つ数列、あるいは $k$-一般化フィボナッチ数列（直前の $k$ 項の和）に対するパターン回避結果の探索。
• マルチパターンの回避: 標準パターンと重複記号を含むマルチパターンの組み合わせに対する回避数の完全な分類（Table 5 に示された未解決ケースの解明）。
• 非正規語への拡張: 正規語以外の文脈でのパターン回避研究への応用。

結論

本論文は、$k$-正規語という対象を通じて、フィボナッチ数列の多様な一般化とパターン回避理論を結びつける重要な架け橋となりました。特に、単純な漸化式を持つ数列が、特定の禁止パターンを持つ語の集合によって自然に記述されることを示し、離散数学における構造の美しさと深さを浮き彫りにしています。