Fibonacci and Catalan Numbers Meet in Staircase Polyominoes
June 11, 2026
Abstract
We study Fibonacci (staircase) polyominoes, a class of column-convex polyominoes whose lower boundary is a staircase with unit vertical steps. We derive multivariate generating functions that refine Turban’s Fibonacci-number enumeration by tracking additional perimeter and area parameters. The proofs use a catalytic functional equation and, in a perimeter specialization, the kernel method, leading to explicit closed forms and Catalan-number coefficient formulas.
1 Introduction↩︎
The enumeration of polyomino classes defined by convexity and directionality constraints is a classical topic in enumerative combinatorics; see [@Book1] and the references therein. A polyomino is a finite edge-connected union of unit squares in \({\mathbb{Z}}^2\).
Among the many families studied with respect to parameters such as area and perimeter [@BleBreKnop3; @Bou; @ManSha2], Turban [@Turban1] introduced a particularly natural class of Fibonacci polyominoes. These are column-convex polyominoes whose lower boundary is a staircase path with unit vertical steps (see Figure 1). Turban proved that the number of such polyominoes of area \(n\) equals the Fibonacci number \(F_n\), and considered variants allowing staircase steps of arbitrary heights [@Turban1; @Turban2].
In this paper we refine Turban’s enumeration by deriving multivariate generating functions that track additional parameters.
2 Perimeter and area↩︎
For a Fibonacci polyomino \(P\), let \({\texttt{area}}(P)\) denote its area (number of cells). Write \({\texttt{sper}}(P)\) for the semiperimeter, i.e., half of the number of unit edges on the boundary of \(P\). We further split it into the horizontal and vertical contributions: \({\texttt{xper}}(P)\) is half of the number of horizontal boundary edges (or number of columns of \(P\)) and \({\texttt{yper}}(P)\) is half of the number of vertical boundary edges. Thus \({\texttt{sper}}(P)={\texttt{xper}}(P)+{\texttt{yper}}(P)\).
Let \({\boldsymbol{F}}\) be the class of all Fibonacci polyominoes. For \(m,n,k\in{\mathbb{Z}}_{>0}\), let \({\boldsymbol{F}}_{m,n,k}\) be the subset consisting of those \(P\) with \(2m\) horizontal boundary edges, \(2n\) vertical boundary edges, and area \(k\), with \(n\geq m\) and \(k\geq 2m-1\). Equivalently, \({\boldsymbol{F}}=\bigcup_{m,n,k\ge 1}{\boldsymbol{F}}_{m,n,k}\). We encode these statistics by the trivariate generating function \[F(x,y,q)=\sum_{P\in{\boldsymbol{F}}} x^{{\texttt{xper}}(P)}\,y^{{\texttt{yper}}(P)}\,q^{{\texttt{area}}(P)} =\sum_{m,n,k\ge 1}\left(\sum_{P\in{\boldsymbol{F}}_{m,n,k}}1\right)x^m y^n q^k.\]
To keep track of the height of the first column, let \(F_h(x,y,q)\) be the generating function of Fibonacci polyominoes whose first column has height exactly \(h\ge1\), so that \(F(x,y,q)=\sum_{h\ge1}F_h(x,y,q)\). Introducing a catalytic variable \(s\) marking this height, we set \[F(x,y,q;s)=\sum_{h\ge1} F_h(x,y,q)\,s^h, \qquad\text{so that}\qquad F(x,y,q;1)=F(x,y,q).\] For brevity, write \(F(s):=F(x,y,q;s)\) and \(F(1):=F(x,y,q)\).
A decomposition according to the possible configurations of the final columns yields the functional equation \[\label{eq:functionalareaper} F(s) = \frac{xyqs}{1-yqs} + \frac{xy (qs)^{2}}{1-qs}\, F(1) + \left( \frac{x (yqs)^{2}}{1-yqs} - \frac{xy(qs)^{2}}{1-qs} \right) F(sq).\tag{1}\] Iterating 1 (with the convention that an empty product equals \(1\)) and then setting \(s=1\) gives an explicit closed form for \(F(x,y,q)\).
Theorem 1. The generating function of nonempty Fibonacci polyominoes according to horizontal semiperimeter, vertical semiperimeter, and area is \[F(x,y,q) =\frac{ \sum_{\ell\ge 0} \left( \frac{(xy)^{\ell+1} q^{(\ell+1)^{2}}(y-1)^{\ell}}{1-yq^{\ell+1}} \prod_{i=0}^{\ell-1}\frac{1}{(1-yq^{i+1})(1-q^{i+1})} \right)}{ 1-\sum_{\ell\ge 0} \left( \frac{(xy)^{\ell+1} q^{(\ell+1)(\ell+2)}(y-1)^{\ell}}{1-q^{\ell+1}} \prod_{i=0}^{\ell-1}\frac{1}{(1-yq^{i+1})(1-q^{i+1})} \right)}.\]
As a consistency check, specializing 1 at \(s=x=y=1\) gives, with \(F(q):=F(1,1,q)\), \[F(q)=\frac{q}{1-q}+\frac{q^2}{1-q}F(q), \qquad\text{hence}\qquad F(q)=\frac{q}{1-q-q^2}.\] Therefore the coefficient of \(q^n\) is the Fibonacci number \(F_n\), recovering Turban’s enumeration by area.
2.1 Perimeter↩︎
We now specialize to perimeter enumeration by discarding the area statistic, that is, by setting \(q=1\) in 1 . In this specialization, the series \(F(1)=F(x,y,1)\) is precisely the bivariate generating function that counts Fibonacci polyominoes by horizontal and vertical semiperimeter.
Setting \(q=1\) in 1 gives a linear functional equation in \(F(s)\): \[\left(1-\frac{x(sy)^2}{1-sy}+\frac{xys^2}{1-s}\right)F(s) =\frac{xys}{1-ys}+\frac{xys^2}{1-s}\,F(1).\]
Let \(p(m,n)\) be the number of Fibonacci polyominoes whose boundary has \(2m\) horizontal edges and \(2n\) vertical edges, and set \[P(x,y):=\sum_{m,n\ge1} p(m,n)\,x^m y^n.\] By definition, \(P(x,y)=F(1)\). We compute it via the kernel method [@ban; @pro]. Denote the kernel by \[K(s):=1-\frac{x(sy)^2}{1-sy}+\frac{xys^2}{1-s}.\] Choosing \(s=s_0(x,y)\) so that \(K(s_0)=0\) cancels the left-hand side and yields an explicit expression for \(F(1)\) from the right-hand side. We take the small root (analytic at \(x=0\)), namely \[s_0=\frac{1+y+\sqrt{(1-y)(1-y-4xy)}}{2y\bigl(1+x(1-y)\bigr)}.\]
Theorem 2. The generating function for nonempty Fibonacci polyominoes according to horizontal and vertical semiperimeter is \[P(x,y)=\frac{1 + x - y - 3xy -(1+x)\sqrt{(1-y)(1-y-4xy)}}{2x}.\]
The first few terms of the expansion of \(P(x,y)\) in powers of \(y\) are \[\begin{gather} P(x,y)= x y+\left(x^2+x\right) y^2+\left(2 x^3+3 x^2+x\right) y^3\\+\left(5 x^4+\boldsymbol{9 x^3}+5 x^2+x\right) y^4+\left(14 x^5+29 x^4+21 x^3+7 x^2+x\right) y^5+O\left(y^6\right). \end{gather}\]
The bold coefficients in the above expansion correspond to the Fibonacci polyominoes shown in Figure 2.
We denote by \(C_n=\frac{1}{n+1}\binom{2n}{n}\) the \(n\)th Catalan number, and let \[C(z)=\sum_{n\geq 0}C_n z^n=\frac{1-\sqrt{1-4z}}{2z}\] be its generating function. From the previous theorem we obtain an explicit expression for the coefficients of \(P(x,y)\) in terms of Catalan numbers.
Theorem 3. For \(m\geq 1\) and \(n\geq 2\), we have \[p(m,n)=[x^my^n]P(x,y)=C_m \binom{n - 2}{m - 1} + C_{m - 1} \binom{n- 2}{m - 2}.\] In particular, for \(n\geq 2\), \(p(n,n)=C_{n-1}.\)
Notice that for the case \(n=m\) we can give a combinatorial argument. Let \(P\) be a Fibonacci polyomino whose boundary has exactly \(2n\) horizontal and \(2n\) vertical edges. This implies that \(P\) has \(n\) columns. Observe that the bottom cell of each column produces (on its right side) a vertical edge lying into the boundary. So, \(P\) has exactly \(n\) other vertical edges in the boundary, which implies that the number of cells in the \(i\)th column is at most \(n-i+1\). Moreover, this also implies that there is no descent in the polyomino, which means that the number of cells in the \(i\)th column is at most equal to the number plus one of cells in the \((i+1)\)th column. Let \(a_i\), \(1\leq i\leq n\), be the number of cells in the column \(i\). Then we have \(2\leq a_i\) for \(1\leq i\leq n-1\), \(a_n=1\), and \(a_i-2\leq a_{i+1}-1\), which proves that the word \(b_1b_2\cdots b_{n-1}=(a_{n-1}-2)(a_{n-2}-2)\cdots (a_1-2)\) is a Catalan word, that is \(0\leq b_i\leq n-1\) and \(b_{i+1}\leq b_{i}+1\). It is well known that these sequences are enumerated by the \((n-1)\)th Catalan number (cf. [@CatWordsBargraphs]).
For example, the Catalan words of length \(n=3\) are \(000, 001, 010, 011,\) and \(012\). The corresponding Fibonacci polyominoes are shown in Figure 3.
Notice that in the case \(n = m\), \(n\) is also the number of rows and the polyominoes are parallelogram polyominoes having the same number of rows and columns, so the upper boundary is an elevated Dyck path of length \(2n\) and, consequently, they are enumerated by the \((n-1)\)-th Catalan number.
[@*]