主题
Search

凸多边形骨牌

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook
ConvexPolyominoes

凸多边形骨牌（有时称为“凸多边形”）是一种多边形骨牌，其周长等于其最小边界框的周长 (Bousquet-Mélou 等人，1999)。如果它还包含其最小边界框的至少一个角，则称其为定向凸多边形骨牌。 列凸多边形骨牌是一种自回避多边形骨牌，使得任何垂直线与该多边形骨牌的交集最多有两个连通分量，行凸多边形骨牌的定义类似。上面描述了一些类型的命名凸多边形骨牌 (Bousquet-Mélou 等人，1999)。

Klarner 和 Rivest (1974) 以及 Bender (1974) 给出了面积为 n 的凸多边形骨牌数量 a_n 的渐近估计为

a_n∼cgamma^n,
(1)

其中 gamma=2.30914... 和 c=2.67564... (Delest 和 Viennot 1984)。

各向异性周长和面积生成函数

G(x,y,q)=sum_(m>=1)sum_(n>=1)sum_(a>=1)C(m,n,a)x^my^nq^a,
(2)

其中 C(m,n,a) 是具有 2m 条水平边、2n 条垂直边和面积为 a 的多边形的数量，由下式给出

G(x,y,q)=2sum_(m>=1)(y^(m+2))/((xq)_m^2N(xq^(m-1))N(xq^m))[T_(m+1)S(xq^m)-yT_mS(xq^(m+1))]^2+sum_(m>=1)(xy^mq^m(T_m)^2)/((xq)_(m-1)(xq)_m),
(3)

其中

N(x)=sum_(n>=0)((-1)^nx^nq^((n+1; 2)))/((q)_n(yq)_n)
(4)
S(x)=sum_(n>=1)[(x^nq^n)/((yq)_n)sum_(j=0)^(n-1)((-1)^jq^((j; 2)))/((q)_j(yq^(j+1))_(n-j))]
(5)

并且 T_n(x) 是多项式递推关系

T_n(x)=2T_(n-1)(x)+(xq^(n-1)-1)T_(n-2)(x)
(6)

其中 T_0(x)=1 和 T_1(x)=1 (Bousquet-Mélou 1992b)。这些多项式的前几个由下式给出

T_2(x)=1+qx
(7)
T_3(x)=1+(2q+q^2)x
(8)
T_4(x)=1+(3q+2q^2+q^3)x+q^4x^2
(9)
T_5(x)=1+(4q+3q^2+2q^3+q^4)x+(2q^4+2q^5+q^6)x^2.
(10)

展开生成函数表明，周长为 2n+8 的凸多边形骨牌的数量由下式给出

p_(2n+8)=(2n+11)4^n-4(2n+1)(2n; n),
(11)

其中 p_4=1、p_6=2 和 (n; k) 是二项式系数 (Delest 和 Viennot 1984，Bousquet-Mélou 1992ab)。 p_(2n) 的生成函数由下式明确给出

sum_(n=2)^inftyp_(2n)t^(2n)=(t^4(1-6t^2+11t^4-4t^6))/((1-4t^2)^2)-4t^8(1-4t^2)^(-3/2)
(12)

(Delest 和 Viennot 1984；Guttmann 和 Enting 1988)。因此，前几项是 1, 2, 7, 28, 120, 528, 2344, 10416, ... (OEIS A005436)。

对于列凸和定向列凸多边形骨牌，此函数已精确计算 (Bousquet-Mélou 1996，Bousquet-Mélou 等人，1999)。 G(1,1,q) 是 q-级数，但对于列凸多边形骨牌变为代数式。然而，G(x,y,q) 对于列凸多边形骨牌再次涉及 q-级数 (Temperley 1956，Bousquet-Mélou 等人，1999)。

G(x,y)=G(x,y,1) 是 x 和 y (称为“逸度”) 的代数函数，由下式给出

G(x,y)=sum_(x>=1)sum_(y>=1)C(m,n)x^my^n
(13)
=(R(x,y)xy)/([Delta(x,y)]^2)-(4x^2y^2)/(Delta^(3/2)),
(14)

其中

R(x,y)=1-3x-3y+3x^2+3y^2+5xy-x^3-y^3-x^2y-xy^2-xy(x-y)^2
(15)
Delta(x,y)=1-2x-2y-2xy+x^2+y^2
(16)
=(1-y)^2[1-(x(2+2y-x))/((1-y)^2)]
(17)

