主題
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.tw/ConvexPolyomino.html

學科分類