1 Introduction

Unit squares with integer vertices in the square lattice are called cells. Two cells are connected if they share a common edge. A polyomino is a finite union of connected cells. Polyominoes have important applications in physics, chemistry, and biology, and enumeration of them is an active area of research in combinatorics. For the earliest works in these directions, see [11, 26, 27] and references therein. Other aspects of polyomino research include: bijective results [3, 9], asymptotic enumeration [12, 16,17,18, 28], algorithmic enumeration [7, 15], and probabilistic results [19, 20].

The area of a polyomino is the number of cells it contains. We define the boundary of a polyomino as the set of all edges that are incident to a cell of the polyomino and a cell outside the polyomino. The perimeter of a polyomino is the number of edges in its boundary. Determining the number of polyominoes of area n is a long-standing open question in combinatorics but there are promising results for enumerations of some special type of polyominoes. A column (row) of a polyomino is the intersection between the polyomino and any infinite vertical (horizontal) strip of unit squares. A polyomino is called column-convex (row-convex) if each of its columns (rows) is a single contiguous block of cells. A convex polyomino is both column-convex and row-convex. We use \(\mathcal {CCP}\) to denote the set of all column-convex polyominoes on the square lattice. For any polyomino, we identify the bottom cell in its first column with the cell with vertices (0, 0), (1, 0), (1, 1), (0, 1). An important subclass of column-convex polyominoes is bargraphs. A bargraph is a column-convex polyomino such that the lower edge of its first row lies on the horizontal axis.

Delest and Viennot [8] used a bijection between convex polyominoes and words of an algebraic language to show that the number of convex polyominoes with perimeter \(2n+8\) is given by

$$\begin{aligned} (2n+11)4^n-4(2n+1){2n \atopwithdelims ()n}. \end{aligned}$$

The perimeter generating function for column-convex polyominoes is defined as

$$\begin{aligned} C(x,y)=\sum _{\pi \in \mathcal {CCP}}x^{h(\pi )}y^{v(\pi )} \end{aligned}$$

where \(h(\pi )\) and \(v(\pi )\) denotes the half of the number of horizontal and of the vertical edges in the boundary of the polyomino \(\pi \), respectively.

Feretić and Svrtan [13, 14] showed that the perimeter generating function is given by

$$\begin{aligned} C(x,y)=(1-y)-\frac{4(1-y)}{6-\sqrt{(1-\sqrt{x})^2-\frac{4\sqrt{x}y}{1-y}}-\sqrt{(1+\sqrt{x})^2+\frac{4\sqrt{x}y}{1-y}}}, \end{aligned}$$
(1.1)

These results have been extended to the Carlitz polyominoes in [22]. In particular, it showed that, as n grows to infinity, asymptotically the number of column-convex and convex Carlitz polyominoes with perimeter 2n is \(\frac{9\sqrt{2}(14+3\sqrt{3})}{2704\sqrt{\pi n^3}}4^n\) and \(\frac{n+1}{10}\left( \frac{3+\sqrt{5}}{2}\right) ^{n-2}\), respectively.

In this paper, we refine and extend this result in two directions. In Sect. 2, we study the generating function

$$\begin{aligned} F(x,y,t,q)=\sum _{\pi \in \mathcal {CCP}}x^{h(\pi )}y^{v(\pi )}t^{area(\pi )}q^{intv(\pi )} \end{aligned}$$

where \(area(\pi )\) and \(intv(\pi )\) denote the number of the cells, and the number of interior vertices in the polyomino \(\pi \), respectively. A vertex in a polyomino \(\pi \) is called an interior vertex if it is adjacent to exactly four different cells of \(\pi \), otherwise it is called a boundary vertex. We find an exact expression for the generating function, and show that the average number of interior vertices over all column-convex polyominoes of perimeter 2n is asymptotic to \(\alpha _o n^{3/2}\) where \(\alpha _o\approx 0.57895563\ldots .\) In [23] bargraphs were enumerated according to the number of interior vertices and then the results were extended to the set partitions in [21].

In Sect. 3, we study the generating function that counts all column-convex polyominoes by their corners. For a polyomino \(\pi \), we call a vertex in its boundary a corner if it is of degree either 2 or 4. Note that a degree 2 (degree 4) vertex in the boundary is adjacent to exactly one (three) cell(s) in the polyomino \(\pi \). For instance, for the polyomino in Fig. 1, \(deg_2(\pi )=11\) and \(deg_4(\pi )=7\). In [4] (see also [1, 5, 6]) integer partitions were enumerated by corners, and then the results were extended to compositions, bargraphs, and set partitions in [24, 25]. We define the generating function

$$\begin{aligned} H(x,y,p,q)=\sum _{\pi \in \mathcal {CCP}}x^{h(\pi )}y^{v(\pi )}p^{deg_2(\pi )}q^{deg_4(\pi )} \end{aligned}$$