(Lin 和 Chang 1988，Bousquet-Mélou 1992ab)。这可以求解以明确给出

C(m,n)=(mn-1)/(m+n-2)(2m+2n-4; 2m-2) -2(m+n-2)(m+n-3; m-1)(m+n-3; n-1)
(18)

(Gessel 2000，Bousquet-Mélou 1992ab)。

G(x,y) 满足反演关系

G(x,y)+y^3G(x/y,1/y)=xy-x^3ypartial/(partialx)(1-x+y)/(Delta(x,y)),
(19)

其中

Delta(x,y)=1-2x-2y-2xy+x^2+y^2
(20)
=(1-y)^2[1-(x(2+2y-x))/((1-y)^2)]
(21)

(Lin 和 Chang 1988，Bousquet-Mélou 等人，1999)。

宽度为 3 的列凸多边形骨牌的半垂直周长和面积生成函数由以下特殊情况给出

H_3(y,q)=(yq^3)/((1-yq)^4(1-yq^2)^2(1-yq^3))(y^6q^8+4y^5q^7+2y^5q^6+y^4q^6-y^4q^4-4y^3q^5-6y^3q^4-4y^3q^3-y^2q^4+y^2q^2+2yq^2+4yq+1)
(22)

的通用有理函数 (Bousquet-Mélou 等人，1999)，它满足互反关系

H_3(1/y,1/q)=-1/(yq^3)H_3(y,q).
(23)

各向异性面积和周长生成函数 G(x,y,q) 和部分生成函数 H_m(y,q)，由下式连接

G(x,y,q)=sum_(m>=1)H_m(y,q)x^m,
(24)

满足自互反和反演关系

H_m(1/y,1/q)=-1/(yq^m)H_m(y,q)
(25)

和

G(x,y,q)+yG(xq,1/y,1/q)=0
(26)

(Bousquet-Mélou 等人，1999)。

另请参见

列凸多边形骨牌, 定向凸多边形骨牌, 平行四边形多边形骨牌, 多边形骨牌, 堆叠多边形骨牌, 阶梯多边形

使用 探索

参考文献

Bender, E. "Convex n-ominoes." Disc. Math. 8, 31-40, 1974.Bousquet-Mélou, M. "Convex Polyominoes and Heaps of Segments." J. Phys. A: Math. Gen. 25, 1925-1934, 1992a.Bousquet-Mélou, M. "Convex Polyominoes and Algebraic Languages." J. Phys. A: Math. Gen. 25, 1935-1944, 1992b.Bousquet-Mélou, M. "A Method for Enumeration of Various Classes of Column-Convex Polygons." Disc. Math. 154, 1-25, 1996.Bousquet-Mélou, M.; Guttmann, A. J.; Orrick, W. P.; and Rechnitzer, A. "Inversion Relations, Reciprocity and Polyominoes." 23 Aug 1999. http://arxiv.org/abs/math.CO/9908123.Delest, M.-P. and Viennot, G. "Algebraic Languages and Polyominoes [sic] Enumeration." Theoret. Comput. Sci. 34, 169-206, 1984.Gessel, I. M. "On the Number of Convex Polyominoes." Ann. des Sci. Math. du Quebec, 24, 63-66, 2000.Guttmann, A. J. and Enting, I. G. "The Number of Convex Polygons on the Square and Honeycomb Lattices." J. Phys. A 21, L467-L474, 1988.Klarner, D. and Rivest, R. "Asymptotic Bounds for the Number of Convex n-ominoes." Disc. Math. 8, 31-40, 1974.Lin, K. Y. and Chang, S. J. "Rigorous Results for the Number of Convex Polygons on the Square and Honeycomb Lattices." J. Phys. A: Math. Gen. 21, 2635-2642, 1988.Sloane, N. J. A. Sequence A005436/M1778 in "The On-Line Encyclopedia of Integer Sequences."Temperley, H. N. V. "Combinatorial Problems Suggested by the Statistical Mechanics of Domains and of Rubber-Like Molecules." Phys. Rev. 103, 1-16, 1956.

在 中被引用

凸多边形骨牌

请引用为

Weisstein, Eric W. "凸多边形骨牌。" 来自 Web 资源。 https://mathworld.net.cn/ConvexPolyomino.html

学科分类