A Partition-Based Generating Function for Row-Convex Polyominoes

技術的概要：行凸ポリオミノに対する分割に基づく母関数

問題定義
2 次元整数格子上の連結した単位正方形の有限集合であるポリオミノの列挙は、特に幾何学的制約によって定義されるクラスにおいて、組合せ論における困難な問題のままです。一般的なポリオミノに対する閉形式の公式はほとんど知られていませんが、凸、行凸、および列凸ポリオミノといった特定の部分クラスは広範に研究されてきました。既存の方法、特に Klarner と Hickerson による方法は、母関数を導出するために漸化式と転送行列の議論に依存しています。しかし、内部の穴を持たない凸ポリオミノを数えるための明示的な閉形式の公式は依然として限られています。本論文は、内部の穴を持たない行凸ポリオミノ（各行が連続したセルの列からなるもの）の列挙に取り組み、ポリオミノの列挙を整数分割に直接結びつける代替的な組合せ論的アプローチを追求します。

手法
提案された手法は、行凸ポリオミノと総面積 $N$ の整数分割との間の直接的な対応関係を確立します。核心的な論理は以下の通りです：

1. 分割分解: 面積 $N$ を持つ任意の行凸ポリオミノは、$\sum \lambda_i = N$ となる行の長さの列 $(\lambda_1, \lambda_2, \dots, \lambda_k)$ に分解されます。この列は $N$ の整数分割を形成します。
2. 水平整列（シフト）: 行の長さの列が固定されている場合、有効な水平整列の数は、連続する行間の「シフト」によって決定されます。行 $i$ の長さが $L_i$ で行 $i+1$ の長さが $L_{i+1}$ である場合、それらが接触できる位置の数（4-連結性を保証するため）は $L_i + L_{i+1} - 1$ です。固定された順序列に対する構成の総数は、これらのシフト因子の積となります：$\prod_{i=1}^{k-1} (\lambda_i + \lambda_{i+1} - 1)$。
3. 順列因子: 行の順序はポリオミノの形状に影響するため、この手法は分割部分の異なる順列を考慮します。因子 $\Phi(\lambda)$ は、分割 $\lambda$ の異なる順列の数を数えるために導入され、繰り返される部分のサイズ（重複度）に対して調整されます。
4. 列挙公式: 大きさ $N$ の行凸ポリオミノの総数 $S(N)$ は、$N$ のすべての整数分割にわたって、順列因子とシフト積の積を合計することで得られます：
   $$S(N) = \sum_{\lambda \in P(N)} \Phi(\lambda) \prod_{i=1}^{\ell(\lambda)-1} (\lambda_i + \lambda_{i+1} - 1)$$
5. 母関数の導出: 本論文は、この組合せ論的総和を母関数 $G(x) = \sum S(N)x^N$ に変換します。順序付き合成の転送級数として問題をモデル化し、その結果生じる線形方程式系を解くことで、正確な有理母関数が導かれます。

主要な結果

• 正確な母関数: 本論文は、行凸ポリオミノの母関数を以下のように導出します：
  $$G(x) = \frac{x(1-x)^3}{1 - 5x + 7x^2 - 4x^3}$$
  この結果は、以前に Klarner と Hickerson によって導出された列凸ポリオミノの母関数と完全に一致することが示され、分割に基づくアプローチの有効性が検証されました。
• 漸近成長: $G(x)$ の極の分析により、数列の漸近挙動が明らかになります。支配的な特異点は、$x = \frac{3 \pm i\sqrt{7}}{8}$ にある複素共役の極であり、その絶対値は $1/2$ です。したがって、ポリオミノの数は以下のように成長します：
  $$S(N) \sim A \cdot 2^N \cos(N\theta + \phi)$$
  ここで $\theta = \arctan(\sqrt{7}/3)$ です。これは、制限のない整数分割の準指数関数的成長とは対照的に、底が 2 の純粋な指数関数的成長を示しています。
• 数値検証: この公式は Python で実装され（アルゴリズム 1）、$N$ が 12 までの OEIS シーケンス A001169 の既知の値に対して検証され、完全な一致を示しました。
• 対称性の削減: 本論文は、鏡像の構成を識別することで数を削減する際の境界について議論しています。特定の偶奇の場合には正確な半分にすることが可能ですが、対称的なポリオミノに対する一般的な閉形式の削減は、分割公式から直接導出することが困難であると指摘しています。

意義と限界
この研究の主な貢献は、整数分割と行凸ポリオミノの列挙との間の直接的な組合せ論的リンクを確立したことです。分割とその順列の観点から問題を再定式化することで、本論文は、従来用いられてきたより複雑な転送行列の議論に依存することなく、正確な列挙と漸近分析の両方に対する「シンプルかつ効果的な枠組み」を提供します。

本論文は、このアプローチの限界を明確に指摘しています：これは内部の穴を持たない行凸ポリオミノに厳密に適用されます。凹ポリオミノへの手法の拡張は、凹んだ行が可変のギャップを持つ複数の非連結なコンポーネント（部分分割）に分裂しうるため、4-連結性の制約の強制が著しく複雑になるという理由から、組合せ論的に扱いにくいとみなされます。

この研究は、Klarner や Hickerson による古典的な手法の代替手段として位置づけられており、置き換えものではありません。この特定のクラスのポリオミノに対する母関数と漸近推定値の導出を簡素化する新しい視点を提供するものです。言及されている潜在的な応用には、離散画像解析における形状事前分布、グリッドベースのモデリング、手続き的生成が含まれますが、これらは本特定の研究の実験結果として提示されたものではなく、そのような列挙が関連する文脈として提示されています。