where \(deg_2(\pi )\) and \(deg_4(\pi )\) denotes the number of degree 2 and degree 4 corners in the polyomino \(\pi \). We obtain an exact expression for this generating function, and show that the average number of corners over all column-convex polyominoes of perimeter 2n is asymptotic to \(\alpha _1n\) where \(\alpha _1\approx 1.17157287\ldots \). We also use the generating functions F and H, and obtain the asymptotic order of the number of column-convex polyominoes which is given by \(\frac{c_1}{2n\sqrt{\pi n}}(3+2\sqrt{2})^n\) where \(c_1\approx 0.15099723\ldots \), see also [14].

Fig. 1
figure 1

An example of a polyomino with 19 cells, a horizontal perimeter of 10, a vertical perimeter of 20, interior vertices of 5, degree-2 boundary vertex of 11, and degree-4 boundary vertex of 7

Full size image

2 Results on the Internal Vertex Statistic

Let \(\pi \) be a nonempty column-convex polyomino with m columns such that the bottom cell of the first column lays on the x-axis. We say that a bottom (upper) cell of the ith column of \(\pi \) is at position k if it lays on (lays below and touches) the line \(y=k\).

Let \(F_a=F_a(x,y,t,q)\) be the generating function for the column-convex polyominoes with the first column of size a, according to the statistics \(h(\pi )\), \(v(\pi )\), \(area(\pi )\) and \(intv(\pi )\), counted by variables x, y, t and q, respectively. We introduce a decomposition method for column-convex polyominoes and calculate the related generating functions by using it. We call this decomposition \(\mathcal {CCP}\)-column decomposition. The details are as follows: we decompose a column-convex polyomino with the first column of size a by considering the size and the bottom-cell’s position of its second column, see Fig. 2.

Fig. 2
figure 2

\(\mathcal {CCP}\)-column decomposition of a column-convex polyomino

Full size image

  • Case I in Fig. 2: The column-convex polyomino has only one column;

  • Case II in Fig. 2: The size of the second column is b, \(1\le b\le a\), and its bottom cell is not below the line \(y=0\) and its upper cell is not above the line \(y=a\);

  • Case III in Fig. 2: The size of the second column is b, \(b\ge 2\), and its bottom cell is below the line \(y=0\) and its upper cell is not above the line \(y=a\);

  • Case IV in Fig. 2: The size of the second column is b, \(b\ge 2\), and its bottom cell is not below the line \(y=0\) and its upper cell is above the line \(y=a\);

  • Case V in Fig. 2: The size of the second column is b, \(b\ge a+2\), and its bottom cell is below the line \(y=0\) and its upper cell is above the line \(y=a\).

Thus,

$$\begin{aligned} F_a=xy^at^a&+\sum _{b=1}^a(a+1-b)q^{b-1}xy^{a-b}t^aF_b +2\sum _{b=2}^axt^a\frac{q^{b-1}y^{a+1-b}-y^a}{q-y}F_b\\&+2\sum _{b\ge a+1}xt^a\frac{y^a-q^a}{y-q}F_b +\sum _{b\ge a+2}(b-1-a)xt^aq^{a-1}F_b. \end{aligned}$$

We define \(F(u)=F(u;x,y,t,q)=\sum _{a\ge 1}F_au^{a-1}\). Then by multiplying the last recurrence by \(u^{a-1}\) and summing over all \(a\ge 1\), we obtain

$$\begin{aligned} F(u)&=\frac{xyt}{1-ytu}+\frac{xt}{(1-ytu)^2}F(qtu) +\frac{2xyt}{(q-y)(1-ytu)}(F(qtu)-F(1))\nonumber \\&\quad +\frac{2qxt(F(1)-F(qtu))}{(q-y)(1-qtu)}+\frac{xt}{(1-qtu)^2}(F(qtu)-F(0))\nonumber \\&\quad -\frac{xt}{(1-qtu)^2}(F(1)-F(0))+\frac{xt}{1-qtu}\frac{\partial }{\partial u}F(u)\mid _{u=1}. \end{aligned}$$
(2.1)

Note that by substituting \(u=0\) into (2.1), we obtain

$$\begin{aligned} \frac{\partial }{\partial u}F(u)\mid _{u=1}= \frac{1}{xt}F(0)-y-F(1). \end{aligned}$$

Thus, (2.1) can be written as

$$\begin{aligned} F(u)&=\frac{xyt}{1-ytu}+\frac{xt}{(1-ytu)^2}F(qtu) +\frac{2xyt}{(q-y)(1-ytu)}(F(qtu)-F(1))\nonumber \\&\quad +\frac{2qxt}{(q-y)(1-qtu)}(F(1)-F(qtu))+\frac{xt}{(1-qtu)^2}(F(qtu)-F(0))\nonumber \\&\quad -\frac{xt}{(1-qtu)^2}(F(1)-F(0))+\frac{1}{1-qtu}(F(0)-xyt-xtF(1)). \end{aligned}$$
(2.2)

