Convex polyominoes revisited: Enumeration of outer site perimeter,\n interior vertices, and boundary vertices of certain degrees

2020/08/16 by Toufik Mansour, Mansour, Toufik, Reza Rastegar +1
Biochemistry, Genetics and Molecular Biology · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Diffusion and Search Dynamics #FOS: Mathematics #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.2008.06931

openalex publication_date 2020/08/16 · openalex created_date 2022/07/22 · openalex updated_date 2026/07/28

Abstract

The main contribution of this paper is a new column-by-column method for the\ndecomposition of generating functions of convex polyominoes suitable for\nenumeration with respect to various statistics including but not limited to\ninterior vertices, boundary vertices of certain degrees, and outer site\nperimeter. Using this decomposition, among other things, we show that\n A) the average number of interior vertices over all convex polyominoes of\nperimeter 2n is asymptotic to \(n²)/(12)+\(n\√(n))/(3\√(\π))\n-\((21\π-16)n)/(12\π).\n B) the average number of boundary vertices with degree two over all convex\npolyominoes of perimeter 2n is asymptotic to\n\(n+6)/(2)+\(1)/(\√(\π n))+\((16-7\π))/(4\π n). Additionally,\nwe obtain an explicit generating function counting the number of convex\npolyominoes with n boundary vertices of degrees at most three and show that\nthis number is asymptotic to \n\(n+1)/(40)\(\(3+\√(5))/(2)\)^n-3\n+ frac\√[4]5(2-\√(5))80\√(\π\nn)\(\(3+\√(5))/(2)\)^n-2. Moreover, we show that the\nexpected number of the boundary vertices of degree four over all convex\npolyominoes with n vertices of degrees at most three is asymptotically \n\(n)/(\√(5))- frac\√[4]125(\√(5)-1)\√(n)10\√(\π). \n C) the number of convex polyominoes with the outer-site perimeter n is\nasymptotic to frac3(\√(5)-1)20\√(\π\n n)\√[4]5\(\(3+\√(5))/(2)\)ⁿ, and show the expected\nnumber of the outer-site perimeter over all convex polyominoes with perimeter\n2n is asymptotic to\n\(25n)/(16)+\(\√(n))/(4\√(\π))+\(1)/(8). Lastly, we prove\nthat the expected perimeter over all convex polyominoes with the outer-site\nperimeter n is asymptotic to \√[4]5n.\n

Related

• k-Convex Polyominoes by Semi-perimeter
• On column-convex and convex Carlitz polyominoes
• The perimeter generating function for nondirected diagonally convex polyominoes
• Polyominoes with nearly convex columns: An undirected model
• The Number of Convex Polyominoes with Given Height and Width