用整数分拆构建多格子形状计数新方法，高效计算无洞行凸多格子数量。
A Partition-Based Generating Function for Row-Convex Polyominoes
- 基于面积的整数分拆，将每行长度序列映射为分拆组合。
- 推导出精确生成函数，渐近增长呈2^N乘余弦振荡形式。
- 适合组合数学与图像建模中凸结构生成的研究者使用。
本文提出一种新的生成函数，用于计数离散网格上无内部孔洞的行凸多格子。方法基于总面积的整数分拆，每个分拆对应一组行长序列，各部分的全排列乘积表示连续行间所有可能的水平对齐方式。对所有此类乘积求和，得到给定大小多格子的总数。通过数值示例验证小面积情形，并利用转移级数法推导出精确生成函数，其渐近形式为S(N) = A·2^N·cos(Nθ + φ)，其中θ = arctan(√7/3)。该方法建立了整数分拆与多格子枚举之间的直接联系，提供了一种简洁有效的框架，适用于精确与渐近组合分析。潜在应用包括离散图像分析中的形状先验、基于网格的建模以及凸结构的组合生成。
原文摘要 · Abstract (English)
An alternative generating function is proposed to enumerate row-convex polyominoes without internal holes on a discrete grid. The approach is based on integer partitions of the total area, where each partition corresponds to a sequence of row lengths, and the product of all permutations of the parts accounts for all possible horizontal alignments of consecutive rows. Summing over the products yields a formula for the total number of convex polyominoes of a given size. Numerical examples are provided for small areas, and the exact generating function is derived via a transfer series argument, establishing the asymptotic growth S(N) as A2^(N) cos(N*theta) + phi) with theta = arctan(sqrt(7)/3). The method establishes a direct connection between integer partitions and polyomino enumeration, offering a simple yet effective framework for both exact and asymptotic combinatorial analysis. Potential applications include shape priors in discrete image analysis, grid-based modeling, and combinatorial generation of convex structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。