Let \(G(u;x,y)=F(u;x,y,1,1)\). Then (2.2) with \(t=q=1\) gives

$$\begin{aligned}&\left( 1-\frac{(1-y)^2u^2x^2}{(1-u)^2(1-yu)^2}\right) G(u;x^2,y)\nonumber \\&\quad =-\frac{(1-2y+yu)ux^2}{(1-u)^2(1-yu)}G(1;x^2,y)+\frac{1}{1-u}G(0;x^2,y) -\frac{x^2yu(1-y)}{(1-u)(1-yu)}. \end{aligned}$$
(2.3)

This type of functional equation can be solved using the kernel method, see [2]. If we assume that u takes the values \(u_+\), \(u_-\) where

$$\begin{aligned}&u_+=u_+(x,y)=\frac{1+x+y-xy-\sqrt{(1+x+y-xy)^2-4y}}{2y},\\&u_-=u_-(x,y)=\frac{1-x+y+xy-\sqrt{(1-x+y+xy)^2-4y}}{2y}, \end{aligned}$$

with \(u_{\pm }\) satisfying

$$\begin{aligned} \frac{x(1-y)u_\pm }{(1-u_\pm )(1-yu_{\pm })}=\pm 1, \end{aligned}$$

then we have

$$\begin{aligned} -\frac{(1-2y+yu_\pm )ux^2}{(1-u_\pm )(1-yu_\pm )}G(1;x^2,y)+G(0;x^2,y) =\frac{x^2yu_\pm (1-y)}{1-yu_\pm }. \end{aligned}$$

Solving for \(G(1;x^2,y)\), we obtain the main result of this section, see also [14].

Theorem 2.1

The perimeter generating function for the column-convex polyominoes is given by

$$\begin{aligned} G(1;x,y)=-\frac{(1-y)(1-u_+(\sqrt{x},y))(1-u_-(\sqrt{x},y))y}{(1-yu_+(\sqrt{x},y))(1-yu_-(\sqrt{x},y))-2y(1-u_+(\sqrt{x},y))(1-u_-(\sqrt{x},y))}. \end{aligned}$$

Moreover, the perimeter generating function for the column-convex polyominoes with the first column of size one is given by

$$\begin{aligned} G(0;x,y)=\frac{xy(1-y)^2u_+(\sqrt{x},y)u_-(\sqrt{x},y)}{(1-yu_+(\sqrt{x},y))(1-yu_-(\sqrt{x},y))-2y(1-u_+(\sqrt{x},y))(1-u_-(\sqrt{x},y))}. \end{aligned}$$

Note that Theorem 2.1 also proves that \(G(1;x,y)=C(x,y)\) for all x, y and hence provides another proof of (1.1).

We can also find the asymptotic of the coefficient of \(x^n\) in the generating function G(1; x, x) which gives the number of colum-convex polyominoes of perimeter 2n. By singularity analysis, see [10], we have

$$\begin{aligned} G(1;x,x)=c_0-c_1\sqrt{1-x/r}+O(1-x/r), \end{aligned}$$

where

$$\begin{aligned} c_0&=\frac{2(1-2\sqrt{10-7\sqrt{2}})(7-\sqrt{2})}{47}=0.086983606\ldots ,\\ c_1&=\frac{2\sqrt{5\sqrt{2}-7}((138\sqrt{2}+444)\sqrt{10-7\sqrt{2}} +589\sqrt{2}-410)}{2209}=0.15099723\ldots . \end{aligned}$$

Hence, the coefficient of \(x^n\) in G(1; , x, x) is asymptotic to

$$\begin{aligned}{}[x^n]F(x,x,1,1)\sim \frac{c_1}{2n\sqrt{\pi n}}(3+2\sqrt{2})^n. \end{aligned}$$
(2.4)

Next, we will find the average number of interior vertices over all column-convex polyominoes with perimeter 2n. We need to consider some special cases of G(u; x, y).

By using (2.3), we obtain a formula for \(G(u;x^2,y)\).

Corollary 2.2

The generating function \(G(u;x^2,y)\) is given by

$$\begin{aligned} \frac{x^2y(1-y)^2(u-u_+)(u-u_-)(1-uy)}{((1-yu_+)(1-yu_-)-2y(1-u_+)(1-u_-))((yu^2-(1+y)u+1)^2-x^2(1-y)^2u^2)}. \end{aligned}$$

We define \(G'(u;x^2,y)=\frac{\partial }{\partial u}G(u;x^2,y)\). Note that, in particular, Corollary 2.2 gives the expressions for \(G(u_\pm ;x^2,y)\) and \(G'(u_\pm ;x^2,y)\) as follows:

Corollary 2.3

We have

$$\begin{aligned} G(u_\pm ;x^2,y)=\frac{\pm xy(1-y)(1-u_\pm y)(u_--u_+)}{2 (y(y-2)u_+u_-+y(u_++u_--2)+1)(2-(1\pm x+y\mp xy)u_\pm )}, \end{aligned}$$

