TOPICS
Search

Directed Convex Polyomino

DirectedConvexPolygon

A convex polyomino containing at least one edge of its minimal bounding rectangle. The perimeter and area generating function for directed polygons of width m, height n, and area q is given by

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

where

N(x)=sum_(n>=0)((-1)^nx^nq^((n+1; 2)))/((q)_n(yq)_n)
(3)
N^^(x)=sum_(n>=1)((-1)^nx^nq^((n+1; 2)))/((q)_(n-1)(yq)_n)
(4)
R(x)=ysum_(n>=2)[(x^nq^n)/((yq)_n)(sum_(m=0)^(n-2)((-1)^mq^((m+2; 2)))/((q)_m(yq^(m+1))_(n-m-1)))]
(5)

(Bousquet-Mélou 1992ab).

The anisotropic perimeter generating function for directed convex polygons of width x and height y is given by

G(x,y)=sum_(x>=1)sum_(y>=1)C(m,n)x^my^n
(6)
=(xy)/(sqrt(Delta(x,y))),
(7)

where

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

(Lin and Chang 1988, Bousquet 1992ab, Bousquet-Mélou et al. 1999). This can be solved to explicitly give

C(m,n)=(m+n-2; m-1)(m+n-2; n-1)
(10)

(Bousquet-Mélou 1992ab). Expanding the generating function gives

G(x,y)=sum_(m>=1)H_m(y)x^m
(11)
=y/(1-y)x+(y(1+y))/((1-y)^3)x^2+(y(1+4y+y^2))/((1-y)^5)x^3+...
(12)
=(y+y^2+y^3+y^4+y^5+...)x+(y+4y^2+9y^3+16y^4+25y^5+...)x^2+(y+9y^2+36y^3+100y^4+225y^5+...)x^3+(y+16y^2+100y^3+400y^4+1225y^5+...)x^4+....
(13)

An explicit formula of H_m(y) is given by Bousquet-Mélou (1992ab). These functions satisfy the reciprocity relations

H_m(1/y)=-y^(m-2)H_m(y)
(14)
G(x,y)+y^2G(x/y,1/y)=0
(15)

(Bousquet-Mélou et al. 1999).

The anisotropic area and horizontal perimeter generating function G(x,q) and partial generating functions H_m(q), connected by

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

satisfy the self-reciprocity and inversion relations

H_m(1/q)=-1/qH_m(q)
(17)

and

G(x,q)+qG(x,1/q)=0
(18)

(Bousquet-Mélou et al. 1999).

See also

Convex Polyomino, Lattice Polygon

Explore with Wolfram|Alpha

References

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.; Guttmann, A. J.; Orrick, W. P.; and Rechnitzer, A. "Inversion Relations, Reciprocity and Polyominoes." 23 Aug 1999. http://arxiv.org/abs/math.CO/9908123.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.

Referenced on Wolfram|Alpha

Directed Convex Polyomino

Cite this as:

Weisstein, Eric W. "Directed Convex Polyomino." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DirectedConvexPolyomino.html

Subject classifications