In this paper, we study additional aspects of the capacity distribution on the set ℬn of compositions of n consisting of 1’s and 2’s extending recent results of Hopkins and Tangboonduangjit. Among our results are further recurrences for this distribution as well as formulas for the total capacity and sign balance on ℬn. We provide algebraic and combinatorial proofs of our results. We also give combinatorial explanations of some prior results where such a proof was requested. Finally, the joint distribution of the capacity statistic with two further parameters on ℬn is briefly considered.
A composition of a positive integer \(n\) is a sequence of positive integers, called parts, whose sum is \(n\). A composition \(\pi\) is often represented as a vector \((\pi_1,\ldots,\pi_r)\) whose components are the parts of \(\pi\), or sequentially as \(\pi_1\cdots \pi_r\), where the commas between the parts are omitted. In the latter case, a sequence of \(\ell\) consecutive parts of the same size \(a\) is usually denoted by \(a^\ell\). Let \(\mathcal{C}_n\) denote the set of compositions of \(n\) for \(n \geq 1\), with \(\mathcal{C}_0\) consisting of the single empty composition with zero parts. For example, if \(n=4\), then \[\mathcal{C}_4=\{(1,1,1,1),(1,1,2),(1,2,1),(1,3),(2,1,1),(2,2),(3,1),(4)\}.\] It is well-known that \(|\mathcal{C}_n|=2^{n-1}\) for all \(n \geq 1\).
Given a word \(w=w_1\cdots w_m\) on the alphabet of positive integers, the bargraph of \(w\), denoted by \(b(w)\), consists of \(m\) columns starting from a horizontal line each comprised of unit squares, called cells, such that the \(i\)-th column from the left contains \(w_i\) cells for \(1 \leq i \leq m\). Here, we will represent a composition \(\pi=\pi_1\cdots\pi_r \in \mathcal{C}_n\) geometrically as a bargraph containing \(r\) columns and \(n\) cells altogether. We will frequently identify a composition \(\pi\) with its bargraph \(b(\pi)\), and vice versa, and treat the two interchangeably when speaking of a statistic defined on either.
By a water cell of a composition \(\pi\), we mean a unit square lying outside of \(b(\pi)\) that would “hold water” by virtue of its location, assuming the usual rules of water flow. The capacity of \(\pi\), denoted by \(\text{cap}(\pi)\), will refer to the number of its water cells. See Figure 1 below illustrating the bargraph of \(\pi\in\mathcal{C}_{30}\), which has 15 parts and a capacity of 10. The capacity statistic has been studied on a variety of discrete structures, represented as bargraphs, such as \(k\)-ary words [2], compositions [3, 7], permutations [4] and set partitions [7].
Let \(\mathcal{B}_n\) denote the set of compositions of \(n\) with parts in \(\{1,2\}\) and let \(f_n=f_{n-1}+f_{n-2}\) denote the \(n\)-th Fibonacci number, with \(f_0=f_1=1\). It is well-known (see, e.g., [10]) that the cardinality of \(\mathcal{B}_n\) is given by \(f_n\) for all \(n \geq0\). In [6], Hopkins and Tangboonduangjit considered the restriction of the capacity statistic to \(\mathcal{B}_n\). Let \(\mathcal{B}_{n,k}\) denote the subset of \(\mathcal{B}_n\) whose members contain exactly \(k\) water cells and let \(w(n,k)=|\mathcal{B}_{n,k}|\). Illustrated in Figure 2 below is the lone member of \(\mathcal{B}_{5,1}\), which is seen to be the unique smallest composition with one water cell, and two members of \(\mathcal{B}_{9,3}\), where the water cells are shaded. Among the results in [6] are various recurrences for \(w(n,k)\), expressions for \(w(n,0)\) and an explicit as well as a generating function formula for the diagonal sum \(\sum\limits_{k=0}^nw(n-k,k)\). In this paper, we study further aspects of the capacity distribution on \(\mathcal{B}_n\) such as the average capacity and sign balance (i.e., the difference in cardinality of those members of \(\mathcal{B}_n\) containing an even versus an odd number of water cells). We also establish an explicit formula for \(w(n,k)\) for \(k \geq 1\) and provide requested combinatorial proofs of some prior results from [6].
We will denote the capacity distribution on \(\mathcal{B}_n\) by \(b_n=b_n(y)\), i.e., \[b_n=\sum\limits_{\pi \in \mathcal{B}_n}y^{\text{cap}(\pi)}=\sum\limits_{k=0}^nw(n,k)y^k, \qquad n \geq1,\] with \(b_0=1\). For example, if \(n=6\), then \[\mathcal{B}_6=\{1^6,1^42,1^321,1^221^2,1^22^2,121^3,1212,1221,21^4,21^22,2121,2^21^2,2^3\},\] and \(b_6=10+2y+y^2\).
The organization of this paper is as follows. In the second section, we consider various aspects of the distribution \(b_n\). In Subsection 2.1, we provide combinatorial proofs of some prior formulas from [6] related to a class of restricted compositions whose cardinality coincides with the diagonal sum \(\sum\limits_{k=0}^nw(n-k,k)\). We then determine explicit formulas for \(w(n,k)\) where \(k \geq 1\), as well as for \(\frac{d}{dy}b_n(y)\mid_{y=1}\) and \(b_n(-1)\), by use of generating functions. In Subsection 2.3, we provide counting arguments for these formulas, where in the case of \(b_n(-1)\), a certain sign-changing involution is defined on \(\mathcal{B}_n\) in isolating a subset accounting for the explicit formula.
In the third section, we consider further results concerning the capacity distribution on \(\mathcal{B}_n\). We first establish both a third and a fourth order recurrence for \(b_n\) by combinatorial arguments, where a creative use of the inclusion-exclusion principle is required for the latter. We then briefly study the joint distribution of capacity with two other parameters on \(\mathcal{B}_n\). One of these parameters records the number of \(1\)’s within a member of \(\mathcal{B}_n\), whereas the other tracks the sum of the numbers covered by the left halves of dominoes when a member of \(\mathcal{B}_n\) is represented as a square-and-domino tiling of length \(n\). An explicit formula is deduced for the generating function of this joint distribution on \(\mathcal{B}_n\) and some special cases of the distribution are studied in greater detail.
Let \(\mathcal{D}_n\) denote the set of compositions \((a_1,\ldots,a_r)\) of a positive integer \(n\) for which either \(r=1,2\) or \(r\geq 3\), with the parts \(a_2,\ldots,a_{r-1}\) each even. That is, any internal part, if it exists, within a member of \(\mathcal{D}_n\) is even. Let \(d(n)=|\mathcal{D}_n|\) for \(n \geq 1\), with \(d(0)=1\). In [6], it was shown \(d(n)=\sum\limits_{k=0}^nw(n-k,k)\) for \(n \geq0\) and that \(d(n)\) corresponds to the sequence A052955 in [9]. These combinatorial interpretations for A052955 in terms of restricted compositions and diagonal water cell sums are apparently new.
In [6], it was requested to find direct combinatorial proofs of the following recurrences for \(d(n)\): \[\label{d(n)0rec1} d(n)=d(n-1)+2d(n-2)-2d(n-3), \qquad n \geq 4, \tag{1}\] and \[\label{d(n)0rec2} d(n)=2d(n-2)+1, \qquad n \geq 3. \tag{2}\]
We provide such proofs for (1) and (2) using the interpretation given above for \(d(n)\) in terms of compositions.
Combinatorial proofs of recurrences (1) and (2). We first show (1) and let \(n \geq 4\). Upon adding 1 to the final part of an arbitrary member of \(\mathcal{D}_{n-1}\), we have that there are \(d(n-1)\) members of \(\mathcal{D}_n\) whose final part is greater than 1. Thus, by subtraction and since \(n\geq 4\), there are \(d(n-2)-d(n-3)\) members of \(\mathcal{D}_{n-2}\) whose final part equals \(1\), the subset of \(\mathcal{D}_{n-2}\) of which we denote by \(S\). Using \(S\), one can obtain the remaining unaccounted for members of \(\mathcal{D}_n\), i.e., those whose last part equals 1, as follows. Let \(\rho \in S\). Then either insert a part 2 directly prior to the terminal 1 of \(\rho\), or add 2 to the penultimate part of \(\rho\). Thus, each member of \(S\) is seen to give rise to exactly two members of \(\mathcal{D}_n\) whose final part is 1. Further, \(n \geq 4\) implies a member of \(\mathcal{D}_n\) ending in 1 cannot end in \(1,1\), and hence all such members of \(\mathcal{D}_n\) are generated in a unique manner from those in \(S\) as described. Thus, there are \(2(d(n-2)-d(n-3))\) members of \(\mathcal{D}_n\) whose final part is 1, and combining with the prior case completes the proof of (1).
For (2), given \(\pi\in \mathcal{D}_{n-2}\), where \(n \geq 3\), let \(z\) denote the final part of \(\pi\). If \(z\) is even, then either replace \(z\) with \(z+2\) or append a 2 to the end of \(\pi\). If \(z\) is odd, then replace \(z\) with either \(z+2\) or \(z+1,1\). Note that these operations give rise to almost all of the members of \(\mathcal{D}_n\). If \(n\) is odd, then the two-part composition \((n-2,2)\) is missed by the operations described above, whereas if \(n\) is even, then \((n-1,1)\) is missed. Further, one may verify that no other members of \(\mathcal{D}_n\) are missed and that all other members of \(\mathcal{D}_n\) arise uniquely by applying one of the operations described above to some \(\pi \in \mathcal{D}_{n-2}\). Since exactly two operations are applied to each member of \(\mathcal{D}_{n-2}\), recurrence (2) follows. ◻
It was also shown in [6] using Riordan arrays that \[\label{d(n)gf} \sum\limits_{n\geq0}d(n)x^n=\frac{1-x^2+x^3}{1-x-2x^2+2x^3}, \tag{3}\] and a direct combinatorial explanation of (3) was requested. We complete this section by providing such an explanation.
Combinatorial proof of formula (3). Let \(\mathcal{D}_n^{(e)}\) and \(\mathcal{D}_n^{(o)}\) denote the subsets of \(\mathcal{D}_n\) whose members each contain at least two parts and end in an even or an odd part, respectively. We first determine the generating function for the sequence \(\{|D_n^{(e)}|\}_{n\geq 3}\). To do so, note that if \(n\) is even with \(n=2m\) for some \(m\geq 2\), then \(\pi \in \mathcal{D}_{n}^{(e)}\) implies \(\pi\) can be expressed as \(\pi=p\pi'\), where \(p\) is even with \(p=2r\) for some \(1\leq r\leq m-1\), and \(\pi'\) is such that \(\frac{1}{2}\pi'\) is any composition of the positive integer \(m-r\). Thus, there are \(2^{m-r-1}\) possibilities for \(\pi'\) given \(p\). Similarly, if \(n\) is odd with \(n=2m-1\) for some \(m \geq 2\), then \(\pi \in \mathcal{D}_n^{(e)}\) implies \(\pi=p\pi'\), where now \(p=2r-1\) for some \(1 \leq r \leq m-1\) and \(\frac{1}{2}\pi'\) is a composition of \(m-r\). Combining the even and odd cases for \(n\), we have \[\sum\limits_{n\geq 3}|\mathcal{D}_n^{(e)}|x^n=\frac{x}{1-x}\cdot \frac{x^2}{1-2x^2}=\frac{x^3}{(1-x)(1-2x^2)},\] where \(\frac{x}{1-x}\) accounts for the part \(p\) in the decompositions described above and \(\frac{x}{1-2x}\) accounts for the composition \(\frac{1}{2}\pi'\) of \(m-\lceil p/2\rceil\) for some \(m>\lceil p/2\rceil\) (which is then doubled to yield \(\pi'\)). Note that the nonempty composition \(\frac{1}{2}\pi'\) can be chosen independently of the part \(p\), which justifies the multiplication of the two constituent factors in the generating function.
A similar approach may be applied in finding \(\sum\limits_{n\geq 2}|\mathcal{D}_n^{(o)}|x^n\). In this case, one may first form \(\pi \in \mathcal{D}_{n+1}^{(e)}\) for some \(n \geq 2\) and then subtract 1 from the final part of \(\pi\) to obtain a member of \(\mathcal{D}_n^{(o)}\), with all members of \(\mathcal{D}_n^{(o)}\) seen to arise in this way. This has the effect of dividing the generating function for the sequence \(|\mathcal{D}_n^{(e)}|\) by \(x\), and hence \[\sum\limits_{n\geq 2}|\mathcal{D}_n^{(o)}|x^n=\frac{x^2}{(1-x)(1-2x^2)}.\] Finally, adding the contribution of \(\frac{1}{1-x}\) coming from one-part (as well as the empty) compositions, we then get \[\sum\limits_{n\geq0}d(n)x^n=\frac{1}{1-x}+\frac{x^2(1+x)}{(1-x)(1-2x^2)}=\frac{1-x^2+x^3}{1-x-2x^2+2x^3},\] as desired. ◻
In this subsection, we find explicit formulas for \(w(n,k)\) for \(k\geq1\), the total capacity taken over all members of \(\mathcal{B}_n\) and the sign balance of the capacity statistic on \(\mathcal{B}_n\). To do so, first recall from [6] the generating function formulas \[\label{unif1} \sum\limits_{n\geq k}w(n,k)x^n=\frac{x^{k+4}}{(1-x)^2(1-x^2)^{k+1}}, \qquad k \geq 1, \tag{4}\] and \[\label{unif2} \sum\limits_{n\geq0}w(n,0)x^n=\frac{1-x+x^3}{(1-x)^2(1-x^2)}. \tag{5}\]
Define the bivariate generating function \[\sum\limits_{n\geq0}\sum\limits_{k=0}^nw(n,k)x^ny^k.\] By (4) and (5), we have \[\begin{aligned} F(x,y)&=\sum\limits_{n\geq0}w(n,0)x^n+\sum\limits_{k\geq1}y^k\sum\limits_{n\geq k+4}w(n,k)x^n\notag\\ &=\frac{1-x+x^3}{(1-x)^2(1-x^2)}+\sum\limits_{k\geq1}\frac{x^{k+4}y^k}{(1-x)^2(1-x^2)^{k+1}}\notag\\ &=\frac{1-x+x^3}{(1-x)^2(1-x^2)}+\frac{x^5y}{(1-x)^2(1-x^2)(1-xy-x^2)}\notag\\ &=\frac{1-x(1+y)-x^2(1-y)+2x^3-x^4y-x^5(1-y)}{(1-x)^2(1-x^2)(1-xy-x^2)}\notag\\ &=\frac{1-x(1+y)+x^2y+x^3(1-y)}{(1-x)^2(1-xy-x^2)}.\label{Fxy} \end{aligned} \tag{6}\] Taking \(y=1\) in (6) gives \(F(x,1)=\frac{1}{1-x-x^2}=\sum\limits_{n\geq0}f_nx^n\), as required. Note that (6) also follows as a special case of a more general result [7, Theorem 2] concerning compositions whose parts lie in \([p]=\{1,\ldots,p\}\) for any \(p\geq1\).
We now determine an explicit formula for \(w(n,k)\) for all \(k \geq1\), a formula for \(w(n,0)\) having already been given in [6].
Theorem 2.1. If \(n \geq 5\) and \(1 \leq k \leq n-4\), then \[\label{wnkform} w(n,k)=\sum\limits_{r=1}^{\lfloor\frac{n-k-2}{2}\rfloor}(n-k-2r-1)\binom{k+r-1}{k}. \tag{7}\]
Proof. From the derivation above of the expression for \(F(x,y)\), we have \[\sum\limits_{n\geq5}\sum\limits_{k=1}^{n-4}w(n,k)x^ny^k=\frac{x^5y}{(1-x)^2(1-x^2)(1-xy-x^2)}.\] To expand the preceding generating function, first note \[\begin{aligned} \frac{x^5y}{(1-x^2)(1-xy-x^2)}&=\frac{x^4}{1-xy-x^2}-\frac{x^4}{1-x^2}\\&=\sum\limits_{r \geq 2}x^{2r}\left(\frac{1}{(1-xy)^{r-1}}-1\right)\\ &=\sum\limits_{r\geq1}x^{2r+2}\sum\limits_{k\geq1}\binom{k+r-1}{r-1}(xy)^k\\&=\sum\limits_{k\geq1}y^k\sum\limits_{r\geq1}\binom{k+r-1}{k}x^{k+2r+2}. \end{aligned}\] Hence, we have \[\begin{aligned} \frac{x^5y}{(1-x)^2(1-x^2)(1-xy-x^2)}&=\sum\limits_{k\geq1}y^k\sum\limits_{r\geq1}\binom{k+r-1}{k}x^{k+2r+2}\sum\limits_{n\geq1}nx^{n-1}\\ &=\sum\limits_{k\geq1}y^k\sum\limits_{r\geq1}\binom{k+r-1}{k}\sum\limits_{n\geq k+2r+2}(n-k-2r-1)x^n\\ &=\sum\limits_{n\geq5}\sum\limits_{k=1}^{n-4}x^ny^k\sum\limits_{r=1}^{\lfloor\frac{n-k-2}{2}\rfloor}(n-k-2r-1)\binom{k+r-1}{k}, \end{aligned}\] which implies (7). ◻
Theorem 2.2. If \(n\geq0\), then the sum of the capacity values of all the members of \(\mathcal{B}_n\) is given by \[\label{totcap} \sum\limits_{k=1}^nkw(n,k)=\frac{(n+1)L_{n+1}-f_n}{5}-2f_{n+1}+n+2, \tag{8}\] where \(L_m=f_{m}+f_{m-2}\) for \(m\geq 1\) denotes the \(m\)-th Lucas number.
Proof. By (6), we have \[\frac{\partial}{\partial y}F(x,y)\mid_{y=1}=\frac{x}{(1-x-x^2)^2}-\frac{x(1-x+x^2)}{(1-x)^2(1-x-x^2)}=\frac{x^5}{(1-x)^2(1-x-x^2)^2}.\] Let \([x^n]\) applied to an expression denote extraction of the coefficient of \(x^n\) in its Taylor series expansion. Note \[[x^n]\left(\frac{1}{(1-x)(1-x-x^2)}\right)=\sum\limits_{i=0}^nf_i=f_{n+2}-1, \qquad n \geq0,\] where in the second equality, we have used [1, Identity 1]. Thus, we have \[[x^n]\left(\frac{1}{(1-x)^2(1-x-x^2)^2}\right)=\sum\limits_{j=0}^n(f_{j+2}-1)(f_{n-j+2}-1),\] upon considering the convolution of the generating function \(\frac{1}{(1-x)(1-x-x^2)}\) with itself. Note that the lower and upper indices of summation in the preceding sum may be replaced by \(j=-2\) and \(j=n+2\), respectively. Replacing \(j\) by \(j-2\) in the sum then gives \[\begin{aligned} \left(\frac{1}{(1-x)^2(1-x-x^2)^2}\right)&=\sum\limits_{j=0}^{n+4}(f_{j}-1)(f_{n-j+4}-1)\notag\\ &=\sum\limits_{j=0}^{n+4}f_jf_{n-j+4}-2\sum\limits_{j=0}^{n+4}f_j+\sum\limits_{j=0}^{n+4}1\notag\\ &=\frac{(n+6)L_{n+6}-f_{n+5}}{5}-2(f_{n+6}-1)+n+5, \qquad n \geq 0, \label{n+5tot} \end{aligned} \tag{9}\] where we have used Identities 1 and 58 from [1] to obtain (9) from the equality preceding it. If \(n \geq 5\), then we have \[[x^n]\frac{\partial}{\partial y}F(x,y)\mid_{y=1}=[x^{n-5}]\left(\frac{1}{(1-x)^2(1-x-x^2)^2}\right)=\frac{(n+1)L_{n+1}-f_n}{5}-2f_{n+1}+n+2,\] by (9), which implies (8) for \(n\geq 5\). Since both sides of (8) are seen to equal zero for \(0 \leq n \leq 4\), the proof of (8) is complete. ◻
Remark 2.3. Dividing the expression in (8) by \(f_n\) yields the average capacity of all the members of \(\mathcal{B}_n\). Since \(f_n\sim\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}\) for large \(n\), one obtains that this average is asymptotically equal to \(\frac{n}{\sqrt{5}}\). This result may be interpreted probabilistically in terms of tilings as follows. Let \(\mathcal{L}_n\) denote the set of linear square-and-domino tilings of length \(n\); see, e.g., [1, Chapter 1]. Then the preceding implies that if a member \(\lambda \in \mathcal{L}_n\) and an element \(x \in [n]\) are chosen at random where \(n\) is large, then the probability that \(x\) is covered by a square in \(\lambda\) such that at least one domino occurs somewhere both to the left and to the right of \(x\) is approximately \(\frac{1}{\sqrt{5}}\approx0.447\).
Let \(\mathcal{B}_n^{(e)}\) and \(\mathcal{B}_n^{(o)}\) denote the subsets of \(\mathcal{B}_n\) consisting of those members whose capacity is even or odd, respectively. We have the following sign balance result for the capacity statistic on \(\mathcal{B}_n\).
Theorem 2.4. If \(n \geq0\), then \[\label{capbalancee1} |\mathcal{B}_n^{(e)}|-|\mathcal{B}_n^{(o)}|=\sum\limits_{k=0}^n(-1)^kw(n,k)=2n-4+(-1)^nf_{n-6}, \tag{10}\] where \(f_{-m}\) for \(m\geq2\) is defined as \((-1)^mf_{m-2}\), with \(f_{-1}=0\).
Proof. The formula is readily verified for \(0 \leq n \leq 2\). Taking \(y=-1\) in (6) gives \(F(x,-1)=\frac{1-x^2+2x^3}{(1-x)^2(1+x-x^2)}\). Note \[\frac{1}{(1-x)^2(1+x-x^2)}=\frac{1}{(1-x)^2}-\frac{x}{1-x}+\frac{x^2}{1+x-x^2},\] and hence \[[x^n]\left(\frac{1}{(1-x)^2(1+x-x^2)}\right)=n+(-1)^nf_{n-2}, \qquad n \geq0.\] This implies for \(n \geq 3\), \[\begin{aligned} F(x,-1)&=n+(-1)^nf_{n-2}-(n-2+(-1)^{n-2}f_{n-4})+2(n-3+(-1)^{n-3}f_{n-5})\\ &=2n-4+(-1)^n(f_{n-2}-f_{n-4}-2f_{n-5})\\ &=2n-4+(-1)^nf_{n-6}, \end{aligned}\] as desired. ◻
As a consequence of the preceding results, one obtains the following binomial coefficient identities.
Corollary 2.5. If \(n\geq 5\), then \[\ \sum\limits_{r=1}^m\sum\limits_{k=2r+2}^{n-1}(n-k)\binom{k-r-2}{r-1} =f_n-1-\lfloor n^2/4 \rfloor, \label{binomcore1}\ \tag{11}\] \[\sum\limits_{r=1}^m\sum\limits_{k=2r+2}^{n-1}(n-k)(k-r-2)\binom{k-r-3}{r-1}=\frac{(n+1)L_{n+1}-f_n}{5}-2f_{n+1}+n+2, \label{binomcore2}\ \tag{12}\] \[\sum\limits_{r=1}^m\sum\limits_{k=2r+2}^{n-1}(-1)^{k-1}(n-k)\binom{k-r-2}{r-1} =2n-5-\lfloor n^2/4 \rfloor+(-1)^nf_{n-6},\label{binomcore3} \tag{13}\] where \(m=\lfloor(n-3)/2\rfloor\).
Proof. First note \(\sum\limits_{k=0}^nw(n,k)=f_n\) and \(\sum\limits_{k=0}^n(-1)^kw(n,k)=|\mathcal{B}_n^{(e)}|-|\mathcal{B}_n^{(o)}|\) for \(n \geq0\), with \(\sum\limits_{k=1}^nkw(n,k)\) being the sum of the capacity values of all the members of \(\mathcal{B}_n\). By (7), (8) and (10), we then obtain the following identities for \(n \geq 5\): \[\begin{aligned} \sum\limits_{k=1}^{n-4}\sum\limits_{r=1}^{p}(n-k-2r-1)\binom{k+r-1}{k}&=f_n-w(n,0),\\ \sum\limits_{k=1}^{n-4}\sum\limits_{r=1}^{p}k(n-k-2r-1)\binom{k+r-1}{k}&=\frac{(n+1)L_{n+1}-f_n}{5}-2f_{n+1}+n+2,\\ \sum\limits_{k=1}^{n-4}\sum\limits_{r=1}^{p}(-1)^k(n-k-2r-1)\binom{k+r-1}{k}&=2n-4+(-1)^nf_{n-6}-w(n,0), \end{aligned}\] where \(p=\lfloor (n-k-2)/2 \rfloor\) and \(w(n,0)=1+\lfloor n^2/4 \rfloor\). Interchanging summation, replacing the index \(k\) with \(k-2r-1\) and noting \((k-2r-1)\binom{k-r-2}{r-1}=(k-r-2)\binom{k-r-3}{r-1}\) in the second resulting identity yields (11)–(13). ◻
We now provide combinatorial explanations of Theorems 2.1, 2.2 and 2.4, which were shown using the generating function formula (6).
Proof of Theorem 2.1. Note that \(\pi \in \mathcal{B}_{n,k}\) for some \(n \geq 5\) and \(k \in [n-4]\) implies \(\pi\) can be decomposed as \[\label{bnkform} \pi=1^x2^{a_0}1\cdots 2^{a_{k-1}}12^{a_k}1^y, \tag{14}\] where \(a_0,a_{k}\geq 1\) and \(x,y,a_1,\ldots,a_{k-1} \geq0\) such that \(x+y+2\sum\limits_{i=0}^ka_i=n-k\). We first enumerate members of \(\mathcal{B}_{n,k}\) of the form (14), where \(\sum\limits_{i=0}^ka_i=r+1\) for some \(r \geq 1\). Note that \(x,y\geq0\) implies \(2(r+1)\leq n-k\), i.e., \(r \leq \lfloor(n-k-2)/2\rfloor\). Then \(a_0,a_{k+1}\geq1\) implies there are \(\binom{k+r-1}{k}\) possibilities for \((a_0,\ldots,a_{k})\) for each \(r\), by [10, p. 15]. Then \(x+y=n-k-2r-2\) with \(x,y \geq0\) yields \(n-k-2r-1\) possibilities for \(x\) and \(y\) independent of the choice of the \(a_i\). Thus, there are \((n-k-2r-1)\binom{k+r-1}{k}\) members of \(\mathcal{B}_{n,k}\) such that \(\sum\limits_{i=0}^ka_i=r+1\) for each \(r\) and summing over all possible \(r\) yields (7). ◻
Proof of Theorem 2.2. Formula (8) is easily seen to hold for \(0 \leq n \leq 2\), so we may assume \(n \geq 3\). Let \(\mathcal{B}_n'\) denote the set of marked members of \(\mathcal{B}_n\) wherein a single part 1 corresponding to a water cell, if it exists, is marked. Equivalently, we determine the cardinality of \(\mathcal{B}_n'\). Let \(\mathcal{B}_n^*\) denote the set of marked members of \(\mathcal{B}_n\) wherein any part \(1\) may be marked. Note that there are \(f_if_{n-i-1}\) members \(\pi \in \mathcal{B}_n^*\) of the form \(\pi=\pi'\underline{1}\pi''\) such that \(\pi' \in \mathcal{B}_i\), \(\pi'' \in \mathcal{B}_{n-i-1}\) and the marked \(1\) is underlined. Summing over all \(0 \leq i \leq n-1\) implies \[|\mathcal{B}_n^*|=\sum\limits_{i=0}^{n-1}f_if_{n-i-1}=\frac{(n+1)L_{n+1}-f_n}{5},\] where in the second equality, we have used [1, Identity 58], which was provided a combinatorial proof by the authors in terms of linear and circular tilings.
To complete our enumeration of \(\mathcal{B}_n'\), we subtract from \(\mathcal{B}_n^*\) the cardinality of those members in which the marked \(1\) occurs as part of an initial or terminal run of \(1\)’s, and hence does not correspond to a water cell. Note that there are \(f_{n-\ell}-1\) members of \(\mathcal{B}_n^*\) of the form \(1^{\ell-1}\underline{1}\rho'\) for some \(1 \leq \ell \leq n-2\), where the marked \(1\) is underlined and \(\rho'\) contains at least one \(2\). Considering all \(\ell\) gives \(\sum\limits_{\ell=1}^{n-2}(f_{n-\ell}-1)=f_{n+1}-n-1\) members of \(\mathcal{B}_n^*\) (not all \(1\)’s) in which the marked \(1\) occurs as part of an initial run of \(1\)’s, where we have made use of [1, Identity 1], which may be readily explained bijectively. By symmetry, there are the same number of members of \(\mathcal{B}_n^*\) in which the marked \(1\) occurs as part of a terminal run (preceded by a \(2\)). Finally, there are \(n\) members of \(\mathcal{B}_n^*\) corresponding to the all \(1\)’s composition. Combining the prior cases, we have \[|\mathcal{B}_n^*\setminus\mathcal{B}_n'|=2(f_{n+1}-n-1)+n=2f_{n+1}-n-2.\] Subtracting this expression from the one found above for \(|\mathcal{B}_n^*|\) gives the desired formula for \(|\mathcal{B}_n'|\) and completes the proof. ◻
Proof of Theorem 2.4. Let \(\mathcal{K}_n\) denote the subset of \(\mathcal{B}_n\) whose members contain at least two parts \(2\) such that at least one part occurs between the first and last \(2\)’s. Note that \(\mathcal{K}_n=\varnothing\) if \(0 \leq n \leq 4\) and formula (10) is readily verified in these cases. So assume \(n \geq 5\) and we seek an involution on \(\mathcal{K}_n\). Note that \(\pi \in \mathcal{K}_n\) for \(n \geq 5\) implies it may be decomposed as \[\label{K-ndec} \pi=1^x2\alpha21^y, \quad x,y \geq0. \tag{15}\] Then \(\alpha \in \mathcal{B}_{n-x-y-4}\) nonempty implies \(x+y \leq n-5\). Define the sign of \(\pi\) by \(\text{sgn}(\pi)=(-1)^{\text{cap}(\pi)}\). Note that \(\text{cap}(\pi)=n-x-y-2\mu(\pi)\), where \(\mu(\pi)\) denotes the number of \(2\)’s of \(\pi\), and hence \(\text{sgn}(\pi)=(-1)^{n-x-y}\).
We define a preliminary involution on \(\mathcal{K}_n\) as follows. If \(x \geq 1\) and \(\alpha=\alpha'1\) in (15), then replace \(\pi\) with the composition \(1^{x-1}2(\alpha'2)21^y\), whereas if \(x \geq 0\) and \(x=\alpha'2\), then replace \(\pi\) with \(1^{x+1}2(\alpha'1)21^y\). This pair of operations defines a sign-changing involution on \(\mathcal{K}_n\) whose set of survivors, which we’ll denote by \(\mathcal{K}_n'\), consists of those \(\pi\) expressible as \(\pi=2(\alpha'1)21^y\), where \(\alpha'\) is possibly empty. If \(n=5\), then \(\mathcal{K}_n'\) contains a single member whose sign is negative, and (10) is seen to hold when \(n=5\) since \(|\mathcal{B}_5\setminus\mathcal{K}_5|=7\).
So assume \(n \geq 6\) and considering the final part of the section \(\alpha'\) within a member of \(\mathcal{K}_n'\) leads to the pairings \[2(\alpha''21)21^y\leftrightarrow 2(\alpha''1^2)21^{y+1}, \qquad y \geq0.\] Thus, each member of \(\mathcal{K}_n'\) is paired with another of opposite sign except for \(\rho=2121^{n-5}\) or \(\pi\) of the form \(\pi=2(\alpha''1^2)2\), where \(\alpha'' \in \mathcal{B}_{n-6}\). Note that \(\rho\) has negative sign, whereas each \(\pi\) of the stated form has sign \((-1)^n\). Thus, the sum of the signs of all members of \(\mathcal{K}_n'\), and hence also of \(\mathcal{K}_n\), is given by \(-1+(-1)^nf_{n-6}\).
To this, we add the contribution of members of \(\mathcal{B}_n\setminus\mathcal{K}_n\), which consists of compositions of \(1\)’s and \(2\)’s containing at most one \(2\) or exactly two \(2\)’s with no part between them. Since \(\mathcal{B}_n\setminus\mathcal{K}_n\) is a subset of \(\mathcal{B}_{n,0}\), each of its members has positive sign, with \(|\mathcal{B}_n\setminus\mathcal{K}_n|=2n-3\), as there are \(n\) members of \(\mathcal{B}_n\) containing at most one \(2\) and \(n-3\) of the form \(1^x2^21^y\) for some \(x,y\geq0\). Adding \(2n-3\) to the contribution towards the sign balance found above for \(\mathcal{K}_n\) yields \(2n-4+(-1)^nf_{n-6}\) for all \(n \geq 6\), as desired. ◻
In this section, we consider a pair of recurrences satisfied by the capacity distribution on \(\mathcal{B}_n\) as well as a \(q\)-generalization involving two additional parameters.
Recall \(b_n=b_n(y)\) for \(n \geq1\) is given by \(b_n=\sum\limits_{\pi \in \mathcal{B}_n}y^{\text{cap}(\pi)}\), with \(b_0=1\). There are the following recurrence formulas for \(b_n\).
Theorem 3.1. We have \[\label{bnrece1} b_n=(1+y)b_{n-1}+(1-y)b_{n-2}-b_{n-3}+1-y,\qquad n \geq 3, \tag{16}\] and \[\label{bnrece2} b_n=(2+y)b_{n-1}-2yb_{n-2}-(2-y)b_{n-3}+b_{n-4},\qquad n \geq 4, \tag{17}\] with \(b_0=b_1=1\), \(b_2=2\) and \(b_3=3\).
Proof. We first show (16), where the initial values for \(0 \leq n \leq 2\) are clear. Let \(n \geq 3\) and note that appending a 1 to an arbitrary member of \(\mathcal{B}_{n-1}\) does not change the capacity, whence the weight of all members of \(\mathcal{B}_n\) ending in 1 is given by \(b_{n-1}\). On the other hand, inserting a 1 directly prior to the final 2 within a member of \(\mathcal{B}_{n-1}\) ending in 2, except for \(1^{n-3}2\), is seen to increase the capacity by one. Thus, by subtraction, the contribution towards \(b_n\) of the members of \(\mathcal{B}_{n}\) ending in \(1,2\) is given by \(y(b_{n-1}-b_{n-2}-1)+1\). Note that the \(+1\) term accounts for the composition \(1^{n-2}2\) of capacity zero, which does not arise by inserting 1 as described. Finally, by subtraction, the weight of all members of \(\mathcal{B}_{n-2}\) ending in 2 is given by \(b_{n-2}-b_{n-3}\) and appending a 2 to such members does not change the capacity. Thus, the contribution towards \(b_n\) of all the members of \(\mathcal{B}_n\) ending in \(2,2\) is given by \(b_{n-2}-b_{n-3}\) and combining with the prior cases implies (16).
Replacing \(n\) with \(n-1\) in \(b_n-(1+y)b_{n-1}-(1-y)b_{n-2}+b_{n-3}=1-y\) for \(n \geq 4\), and equating expressions for \(1-y\), leads to (17). ◻
Note that recurrence (17) follows from the generating function formula (6) above as well. It is also possible to provide a counting argument for (17) as follows.
Combinatorial proof of recurrence (17). Let \(n \geq 4\), and first observe \(\mathcal{B}_n\setminus\{1^{n-2}2\}\) is a (non-disjoint) union of the following three sets: \[\begin{aligned} U=\{&\pi \in \mathcal{B}_n: \pi \text{ ends in } 1\},\\ V=\{&\pi \in \mathcal{B}_n: \pi \text{ contains at least two 2's and at least one 1 occurs between the rightmost}\\ &\text{two 2's}\},\\ W=\{&\pi \in \mathcal{B}_n: \pi \text{ contains at least two 2's, with the rightmost two 2's adjacent}\}. \end{aligned}\] Let \(|S|\) denote here \(\sum\limits_{\pi \in S}y^{\text{cap}(\pi)}\) for a subset \(S\) of \(\mathcal{B}_n\); i.e., \(|S|\) gives the cardinality of the set of colored members of \(S\) wherein each water cell receives one of \(y\) colors in the case when \(y\) is a fixed positive integer. Applying the principle of inclusion-exclusion, and noting \(V\cap W =\varnothing\), we have \[\label{incexcl} b_n-1=|U|+|V|+|W|-|U\cap V|-|U\cap W|. \tag{18}\]
To complete the proof of (17), we seek expressions for the quantities on the right-hand side of (18) in terms of \(b_n\). Clearly, we have \(|U|=b_{n-1}\). Also, members of \(V\) may be formed in a unique manner from members of \(\mathcal{B}_{n-1}\) containing at least two \(2\)’s by inserting a single 1 directly prior to the rightmost 2. This is seen to increase the capacity by one and hence \(|V|=y(b_{n-1}-n+1)\), upon excluding the \(n-1\) members of \(\mathcal{B}_{n-1}\) that contain at most one \(2\). To determine \(|W|\), we consider the auxiliary set \(X\) given by \(X=\{\pi \in \mathcal{B}_n: \pi \text{ ends in 2,\,1}\}\). To form members of \(W\) or \(X\), we start with a composition \(\pi \in \mathcal{B}_{n-1}\setminus\{1^{n-1}\}\) and consider the final part of \(\pi\). If \(\pi\) ends in 1, then we change the 1 directly following the rightmost 2 in \(\pi\) to a 2, which is seen to yield all members of \(W\). If \(\pi\) ends in a 2, then we append 1 to \(\pi\), which yields the members of \(X\). Since the capacity is unchanged by the operation in either case, we have \(b_{n-1}-1=|W|+|X|\).
To determine \(|X|\), we consider the antepenultimate part of \(\pi \in X\). If \(\pi=\pi'2^21\), then \(\pi\) may be obtained by appending \(2,1\) to a member of \(\mathcal{B}_{n-3}\) ending in 2, of which there are \(b_{n-3}-b_{n-4}\) possibilities, by subtraction. If \(\pi=\pi'121\) and \(\pi \neq 1^{n-3}21\), then \(\pi\) may be obtained from \(\rho \in \mathcal{B}_{n-2}\) ending in 2, and not equal \(1^{n-4}2\), by inserting a 1 both directly before and after the terminal 2 of \(\rho\). Since \(\rho \neq 1^{n-4}2\), this operation always increases the capacity by one and hence there are \(y(b_{n-2}-b_{n-3}-1)\) possibilities for such \(\pi\), upon excluding the members of \(\mathcal{B}_{n-2}\) ending in 1 as well as the single composition \(1^{n-4}2\) from consideration for \(\rho\). Adding to this the contribution of \(1^{n-3}21\), which has capacity zero, implies members of \(X\) with antepenultimate part 1 have weight \(y(b_{n-2}-b_{n-3})+1-y\). Combining with the previous case implies \(|X|=yb_{n-2}+(1-y)b_{n-3}-b_{n-4}+1-y\), and hence \[|W|=b_{n-1}-1-|X|=b_{n-1}-yb_{n-2}-(1-y)b_{n-3}+b_{n-4}-2+y.\]
To find \(|U\cap V|\), first note that \(\pi \in U \cap V\) implies \(\pi\) is expressible as \(\pi=\pi'21^x21^y\) for some \(x,y\geq 1\). Thus, members of \(U \cap V\) may be obtained in a unique manner from compositions in \(\mathcal{B}_{n-2}\) containing at least two \(2\)’s by inserting a 1 both directly before and after the rightmost 2. This implies \(|U\cap V|=y(b_{n-2}-n+2)\), upon excluding the \(n-2\) members of \(\mathcal{B}_{n-2}\) containing at most one \(2\). Next, observe \(\pi \in U \cap W\) implies it is of the form \(\pi=\pi'2^21^x\) for some \(x\geq 1\). Hence, \(\pi\) may be formed from \(\rho \in \mathcal{B}_{n-3}\setminus\{1^{n-3}\}\) by inserting \(2,1\) directly after the rightmost 2 of \(\rho\), which leaves the capacity unchanged. Therefore, we have \(|U \cap W|=b_{n-3}-1\). Recurrence (17) now follows from (18), upon substituting the expressions found above for the weights of the sets on the right-hand side. ◻
In this subsection, we consider a polynomial generalization of \(b_n\) in terms of a pair of statistics on \(\mathcal{B}_n\) as follows. Let \(\tau(\pi)\) denote the number of \(1\)’s in \(\pi \in \mathcal{B}_n\). For our second statistic, let \(1 \leq i_1<\cdots<i_r \leq m\) denote the set of indices \(j \in [m]\) such that \(\pi_j=2\) within \(\pi=\pi_1\cdots \pi_m \in \mathcal{B}_n\), where \(\pi\) contains \(m\) parts for some \(m \in [n]\). Define \[\sigma (\pi)=r+\sum\limits_{j=1}^r\sum\limits_{k=1}^{i_j-1}\pi_k.\]
Remark 3.2. We have that \(\sigma(\pi)\) then gives the total of the number of parts of size 2 in \(\pi\) and the sum of all the partial sums of \(\pi\) consisting of the parts lying strictly to the left of some part of size 2. Note that a composition in \(\mathcal{B}_n\) may be regarded as a member of \(\mathcal{L}_n\) by putting a square for each part 1 and a domino for each 2 and then writing the numbers \(1,2,\ldots,n\) from left to right in the \(n\) positions covered by the resulting tiling. Thus, the analogous statistic on \(\mathcal{L}_n\) (see [8]) records the sum of the numbers that are covered by the left halves of the dominoes within a tiling. An equivalent statistic was considered earlier by Carlitz [5] recording the value of \(a_1+2a_2+\cdots+(n-1)a_{n-1}\) on the set of \(\{0,1\}\)-words \(a_1a_2\cdots a_{n-1}\) in which no two consecutive \(1\)’s occur. Finally, the capacity statistic on \(\mathcal{B}_n\) is seen to be equivalent to the statistic on \(\mathcal{L}_n\) recording the total number of squares occurring between the first and last dominoes.
Define \({\bf b}_n={\bf b}_n(y;p,q)\) by \[{\bf b}_n=\sum\limits_{\pi \in \mathcal{B}_n}p^{\tau(\pi)}q^{\sigma(\pi)}y^{\text{cap}(\pi)}, \qquad n \geq 1,\] with \({\bf b}_0=1\). Note that \({\bf b}_n(y;1,1)=b_n(y)\) for all \(n\). For example, if \(n=6\), then \[{\bf b}_6(y;p,q)=q^9+p^2q^4(1+q^2+q^4)+p^2q^5y(1+q^2+qy)+p^4q(1+q+q^2+q^3+q^4)+p^6,\] which reduces to \(b_6(y)=10+2y+y^2\) when \(p=q=1\).
Define the generating function \(F(x)=F(x,y;p,q)\) by \[F(x)=\sum\limits_{n\geq0}{\bf b}_nx^n.\]
Theorem 3.8. We have \[\label{F(x,y;p,q)e1} F(x,y;p,q)=\frac{1}{1-px}+\sum\limits_{n\geq1}\frac{q^{n^2}x^{2n}}{(1-px)(1-pq^nx)\prod_{j=1}^{n-1}(1-pq^jxy)}. \tag{19}\]
Proof. Let \({\bf b}_n^{(i)}\) for \(i=1,2\) denote the restriction of \({\bf b}_n\) to members of \(\mathcal{B}_n\) whose last part is \(i\). Then we have \[\ {\bf b}_n^{(1)} =p{\bf b}_{n-1}, \qquad\qquad\qquad\qquad\qquad\quad\qquad n \geq 1,\label{bn(1)}\ \tag{20}\] \[{\bf b}_n^{(2)} =p^{n-2}q^{n-1}+\sum\limits_{j=2}^{n-2}(py)^{j-2}q^{n-1}{\bf b}_{n-j}^{(2)}, \qquad n \geq 2,\label{bn(2)} \tag{21}\] with \({\bf b}_0=1\), \({\bf b}_1^{(2)}=0\) and \({\bf b}_n={\bf b}_n^{(1)}+{\bf b}_n^{(2)}\) for \(n \geq 1\). Let \(F^{(i)}(x)=\sum\limits_{n\geq1}{\bf b}_n^{(i)}x^n\) for \(i=1,2\). Then (20) implies \(F^{(1)}(x)=pxF(x)\) and \(F(x)=1+F^{(1)}(x)+F^{(2)}(x)\), by the definitions. Hence, we have \[\label{F(x,y;p,q)e2} F(x)=\frac{1+F^{(2)}(x)}{1-px}. \tag{22}\]
To determine \(F^{(2)}(x)\), first note \[\begin{aligned} \sum\limits_{n\geq4}x^n\sum\limits_{j=2}^{n-2}(py)^{j-2}q^{n-1}{\bf b}_{n-j}^{(2)}&=\frac{1}{q}\sum\limits_{j\geq2}(py)^{j-2}\sum\limits_{n\geq j+2}{\bf b}_{n-j}^{(2)}(qx)^n\\&=\frac{1}{q}\sum\limits_{j\geq2}(py)^{j-2}\cdot(qx)^jF^{(2)}(qx)\\ &=F^{(2)}(qx)\sum\limits_{j\geq2}p^{j-2}q^{j-1}x^jy^{j-2}\\&=\frac{qx^2}{1-pqxy}F^{(2)}(x). \end{aligned}\] Multiplying both sides of (21) by \(x^n\), and summing over all \(n \geq 2\), then gives \[\begin{aligned} F^{(2)}(x)&=\sum\limits_{n\geq2}p^{n-2}q^{n-1}x^n+\sum\limits_{n\geq4}x^n\sum\limits_{j=2}^{n-2}(py)^{j-2}q^{n-1}{\bf b}_{n-j}^{(2)}\notag\\ &=\frac{qx^2}{1-pqx}+\frac{qx^2}{1-pqxy}F^{(2)}(qx). \label{f(x,y;p,q)funceq} \end{aligned} \tag{23}\] Iterating the functional relation (23) an infinite number of times, where \(x\) is assumed to be sufficiently small in absolute value, yields \[\begin{aligned} F^{(2)}(x)&=\frac{qx^2}{1-pqx}+\frac{qx^2}{1-pqxy}\left(\frac{q^3x^2}{1-pq^2x}+\frac{q^3x^2}{1-pq^2xy}F^{(2)}(q^2x)\right)\\ &=\cdots=\frac{qx^2}{1-pqx}+\sum\limits_{n\geq1}\frac{q^{2n+1}x^2}{1-pq^{n+1}x}\prod_{j=1}^n\left(\frac{q^{2j-1}x^2}{1-pq^jxy}\right)\\ &=\sum\limits_{n\geq0}\frac{q^{(n+1)^2}x^{2n+2}}{(1-pq^{n+1}x)\prod_{j=1}^n(1-pq^jxy)}\\&=\sum\limits_{n\geq1}\frac{q^{n^2}x^{2n}}{(1-pq^{n}x)\prod_{j=1}^{n-1}(1-pq^jxy)}, \end{aligned}\] from which (19) now follows from (22). ◻
Taking \(q=1\) in (19) gives the following formula for \(F(x,y;p,1)\), which reduces to (6) when \(p=1\).
Corollary 3.4. We have \[\label{F(x,y;p,q)core1} F(x,y;p,1)=\frac{1-px(1+y)+p^2x^2y+px^3(1-y)}{(1-px)^2(1-pxy-x^2)}. \tag{24}\]
Let \(\mathcal{B}_{n,k,j}\) denote the subset of \(\mathcal{B}_{n,k}\) whose members contain exactly \(j\) parts \(1\). Using (24), one can find an explicit formula for its cardinality.
Theorem 3.5. Let \(n \geq j\geq k\geq0\) with \(n \equiv j\,(mod~2)\). If \(k \geq 1\) and \(n \geq j+4\), then \[\label{th1exe1} |\mathcal{B}_{n,k,j}|=(j-k+1)\binom{\frac{n-j-4}{2}+k}{k}. \tag{25}\] If \(n \geq j+2\), then \(|\mathcal{B}_{n,0,j}|=j+1\), with \(|\mathcal{B}_{n,0,n}|=1\) for all \(n \geq0\).
Proof. One can give an algebraic proof as follows. By (24), we have \[F(x,y;p,1)=\frac{1}{1-px}+\frac{x^2}{(1-px)^2(1-x^2)}+\frac{px^5y}{(1-px)^2(1-x^2)(1-pxy-x^2)}.\] Now observe \[\begin{aligned} \frac{px^5y}{(1-px)^2(1-x^2)(1-pxy-x^2)}&=\frac{x^4}{(1-px)^2}\sum\limits_{k\geq1}\frac{(pxy)^k}{(1-x^2)^{k+1}}\\ &=x^4\sum\limits_{k\geq1}\frac{(pxy)^k}{(1-x^2)^{k+1}}\sum\limits_{j\geq 1}j(px)^{j-1}\\ &=\sum\limits_{k\geq1}\sum\limits_{j \geq k}(j-k+1)x^{j+4}y^kp^j\cdot \frac{1}{(1-x^2)^{k+1}}\\ &=\sum\limits_{r\geq0}\sum\limits_{k\geq 1}\sum\limits_{j \geq k}(j-k+1)\binom{r+k}{k}x^{2r+j+4}y^kp^j. \end{aligned}\] Letting \(n=2r+j+4\), and extracting the coefficient of \(x^ny^kp^j\) in the last expression, yields (25). The \(\frac{1}{1-px}\) term accounts for the \(n=j\geq0,\,k=0\) case, whereas writing \[\frac{x^2}{(1-px)^2(1-x^2)}=\frac{x^2}{1-x^2}\sum\limits_{j\geq0}(j+1)(px)^j=\sum\limits_{r\geq1}\sum\limits_{j\geq0}(j+1)x^{2r+j}p^j,\] implies \(|\mathcal{B}_{n,0,j}|=j+1\) for \(n \geq j+2\). ◻
Let \(F_n=F_n(p)\) denote the \(n\)-th Fibonacci polynomial defined by \(F_n=pF_{n-1}+F_{n-2}\) for \(n \geq 2\), with \(F_0=1\) and \(F_1=p\). Note that \(F_n(p)\) when \(p\) is a positive integer is seen to enumerate colored members of \(\mathcal{B}_n\) wherein each part of size \(1\) is assigned one of \(p\) colors. Theorem 2.2 can be generalized in terms of colored compositions as follows.
Theorem 3.6. The total capacity of all members of \(\mathcal{B}_n\) for \(n \geq0\) in which each 1 is assigned one of \(p\) colors is given by \[\label{totcapthgene1} [x^n]\frac{\partial }{\partial y}F(x,y;p,1)\mid_{y=1}=\frac{p^2nF_n+2p(n+1)F_{n-1}}{p^2+4}-2pF_{n+1}+p^{n}(n+2p^2). \tag{26}\]
Proof. By (24), we have \[\frac{\partial }{\partial y}F(x,y;p,1)\mid_{y=1}=\frac{px}{(1-px-x^2)^2}-\frac{px(1-px+x^2)}{(1-px)^2(1-px-x^2)}=\frac{px^5}{(1-px)^2(1-px-x^2)^2}.\] Generalizing the argument given above for (9), and using the fact \(\sum\limits_{i=0}^np^{n-i}F_i=F_{n+2}-p^{n+2}\), we have \[\label{x^ncoeff} [x^n]\left(\frac{1}{(1-px)^2(1-px-x^2)^2}\right)=\sum\limits_{i=0}^{n+4}F_iF_{n-i+4}-2F_{n+6}+p^{n+4}(n+5+2p^2), \quad n \geq0. \tag{27}\] Note that the right side of (27) is seen to give the correct value of zero for \(-5 \leq n \leq -1\). Upon comparing the generating functions of both sides, we have \[\label{Fibpolconv} \sum\limits_{i=0}^{n-1}F_iF_{n-i-1}=\frac{pnF_n+2(n+1)F_{n-1}}{p^2+4}, \qquad n \geq0, \tag{28}\] where \(F_{-1}=0\). Formula (26) now follows from computing \(p[x^{n-5}]\left(\frac{1}{(1-px)^2(1-px-x^2)^2}\right)\) for \(n \geq0\) using (27) and (28). ◻
Remark 3.7. Rewriting formula (25) using \(r=\frac{n-j-2}{2}\), where \(1 \leq r \leq \lfloor(n-k-2)/2\rfloor\), and then summing over \(r\) yields (7). Taking \(p=1\) in (26), and noting \(L_{n+1}=F_n+2F_{n-1}\), yields (8). In addition, it is possible to provide combinatorial arguments of (25) and (26) by modifying appropriately those given above for (7) and (8), respectively. Moreover, one can explain combinatorially the Fibonacci polynomial identity (28) used in obtaining Theorem 3.6 by extending the tiling argument given in [1, Identity 58].