and

$$\begin{aligned}&G'(u_\pm ;x^2,y)=\\&\frac{y^2L_\pm }{4((y-1)(1\mp x)^2\mp 4x)(1-(1\pm x+y\mp xy)u_\pm )(y(y-2)u_+u_-+y(u_++u_--2)+1)}, \end{aligned}$$

where

$$\begin{aligned} L_\pm&=(y-1)(u_\mp -1)(yu_\pm -1) \pm (2y(1-2y)u_+u_-+3y^2u_\pm +2yu_\mp -u_\pm -2y)x\\&\quad +(y-1)(3yu_\pm (u_\mp -1)+u_\mp +1)x^2\pm u_\pm (y-1)^2x^3. \end{aligned}$$

We are ready to find the generating function for the column-convex polyominoes according to the semi-perimeters and number of interior vertices.

Define \(Q(u;x,y)=\frac{\partial }{\partial q}F(u;x,y,1,q)\mid _{q=1}\), and \(Q'(u;x,y)=\frac{\partial }{\partial u}Q(u;x,y)\). By differentiating (2.2) at \(q=1\), we have

$$\begin{aligned}&\left( 1-\frac{x^2(1-y)^2u^2}{(1-u)^2(1-uy)^2}\right) Q(u;x^2,y)=\frac{x^2(1-2u+yu)}{(1-u)^2(1-yu)}Q(1;x^2,y)\nonumber \\&\quad +\frac{x^2(1-y)^2u^3}{(1-u)^2(1-uy)^2}G'(u;x^2,y)+\frac{x^2u}{(1-u)^2}G'(1;x^2,y)+\frac{x^2}{1-u}Q'(1;x^2,y)\\&\quad +\frac{2x^2(1-y)u^2}{(1-u)^3(1-yu)}G(u;x^2,y)-\frac{2x^2(1-y)u^2}{(1-u)^3(1-uy)}G(1;x,y).\nonumber \end{aligned}$$
(2.5)

Note that by substituting \(u=0\) into (2.5) gives

$$\begin{aligned} x^2Q(1;x^2,y)+x^2Q'(1;x^2,y)-Q(0;x^2,y)=0 \end{aligned}$$

and by (2.1), we obtain

$$\begin{aligned} G'(1;x^2,y)= \frac{1}{x^2}G(0;x^2,y)-y-G(1;x^2,y). \end{aligned}$$

Hence, (2.5) gives

$$\begin{aligned}&\left( 1-\frac{x^2(1-y)^2u^2}{(1-u)^2(1-uy)^2}\right) Q(u;x^2,y)\nonumber \\&\quad =-\frac{x^2(1-2y+yu)u}{(1-u)^2(1-yu)}Q(1;x^2,y)+\frac{1}{1-u}Q(0;x^2,y)\nonumber \\&\qquad +\frac{x^2(1-y)^2u^3}{(1-u)^2(1-uy)^2}G'(u;x^2,y)\nonumber \\&\qquad +\frac{2x^2(1-y)u^2}{(1-u)^3(1-yu)}G(u;x^2,y) -\frac{x^2(1+u-3yu+yu^2)u}{(1-u)^3(1-uy)}G(1;x^2,y)\nonumber \\&\qquad +\frac{u}{(1-u)^2}G(0;x^2,y) -\frac{x^2yu}{(1-u)^2}. \end{aligned}$$
(2.6)

As before, by substituting \(u=u_\pm \), we obtain the following two equations:

$$\begin{aligned}&\frac{x^2(1-2y+yu_\pm )u_\pm }{(1-u_\pm )(1-yu_\pm )}Q(1;x^2,y)-Q(0;x^2,y)\\&\quad =\frac{x^2(1-y)^2u_\pm ^3}{(1-u_\pm )(1-yu_\pm )^2}G'(u_\pm ;x^2,y)\\&\qquad +\frac{2x^2(1-y)u_\pm ^2}{(1-u_\pm )^2(1-yu_\pm )}G(u_\pm ;x^2,y) -\frac{x^2(1+u_\pm -3yu_\pm +yu_\pm ^2)u_\pm }{(1-u_\pm )^2(1-yu_\pm )}G(1;x^2,y)\\&\qquad +\frac{u_\pm }{1-u_\pm }G(0;x^2,y) -\frac{x^2yu_\pm }{1-u_\pm }. \end{aligned}$$

Hence, by subtracting these two equations, we obtain the following result.

Theorem 2.4

We have

$$\begin{aligned} Q(1;x^2,y)=\frac{R(x,u_+)-R(x,u_-)}{\frac{x^2(1-2y+yu_+)u_+}{(1-u_+)(1-yu_+)}-\frac{x^2(1-2y+yu_-)u_-}{(1-u_-)(1-yu_-)}}. \end{aligned}$$

where

$$\begin{aligned} R(x,u)&=\frac{x^2(1-y)^2u^3}{(1-u)(1-yu)^2}G'(u;x^2,y)+\frac{2x^2(1-y)u^2}{(1-u)^2(1-yu)}G(u;x^2,y)\\&\quad -\frac{x^2(1+u-3yu+yu^2)u}{(1-u)^2(1-yu)}G(1;x^2,y)+\frac{u}{1-u}G(0;x^2,y) -\frac{x^2yu}{1-u}. \end{aligned}$$

Note that the expressions for \(G(u_\pm ;x^2,y)\) and \(G'(u_\pm ;x^2,y)\) are given in Corollary 2.3 and the expressions for \(G(1;x^2,y)\) and \(G(0;x^2,y)\) are given in Theorem 2.1.

After several algebraic operations, the generating function \(Q(1;x^2,x^2)\) for the total number of interior vertices over all polyominoes of perimeter 2n can be written as

$$\begin{aligned} Q(1;x^2,x^2)&=\frac{a(x^2)}{4(1+x^2)(2x^6-23x^4+38x^2-18)^2((1-x^2)^2-4x^2)}\\&\quad +\frac{\sqrt{1-x^2}(b(x)+b(-x))}{4x\sqrt{1+x^2}(2x^6-23x^4+38x^2-18)^2}\\&\quad +\frac{(1-x^2)c(x^2)}{4(2x^6-23x^4+38x^2-18)^2\sqrt{(1-x^2)^2-4x^2}}, \end{aligned}$$

where

$$\begin{aligned} a(x)&=-11x^9-11x^8+1084x^7-4684x^6+6617x^5+217x^4-9836x^3+9892x^2\\&\quad -3702x+402,\\ b(x)&=\frac{\begin{array}{l} 4x^{17}-7x^{16}-17x^{15}+75x^{14}+4x^{13}-456x^{12}+65x^{11} +1213x^{10}-1272x^9\\ -1663x^8+3322x^7+1410x^6-3398x^5-742x^4+1490x^3+230x^2-198x-36 \end{array}}{(1+2x-x^2)\sqrt{1-2x-x^2}},\\ c(x)&=-21x^6+172x^5-553x^4+1072x^3-1026x^2+480x-78. \end{aligned}$$

Note that generating function Q(1; x, x) is analytic in the disk \(|x|<r=(\sqrt{2}-1)^2\), while it has a singular point at \(x=r\). Moreover,

$$\begin{aligned} Q(1;x,x)=\frac{794\sqrt{2}-999+6(51-14\sqrt{2})\sqrt{10-7\sqrt{2}}}{8836(1-x/r)}+O(1/\sqrt{1-x/r}). \end{aligned}$$

Hence, by Theorem IV.5 in [10] and (2.4), we can state the following result.

Theorem 2.5

The average number of interior vertices over all column-convex polyominoes of perimeter 2n is asymptotic to

$$\begin{aligned} \frac{\left( 794\sqrt{2}-999+6(51-14\sqrt{2})\sqrt{10-7\sqrt{2}}\right) \sqrt{\pi }}{2\sqrt{2}(12(209-144\sqrt{2}) +(589\sqrt{2}-410)\sqrt{10-7\sqrt{2}})} n^{3/2} \end{aligned}$$

where the coefficient is approximately equal to \(0.57895563\ldots .\)

3 Results on the Corner Statistic

Recall that the generating function for the number of column-convex polyominoes according to the statistics \(h(\pi )\), \(v(\pi )\), \(deg_2(\pi )\) and \(\deg _4(\pi )\), counted by x, y, p and q, respectively, is defined by

$$\begin{aligned} H(x,y,p,q)=\sum _{\pi \in \mathcal {CCP}}x^{h(\pi )}y^{v(\pi )}p^{deg_2(\pi )}q^{deg_4(\pi )} \end{aligned}$$

where \(deg_2(\pi )\) and \(deg_4(\pi )\) denote the number of degree 2 and degree 4 corners in the polyomino \(\pi \). The main result of this section is the following:

Theorem 3.1

The generating function H is given by

$$\begin{aligned} H(x,y,p,q)=-\frac{y(1-y)p^2(1-v_+)(1-v_-)}{q^2((1-v_+y)(1-v_-y)-2y(1-v_+)(1-v_-))}, \end{aligned}$$

where

$$\begin{aligned} v_\pm&=\frac{(1\mp \sqrt{x})(1+y)\pm 2pq\sqrt{x}y-\sqrt{((1\mp \sqrt{x})(1+y)\pm 2pq\sqrt{x}y)^2-4y(1\mp \sqrt{x}\pm pq\sqrt{x})^2}}{2y(1\mp \sqrt{x}\pm pq\sqrt{x})}. \end{aligned}$$

For instance, \(H(x,y,p,q)=p^4xy+p^4xy^2+p^4x^2y+p^4xy^3+\mathbf{p^4(4pq+1)}x^2y^2+p^4x^3y+ p^4xy^4+p^4(4p^2q^2+8pq+1)x^2y^3+ p^4(4p^2q^2+8pq+1)x^3y^2+p^4x^4y+\cdots \), where the bold coefficient counts the 5 column-convex polyominoes in Fig. 3.

Fig. 3
figure 3

Polyominoes with horizontal and vertical perimeter of 4

Full size image

Note that Theorem 3.1 with \(p=q=1\) gives (1.1). Indeed, the Proof of Theorem 3.1 provides a different proof of (1.1). As an application of Theorem 3.1, in Corollary 3.3, we show that the average number of corners over all column-convex polyominoes of perimeter 2n is asymptotic to

$$\begin{aligned} \frac{4(6(51-14\sqrt{2})\sqrt{10-7\sqrt{2}} +794\sqrt{2}-999)}{ 6(23\sqrt{2}+74)\sqrt{10-7\sqrt{2}}+589\sqrt{2}-410}n \end{aligned}$$

where the coefficient is approximately equal to \(1.17157287\ldots .\) For the asymptotic results for corners of degrees 2 and 4, see Corollary 3.4.

Let \(\pi \) be any nonempty polyomino with m columns such that the bottom cell of the first column lays on the x-axis. We say that a bottom (upper) cell of the ith column of \(\pi \) is at position k if it lays on (lays below and touches) the line \(y=k\).

Let \(H_a=H_a(x,y,p,q)\) be the generating function for the column-convex polyominoes with the first column of size a, according to the statistics \(h(\pi )\), \(v(\pi )\), \(deg_2(\pi )\) and \(deg_4(\pi )\), counted by variables x, y, p and q, respectively. We will first write an equation for the generating function \(H_a\) by making use of \(\mathcal {CCP}\)-column decomposition as used in Sect. 2. See also Fig. 2:

  • Case I in Fig. 2: The column-convex polyomino has only one column. Thus the contribution of this case is given by \(xy^ap^4\).

  • Case II in Fig. 2: The size of the second column is b, \(1\le b\le a\), and its bottom cell is not below the line \(y=0\) and its upper cell is not above the line \(y=a\). Thus, the contribution of this case is given by \(xy^{a-b}(2pq+p^2q^2(a-1-b))H_b\) when \(b=1,2,\ldots ,a-1\) and \(xH_b\) when \(b=a\).

  • Case III in Fig. 2: The size of the second column is b, \(b\ge 2\), and its bottom cell is below the line \(y=0\) and its upper cell is not above the line \(y=a\). Thus, the contribution of this case is given by \(xp^2q^2\frac{y^{a+1-b}-y^a}{1-y}H_b\) when \(2\le b\le a\), \(xp^2q^2\frac{y-y^a}{1-y}H_b\) when \(b\ge a+1\) and the upper cell of the second column is not above the line \(y=a-1\), and \(xpqH_b\) when \(b\ge a+1\) and the upper cell of the second column is below and touches the line \(y=a\).

  • Case IV in Fig. 2: The size of the second column is b, \(b\ge 2\), and its bottom cell is not below the line \(y=0\) and its upper cell is above the line \(y=a\). As In case III, the contribution of this case is given by \(xp^2q^2\frac{y^{a+1-b}-y^a}{1-y}H_b\) when \(2\le b\le a\), \(xp^2q^2\frac{y-y^a}{1-y}H_b\) when \(b\ge a+1\) and the lower cell of the second column is not below the line \(y=1\), and \(xpqH_b\) when \(b\ge a+1\) and the lower cell of the second column is above and touches the line \(y=0\).

  • Case V in Fig. 2: The size of the second column is b, \(b\ge a+2\), and its bottom cell is below the line \(y=0\) and its upper cell is above the line \(y=k\). The contribution of this case is given by \(xp^2q^2(b-1-a)H_b\) when \(b\ge a+2\).

Thus,

$$\begin{aligned} H_a&=xy^ap^4+x\sum _{b=1}^{a-1}y^{a-b}(2pq+p^2q^2(a-1-b))H_b+xH_b +2xp^2q^2\sum _{b=2}^a \frac{y^{a+1-b}-y^a}{1-y}H_b\\&\quad +2xp^2q^2\sum _{b\ge a+1}\frac{y-y^a}{1-y}H_b+ 2xpq\sum _{b\ge a+1}H_b+xp^2q^2\sum _{b\ge a+2}(b-1-a)H_b, \end{aligned}$$

We define \(H(u)=H(u;x,y,p,q)=\sum _{a\ge 1}H_au^{a-1}\).

Then by multiplying the last recurrence by \(u^{a-1}\) and summing over all \(a\ge 1\), we obtain

$$\begin{aligned} H(u)&=\frac{xyp^4}{1-yu}+\frac{xy^2p^2q^2u^2}{(1-yu)^2}H(u) +\frac{2xypqu}{1-yu}H(u)+xH(u)\\&\quad +\frac{2xyp^2q^2H(u)}{(1-y)(1-yu)}+\frac{2xyp^2q^2uH(1)}{(1-u)(1-yu)}-\frac{2xyp^2q^2H(u)}{(1-u)(1-y)} +\frac{2xpq(H(1)-H(u))}{1-u}\\&\quad +\frac{xp^2q^2}{(1-u)^2}(H(u)-H(0))-\frac{xp^2q^2}{(1-u)^2}(H(1)-H(0)) +\frac{xp^2q^2}{1-u}\frac{d}{du}H(u)\mid _{u=1}, \end{aligned}$$

which is equivalent to

$$\begin{aligned}&\left( 1-\frac{(y(pq-1)u^2+(1+y-2ypq)u+pq-1)^2x^2}{(1-u)^2(1-yu)^2}\right) H(u,x^2,y,p,q)\nonumber \\&\quad =\frac{x^2pq(2-pq+(3pqy-2y-2)u+2y(1-pq)u^2)}{(1-u)^2(1-yu)}H(1;x^2,y,p,q)\\&\qquad +\frac{x^2yp^4}{1-yu}+\frac{x^2p^2q^2}{1-u}\frac{d}{du}H(u;x^2,y,p,q)\mid _{u=1}.\nonumber \end{aligned}$$
(3.1)

We will solve this functional equation by using the kernel method. If we assume that u takes the values of \(u_+, u_-\) where

$$\begin{aligned} u_+&=u_+(x,y,p,q)\\&=\frac{1-x+y-xy+2pqxy-\sqrt{(1-x+y-xy+2pqxy)^2-4y(1-x+pqx)^2}}{2y(1-x+pqx)},\\ u_-&=u_-(x,y,p,q)\\&=\frac{1+x+y+xy-2pqxy-\sqrt{(1+x+y+xy-2pqxy)^2-4y(1+x-pqx)^2}}{2y(1+x-pqx)}, \end{aligned}$$

with \(u=u_{\pm }\) satisfying

$$\begin{aligned} 1-\frac{(y(pq-1)u^2+(1+y-2ypq)u+pq-1)^2x^2}{(1-u)^2(1-yu)^2}=0, \end{aligned}$$

then, we obtain

$$\begin{aligned}&\frac{q(2-pq+(3pqy-2y-2)u_++2y(1-pq)u_+^2)}{(1-u_+)(1-yu_+)}H(1;x^2,y,p,q)\\&\quad +\frac{yp^3(1-u_+)}{1-yu_+}+pq^2\frac{d}{du}H(u;x^2,y,p,q)\mid _{u=1}=0,\\&\frac{q(2-pq+(3pqy-2y-2)u_-+2y(1-pq)u_-^2)}{(1-u_-)(1-yu_-)}H(1;x^2,y,p,q)\\&\quad +\frac{yp^3(1-u_-)}{1-yu_-}+pq^2\frac{d}{du}H(u;x^2,y,p,q)\mid _{u=1}=0. \end{aligned}$$

By solving this system for \(H(1;x^2,y,p,q)\), we obtain

$$\begin{aligned} H(1;x^2,y,p,q)=-\frac{y(1-y)p^2(1-u_+)(1-u_-)}{q^2((1-u_+y)(1-u_-y)-2y(1-u_+)(1-u_-))}, \end{aligned}$$

which, by substituting expressions of \(u_\pm \), completes the Proof of Theorem 3.1.\(\square \)

Note that \(cor(\pi )=deg_2(\pi )+deg_4(\pi )\) is the number of all corners in \(\pi \). Thus, by Theorem 3.1, we have the following corollary.

Corollary 3.2

We set \(v_\pm (x,y,p,q)=u_\pm (\sqrt{x},y,p,q)\). Then

  1. (i)

    The generating function for the column-convex polyominoes according to the statistics \(h(\pi )\), \(v(\pi )\), and the number of corners, counted by x, y and q, respectively, is given by

    $$\begin{aligned} \frac{-y(1-y)(1-v_+(x,y,q,q))(1-v_-(x,y,q,q))}{(1-yv_+(x,y,q,q))(1-yv_-(x,y,q,q))-2y(1-v_+(x,y,q,q))(1-v_-(x,y,q,q))}. \end{aligned}$$
  2. (ii)

    The generating function for the column-convex polyominoes according to the statistics \(h(\pi )\), \(v(\pi )\) and \(deg_2(\pi )\), counted by x, y and p, respectively, is given by

    $$\begin{aligned} \frac{-y(1-y)p^2(1-v_+(x,y,p,1))(1-v_-(x,y,p,1))}{((1-yv_+(x,y,p,1))(1-yv_-(x,y,p,1))-2y(1-v_+(x,y,p,1))(1-v_-(x,y,p,1)))}. \end{aligned}$$
  3. (iii)

    The generating function for the column-convex polyominoes according to the statistics \(h(\pi )\), \(v(\pi )\) and \(deg_4(\pi )\), counted by x, y and q, respectively, is given by

    $$\begin{aligned} \frac{-y(1-y)(1-v_+(x,y,1,q))(1-v_-(x,y,1,q))}{q^2((1-yv_+(x,y,1,q))(1-yv_-(x,y,1,q))-2y(1-v_+(x,y,1,q))(1-v_-(x,y,1,q)))}. \end{aligned}$$

We can find the asymptotic of the coefficient of \(x^n\) in the generating function H(x, x, 1, 1). Let \(r=3-2\sqrt{2}\), by singularity analysis, see [10], we have

$$\begin{aligned} H(x,x,1,1)=c_0-c_1\sqrt{1-x/r}+O(1-x/r), \end{aligned}$$

where

$$\begin{aligned} c_0&=\frac{2(1-2\sqrt{10-7\sqrt{2}})(7-\sqrt{2})}{47}=0.086983606\ldots ,\\ c_1&=\frac{2\sqrt{5\sqrt{2}-7}((138\sqrt{2}+444)\sqrt{10-7\sqrt{2}} +589\sqrt{2}-410)}{2209}=0.15099723\ldots . \end{aligned}$$

Hence, the coefficient of \(x^n\) in H(x, x, 1, 1) is asymptotic to

$$\begin{aligned}{}[x^n]H(x,x,1,1)\sim \frac{c_1}{2n\sqrt{\pi n}}(3+2\sqrt{2})^n. \end{aligned}$$
(3.2)

In the following, we study the average number of of corners, the sum of the corners of degrees 2 and 4, in column-convex polyominoes of perimeter 2n.

By differentiating H(x, x, q, q) at \(q=1\), Corollary 3.2 gives

$$\begin{aligned}&\frac{\partial }{\partial q}H(x,x,q,q)\mid _{q=1}\\&\quad =\frac{y(1-y)^2(yv'_+v_-^2+yv_+^2v'_--(1+y)v'_+v_--(1+y)v_+v'_-+v_+'+v_-')}{(y^2v_+v_--2yv_+v_-+y(v_++v_-)-2y+1)^2}, \end{aligned}$$

where \(v_\pm =u_\pm (\sqrt{x},x,1,1)\) and \(v'_\pm =\frac{\partial }{\partial q}u_\pm (\sqrt{x},x,q,q)\mid _{q=1}\). After substituting the expressions of \(v_\pm \) and \(v'_\pm \) into \(\frac{\partial }{\partial q}H(x,x,q,q)\mid _{q=1}\), we obtain

$$\begin{aligned}&\frac{\partial }{\partial q}H(x,x,q,q)\mid _{q=1}=\frac{d_0}{\sqrt{1-x/r}}+d_1+O(\sqrt{1-x/r}), \end{aligned}$$

where

$$\begin{aligned} d_0&=\frac{24(51-14\sqrt{2})\sqrt{10-7\sqrt{2}}\sqrt{5\sqrt{2}-7} +4(794\sqrt{2}-999)\sqrt{5\sqrt{2}-7}}{2209}\\&=0.08845213\ldots ,\\ d_1&=\frac{24(97025-68562\sqrt{2})}{103823} +\frac{2(190697\sqrt{2}-269765)\sqrt{10-7\sqrt{2}}}{103823}\\&=0.0142419\ldots . \end{aligned}$$

Hence, the coefficient of \(x^n\) in \(\frac{\partial }{\partial q}H(x,x,q,q)\mid _{q=1}\) is asymptotic to \(\frac{d_0}{\sqrt{\pi n}}(3+2\sqrt{2})^n\). Thus, by (3.2), we have the following result.

Corollary 3.3

The average  number  of corners  over all column-convex polyominoes of perimeter 2n is asymptotic to

$$\begin{aligned} \frac{2d_0n}{c_1}=\frac{4(6(51-14\sqrt{2})\sqrt{10-7\sqrt{2}} +794\sqrt{2}-999)}{ 6(23\sqrt{2}+74)\sqrt{10-7\sqrt{2}}+589\sqrt{2}-410}n \end{aligned}$$

where the coefficient is approximately equal to \(1.17157287\ldots .\)

3.1 Corners of Degree Either 2 or 4

Similar arguments as in the above subsection (counting all corners), where we consider the generating functions \(\frac{\partial }{\partial p}H(x,x,p,1)\mid _{p=1}\) and \(\frac{\partial }{\partial p}H(x,x,1,q)\mid _{q=1}\), Corollary 3.2 leads to the following result.

Corollary 3.4

The average number of corners of degree 2 (degree 4) over all column-convex polyominoes of perimeter 2n is asymptotic to

$$\begin{aligned} \frac{2(6(51-14\sqrt{2})\sqrt{10-7\sqrt{2}} +794\sqrt{2}-999)}{ 6(23\sqrt{2}+74)\sqrt{10-7\sqrt{2}}+589\sqrt{2}-410}n, \end{aligned}$$

where the coefficient is approximately equal to \(0.5857864358\ldots \).