TOPICS
Search

Staircase Polygon


StaircasePolygon

Define the minimal bounding rectangle as the smallest rectangle containing a given lattice polygon. If the perimeter of the lattice polygon is equal to that of its minimal bounding rectangle, it is said to be convex. (Note that a "convex" lattice polygon is not necessarily convex in the usual sense of the word.) A staircase polygon is then defined as a convex polygon which contains two opposite corners of its bounding rectangle (Bousquet-Mélou et al. 1999).

The area generating function H_m(y,q) that counts polygons of width m for staircase polygons of width 4 is given by

 H_4(q)=(q^4(1+2q+4q^2+6q^3+7q^4+6q^5+4q^6+2q^7+q^8))/((1-q)^2(1-q^2)^2(1-q^3)^2(1-q^4)),
(1)

which satisfies

 H_4(1/q)=-H_4(q)
(2)

(Bousquet-Mélou 1992, Bousquet-Mélou et al. 1999). The anisotropic area and perimeter generating function G(x,y,q) and partial generating functions H_m(y,q), connected by

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

satisfy the self-reciprocity and inversion relations

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

for m>=2 and

 G(x,y,q)+yG(x/y,1/y,1/q)=-x
(5)

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

The anisotropic area and perimeter generating function G(x,y,q) of staircase polygon with a staircase hole satisfies an inversion relation of the form

 G(x,y,q)+y^2G(x/y,1/y,1/q)
(6)

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

Knuth (2022) considered the packing of all staircase polygons with a given semiperimeter into a square.


See also

Convex Polyomino, Self-Avoiding Polygon, Staircase Walk

Explore with Wolfram|Alpha

References

Bousquet-Mélou, M. "Convex Polyominoes and Heaps of Segments." J. Phys. A: Math. Gen. 25, 1925-1934, 1992.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.Knuth, D. E. Exercise 7.2.2.1-303 in The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2. New York: Addison-Wesley, 2022.

Referenced on Wolfram|Alpha

Staircase Polygon

Cite this as:

Weisstein, Eric W. "Staircase Polygon." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/StaircasePolygon.html

Subject classifications