A Partition-Based Generating Function for Row-Convex Polyominoes

技术摘要：基于分拆的行凸多联骨牌生成函数

问题陈述
多联骨牌（即二维整数格点上有限个连通单位正方形的集合）的计数问题在组合数学中仍然是一个具有挑战性的课题，尤其是对于由几何约束定义的类别。尽管一般多联骨牌的闭式公式大多未知，但凸多联骨牌、行凸多联骨牌和列凸多联骨牌等特定子类已被广泛研究。现有方法，特别是 Klarner 和 Hickerson 提出的方法，依赖于递推关系和转移矩阵论证来推导生成函数。然而，针对不含内部空洞的凸多联骨牌进行计数的显式闭式公式仍然有限。本文致力于解决不含内部空洞的行凸多联骨牌（即每一行均由连续单元格序列组成）的计数问题，寻求一种将多联骨牌计数直接关联到整数分拆的替代组合方法。

方法论
所提出的方法建立了行凸多联骨牌与总面积 $N$ 的整数分拆之间的直接对应关系。其核心逻辑如下：

1. 分拆分解：每一个面积为 $N$ 的行凸多联骨牌被分解为行长度序列 $(\lambda_1, \lambda_2, \dots, \lambda_k)$，使得 $\sum \lambda_i = N$。该序列构成了 $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），并与 OEIS 序列 A001169 中 $N$ 高达 12 的已知值进行了验证，结果显示完全一致。
• 对称性简化：本文讨论了通过识别镜像构型来减少计数的界限，指出虽然对于特定的奇偶性情况可以实现精确减半，但从分拆公式直接推导出对称多联骨牌的通用闭式简化形式是困难的。

意义与局限性
本工作的主要贡献在于建立了整数分拆与行凸多联骨牌计数之间的直接组合联系。通过将问题重构为分拆及其排列的形式，本文提供了一个“简单而有效的框架”，用于精确计数和渐近分析，而无需依赖传统上使用的更复杂的转移矩阵论证。

本文明确指出该方法的局限性：它严格适用于不含内部空洞的行凸多联骨牌。将该方法扩展到凹多联骨牌被认为在组合上是不可行的，因为凹行可能会分裂成多个不连通的分量（子分拆），并带有可变的间隙，这使得 4-连通性约束的强制执行变得显著更加复杂。

这项工作将自己定位为对经典方法（Klarner, Hickerson）的替代而非取代，提供了一种新的视角，简化了此类特定多联骨牌生成函数和渐近估计的推导。文中提到的潜在应用包括离散图像分析中的形状先验、基于网格的建模以及程序化生成，尽管这些仅作为此类计数相关的背景被提及，而非本具体研究的实验结果。