Let Fn denote the n-th Fibonacci number defined by Fn = Fn − 1 + Fn − 2 if n ≥ 2, with F0 = 0 and F1 = 1. In this paper, we find determinant identities for several Toeplitz–Hessenberg matrices whose nonzero entries are derived from the sequence kn + m for various fixed m, where kn = Fn − 1. These results may be obtained algebraically as special cases of more general formulas involving the Horadam numbers and the generating functions for the associated sequences of determinants. Equivalent multi-sum identities featuring sums of products of kn terms with multinomial coefficients may be given, which follow from Trudi’s formula. Connections are made to several OEIS entries that have arisen previously in other contexts, perhaps most notably the Padovan number sequence. Finally, we provide combinatorial proofs of our identities involving kn by enumerating (or finding the sum of signs of) various classes of tilings containing squares, dominos, trominos and a special type of tile which can be of arbitrary length.
The Fibonacci numbers \(F_n\) occur throughout enumerative combinatorics and are given by \(F_n=F_{n-1}+F_{n-2}\) if \(n \geq 2\), with \(F_0=0\) and \(F_1=1\); see entry A000045 in the OEIS [13]. Less well studied is the sequence of Fibonacci numbers minus one [13, A000071], which we will denote here by \(k_n=F_n-1\). The numbers \(k_n\) enumerate a variety of discrete structures, among them, the permutations \(p\) of \([n-1]=\{1,\ldots,n-1\}\) for which \(\max|p(i)-i|=1\) and the set of binary words of length \(n-3\) avoiding the string \(001\). A more recent result [2, Prop. 15] is that \(k_{n+2}\) gives the cardinality of the set of Catalan words of length \(n\) which simultaneously avoid the patterns \(001\) and \(100\) in the classical sense. Here, we will be interested in some new combinatorial aspects of the numbers \(k_n\) as it pertains to their occurrence in certain Toeplitz–Hessenberg matrices. This extends recent work concerning determinants of Toeplitz–Hessenberg matrices whose nonzero entries were derived from such sequences as the generalized Fibonacci [5], Motzkin [6], Schröder [7] and Leonardo [8] numbers.
The organization of this paper is as follows. In the next section, we consider determinants of Toeplitz–Hessenberg matrices involving an extension of \(k_n\) or \(k_{2n}\) in terms of the Horadam numbers and their translates. We compute general formulas for the ordinary generating functions of these determinants, and taking the relevant parameters to be unity gives the comparable results involving the sequence \(k_n\). We find simple explicit formulas from the generating functions in several cases in the third section leading to determinant identities involving \(k_n\). As a consequence, one obtains new combinatorial interpretations of several sequences from [13], which have arisen previously in other settings. In the final section, we provide combinatorial arguments for the determinant formulas found in the third. To do so, we introduce into the linear tiling structure a new type of tile that can have arbitrary length. This allows one to find combinatorial meanings of determinants of Toeplitz–Hessenberg matrices with entries in \(k_{n+m}\) or \(k_{2n+m}\) for a fixed \(m\). To complete the combinatorial argument in each case, we then find an appropriate sign-changing involution or provide a direct enumeration depending on if the superdiagonal entry in the associated matrix is \(1\) or \(-1\).
A Toeplitz–Hessenberg matrix \(A_n\) (see, e.g., [12]) is one having the form \[\label{DetHess} A_n:= A_n(a_0; a_1,\ldots,a_n)=\left(\begin{array}{ccccccc} a_1 & a_0 & 0 & \cdots & 0 & 0 \\ a_2 & a_1 & a_0 & \cdots & 0 & 0 \\ a_3 & a_2 & a_1 & \cdots & 0 & 0 \\ \cdots & \cdots & \cdots & \ddots & \cdots & \cdots \\ a_{n-1} & a_{n-2} & a_{n-3} & \cdots & a_1 & a_0 \\ a_{n} & a_{n-1}& a_{n-2} & \cdots & a_2 & a_1 \end{array}\right)\!, \tag{1}\] where \(a_0\neq0\). The determinant of \(A_n\) may be given explicitly, a result known as Trudi’s formula [11, Theorem 1], in terms of a multi-sum over the set of partitions of \(n\) as follows.
Lemma 1.1. If \(n \geq 1\), then \[\label{Trudi} \det(A_n)=\sum\limits_{\widetilde{s}=n}(-a_0)^{n-|s|}{|s| \choose s_1,\ldots,s_n}a_1^{s_1}a_2^{s_2}\cdots a_{n}^{s_n}, \tag{2}\] where \({|s|\choose s_1,\ldots,s_n}=\dfrac{|s|!}{s_1!s_2!\cdots s_n!}\), \(\widetilde{s}=s_1+2s_2+\cdots+ns_n\), \(|s|=s_1+s_2+\cdots+s_n\) and \(s_i\geq 0\) for all i.
The \(a_0=1\) case of (2) is known as Brioschi’s formula [12].
Define the generating functions \[u(x)=\sum\limits_{n\geq1}\det(A_n)x^n \quad\text{and}\quad v(x)=\sum\limits_{i\geq1}a_ix^i.\]
We make frequent use of the following relation between \(u(x)\) and \(v(x)\), see [8].
Lemma 1.2. We have \[\label{lem2e1} u(x)=\dfrac{-\dfrac{1}{a_0}v(-a_0x)}{1+\dfrac{1}{a_0}v(-a_0x)}. \tag{3}\]
We now recall some well-known sequences. Let \(L_n\), \(P_n\) and \(p_n\) denote, respectively, the Lucas, Padovan and Pell number sequences satisfying \(L_n=L_{n-1}+L_{n-2}\) for \(n \geq 2\), \(P_n=P_{n-2}+P_{n-3}\) for \(n \geq 3\) and \(p_n=2p_{n-1}+p_{n-2}\) for \(n \geq 2\), with initial values \(L_0=2,L_1=1\), \(P_0=1,P_1=P_2=0\) and \(p_0=0,p_1=1\). For further information on these sequences, we refer the reader to A000032, A000931 and A000129, respectively, in [13]. The generalized Fibonacci numbers \(G_n\), or Gibonacci as they are sometimes called, are given recursively by \(G_n=G_{n-1}+G_{n-2}\) if \(n \geq 2\), with \(G_0=a\) and \(G_1=b\), where \(a\) and \(b\) are arbitrary (see, e.g., [3, Chapter 2]). Note that \(G_n\) reduces to \(F_n\) for all \(n \geq 0\) when \(a=0, b=1\) and to \(L_n\) when \(a=2, b=1\). Finally, the Horadam numbers, which we will denote here by \(g_n=g_n(a,b,c,d)\), where \(a\), \(b\), \(c\) and \(d\) are variables, satisfy the recursion \(g_n=cg_{n-1}+dg_{n-2}\) for \(n \geq 2\), with \(g_0=a\) and \(g_1=b\) (see, e.g., [9, 16]). Note that \(g_n\) reduces to \(G_n\) when \(c=d=1\) and to \(F_{n+1}\) when all variables are unity.
In this section, we develop some explicit formulas for the generating functions of determinants involving a Horadam number extension of \(k_n\). Recall that the Horadam numbers \(g_n=g_n(a,b,c,d)\) have generating function given by \[\label{gxfune1} g(x)=\sum\limits_{n\geq0}g_nx^n=\dfrac{a+(b-ac)x}{1-cx-dx^2}. \tag{4}\]
Upon computing \(\dfrac{g(x)\pm g(-x)}{2}\), and replacing \(x\) with \(x^{1/2}\), one finds \[ \sum\limits_{n\geq0}g_{2n}x^n =\dfrac{a-(ac^2+ad-bc)x}{1-(c^2+2d)x+d^2x^2}, \label{gxfune2}\ \tag{5}\] \[\sum\limits_{n\geq1}g_{2n-1}x^n =\dfrac{bx+d(ac-b)x^2}{1-(c^2+2d)x+d^2x^2}. \tag{6}\]
Let \(q_n=q_n(a,b,c,d)\) be given by \[q_n=\sum\limits_{i=0}^{n-2}c^{n-i-2}g_i,\qquad n \geq 2,\] with \(q_n=0\) for all integers \(n \leq 1\). Note that \(q_n\) reduces to \(k_{n+1}\), when each parameter is unity, and to \(G_n-b\) when \(c=d=1\), via the well-known Fibonacci number identity \(\sum\limits_{i=1}^{n-1}F_{i}=F_{n+1}-1\) and its extension in terms of \(G_n\) (see, e.g., [15, p. 39]). By comparing the generating functions of both sides, or by a combinatorial argument, one can prove the relation \[\label{t-n/g-n} q_n=\dfrac{g_n-bc^{n-1}}{d}, \qquad n \geq 1. \tag{7}\]
Using (7) or the definition of \(q_n\), together with (4)–(6), one can obtain the following formulas.
Lemma 2.1. We have \[\ \sum\limits_{n\geq1}q_nx^n =\dfrac{ax^2+(b-ac)x^3}{(1-cx)(1-cx-dx^2)}, \label{lem3e1}\ \tag{8}\] \[ \sum\limits_{n\geq1}q_{2n}x^n=\dfrac{ax-(ac^2+ad-2bc)x^2+cd(ac-b)x^3}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)},\label{lem3e2}\ \tag{9}\] \[\sum\limits_{n\geq1}q_{2n-1}x^n =\dfrac{(ac+b)x^2-(ac^3+bd-bc^2)x^3}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}.\label{lem3e3} \tag{10}\]
Note that from (8), we have that \(q_n\) is given recursively by \[\label{tnrec1} q_n=2cq_{n-1}-(c^2-d)q_{n-2}-cdq_{n-3}, \qquad n \geq 4, \tag{11}\] with initial values \(q_1=0\), \(q_2=a\) and \(q_3=ac+b\). From (9) and (10), we have that \(u_n=q_{2n}\) and \(u_n=q_{2n-1}\) both satisfy the recurrence \[\label{tnrec2} u_n=2(c^2+d)u_{n-1}-(c^2+d)^2u_{n-2}+c^2d^2u_{n-3}, \qquad n \geq 4, \tag{12}\] with respective initial values \(u_1=a\), \(u_2=ac^2+ad+2bc\), \(u_3=ac^4+3ac^2d+ad^2+4bc^3+3bcd\) and \(u_1=0\), \(u_2=ac+b\), \(u_3=ac^3+2acd+3bc^2+bd\).
We have the following generating function formulas for \(\det(A_n)\), where \(A_n\) is given by (1), in the case when the sequence \(a_i\) corresponds to an arbitrary translate of \(q_i\). Henceforth, we will write \(\det(a_0;a_1,\ldots,a_n)\) in place of \(\det(A_n(a_0;a_1,\ldots,a_n))\) to simplify notation.
Theorem 2.2. Let \(h_m(x)=h_m(x;s)\) be given by \[h_m(x):=\sum\limits_{n\geq1}\det(s;q_{1+m},q_{2+m},\ldots,q_{n+m})x^n,\] where \(m \in \mathbb{Z}\) and \(s\) is an indeterminate. Then \[\label{gfunth1e1} h_m(x)= \begin{cases} \dfrac{q_{m+1}x+s(cdq_{m-1}+(c^2-d)q_m)x^2-cds^2q_mx^3}{1-(q_{m+1}-2cs)x-s(cdq_{m-1}+(c^2-d)(q_m-s))x^2+cds^2(q_m-s)x^3}, & m\geq2;\\[2mm] \dfrac{(-sx)^{1-m}(ax+s(ac-b)x^2)}{1+2csx+s^2(c^2-d)x^2-cds^3x^3-(-sx)^{1-m}(ax+s(ac-b)x^2)}, & m\leq1. \end{cases} \tag{13}\]
Proof. We first extend (8) to an arbitrary translate of \(q_n\). If \(m \geq0\), then \[\begin{aligned} \sum\limits_{n\geq1}q_{n+m}x^n&=\sum\limits_{n \geq m+1}q_nx^{n-m}=x^{-m}\left(\sum\limits_{n\geq1}q_nx^n-\sum\limits_{n=1}^mq_nx^n\right)\\ &=\dfrac{ax^2+(b-ac)x^3-(1-cx)(1-cx-dx^2)\sum\limits_{n=1}^mq_nx^n}{x^m(1-cx)(1-cx-dx^2)}, \end{aligned}\] where we have made use of (8). If \(m \geq 3\), then \[\begin{aligned} (1-cx)&(1-cx-dx^2)\sum\limits_{n=1}^mq_nx^n\\ &=(1-2cx+(c^2-d)x^2+cdx^3)(ax^2+(ac+b)x^3+q_4x^4+\cdots+q_mx^m)\\ &=ax^2+(b-ac)x^3+0x^4+\cdots+0x^m+(cdq_{m-2}+(c^2-d)q_{m-1}-2cq_m)x^{m+1}\\ &\quad+(cdq_{m-1}+(c^2-d)q_m)x^{m+2}+cdq_mx^{m+3}\\ &=ax^2+(b-ac)x^3-q_{m+1}x^{m+1}+(cdq_{m-1}+(c^2-d)q_m)x^{m+2}+cdq_mx^{m+3}, \end{aligned}\] by repeated use of (11). If \[v_m(x):=\sum\limits_{n\geq 1}q_{n+m}x^n,\] then we have \[\label{vmeq1} v_m(x)=\dfrac{q_{m+1}x-(cdq_{m-1}+(c^2-d)q_m)x^2-cdq_mx^3}{(1-cx)(1-cx-dx^2)}, \qquad m \geq 3. \tag{14}\]
Note that (14) is also seen to hold for \(m=2\), upon writing \[\begin{aligned} v_2(x)=&\sum\limits_{n\geq3}q_nx^{n-2}\\ =&\dfrac{a+(b-ac)x}{(1-cx)(1-cx-dx^2)}-a\\ =&\dfrac{(ac+b)x-a(c^2-d)x^2-acdx^3}{(1-cx)(1-cx-dx^2)}. \end{aligned}\]
By (3), we then have for \(m \geq 2\), \[\begin{aligned} h_m(x)&=\dfrac{-\dfrac{1}{s}v_m(-sx)}{1+\dfrac{1}{s}v_m(-sx)}\\ &=\dfrac{\dfrac{q_{m+1}x+s(cdq_{m-1}+(c^2-d)q_m)x^2-cds^2q_mx^3}{1+2csx+s^2(c^2-d)x^2-cds^3x^3}}{1-\dfrac{q_{m+1}x+s(cdq_{m-1}+(c^2-d)q_m)x^2-cds^2q_mx^3}{1+2csx+s^2(c^2-d)x^2-cds^3x^3}}\\ &=\dfrac{q_{m+1}x+s(cdq_{m-1}+(c^2-d)q_m)x^2-cds^2q_mx^3}{1-(q_{m+1}-2cs)x-s(cdq_{m-1}+(c^2-d)(q_m-s))x^2+cds^2(q_m-s)x^3}, \end{aligned}\] which establishes the first case of (13).
On the other hand, if \(m \leq 1\), then \[\begin{aligned} v_m(x)=\sum\limits_{n\geq1}q_{n+m}x^n=\sum\limits_{n \geq m+1}q_nx^{n-m}=x^{-m}\sum\limits_{n\geq1}q_nx^n=\dfrac{x^{2-m}(a+(b-ac)x)}{(1-cx)(1-cx-dx^2)}. \end{aligned}\]
Hence, by (3), we have \[\begin{aligned} h_m(x)&=\dfrac{\dfrac{-\dfrac{1}{s}(-sx)^{2-m}(a+s(ac-b)x)}{1+2csx+s^2(c^2-d)x^2-cds^3x^3}}{1-\dfrac{-\dfrac{1}{s}(-sx)^{2-m}(a+s(ac-b)x)}{1+2csx+s^2(c^2-d)x^2-cds^3x^3}}\\ &=\dfrac{\dfrac{(-sx)^{1-m}(ax+s(ac-b)x^2)}{1+2csx+s^2(c^2-d)x^2-cds^3x^3}}{1-\dfrac{(-sx)^{1-m}(ax+s(ac-b)x^2)}{1+2csx+s^2(c^2-d)x^2-cds^3x^3}}, \end{aligned}\] which implies the second case of (13) and completes the proof. ◻
Let \(r_n=r_n(a,b)\) be given by \(q_n(a,b,1,1)\). Note that letting \(c=d=1\) in (7) implies \(r_n=G_n-b\) for all \(n \geq 1\). Taking \(c=d=1\) in Theorem 2.2 yields the following result for \(r_n\).
Corollary 2.3. Let \(j_m(x)=j_m(x;s)\) for an integer \(m\) be given by \[j_m(x):=\sum\limits_{n\geq1}\det(s;r_{1+m},r_{2+m},\ldots,r_{n+m})x^n.\] Then we have \[\label{gnfunth1c1e1} j_m(x)= \begin{cases} \dfrac{r_{m+1}x+sr_{m-1}x^2-s^2r_mx^3}{1-(r_{m+1}-2s)x-sr_{m-1}x^2+s^2(r_m-s)x^3}, & m\geq2;\\ \dfrac{(-sx)^{1-m}(ax+s(a-b)x^2)}{1+2sx-s^3x^3-(-sx)^{1-m}(ax+s(a-b)x^2)}, & m\leq1. \end{cases} \tag{15}\]
We have the following comparable result for the generating function of \(\det(A_n)\) in the case when \(a_i\) is a translate of the half-sequence \(q_{2n}\).
Theorem 2.4. Let \(k_m(x)=k_m(x;s)\) be given by \[k_m(x):=\sum\limits_{n\geq1}\det(s;q_{2+m},q_{4+m},\ldots,q_{2n+m})x^n,\] where \(m \in \mathbb{Z}\) and \(s\) is an indeterminate. If \(m \geq 3\), then \[\begin{aligned} \label{gnfunth2e1} k_m(x)&=\tfrac{q_{m+2}x+s((c^2+d)^2q_m-c^2d^2q_{m-2})x^2+(cds)^2q_mx^3}{1+(2s(c^2+d)-q_{m+2})x+s((c^2+d)^2(s-q_m)+c^2d^2q_{m-2})x^2+(cds)^2(s-q_m)x^3}, \end{aligned} \tag{16}\] with \[\begin{aligned} \label{gnfunth2e2} k_2(x)&=\tfrac{q_4x+s(ac^4+ac^2d+ad^2+bcd)x^2+(cds)^2q_2x^3}{1+(2s(c^2+d)-q_4)x-s(ac^4+ac^2d+ad^2+bcd-s(c^2+d)^2)x^2+(cds)^2(s-q_2)x^3}. \end{aligned} \tag{17}\]
If \(m \leq 1\), then \[\label{gnfunth2e3} k_m(x)= \begin{cases} \frac{(-sx)^p(ax+s(ac^2+ad-2bc)x^2+cds^2(ac-b)x^3)}{(1+s(c^2+d)x)^2+c^2d^2s^3x^3-(-sx)^p(ax+s(ac^2+ad-2bc)x^2+cds^2(ac-b)x^3)}, & m=-2p;\\ \frac{(-sx)^{p}((ac+b)x+s(ac^3+bd-bc^2)x^2)}{(1+s(c^2+d)x)^2+c^2d^2s^3x^3-(-sx)^{p}((ac+b)x+s(ac^3+bd-bc^2)x^2)}, & m=1-2p, \end{cases} \tag{18}\] where \(p\) denotes a non-negative integer.
Proof. First assume \(m \geq 6\), with \(m=2r\). By (9), we have \[\begin{aligned} w_m(x)&:=\sum\limits_{n\geq1}q_{2n+m}x^n=\sum\limits_{n\geq1}q_{2n+2r}x^n=\sum\limits_{n\geq r+1}q_{2n}x^{n-r}\\ &=x^{-r}\left(\dfrac{ax-(ac^2+ad-2bc)x^2+cd(ac-b)x^3}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}-\sum\limits_{n=1}^rq_{2n}x^n\right). \end{aligned}\] Applying the recurrence (12) gives \[\begin{aligned} &(1-c^2x)(1-(c^2+2d)x+d^2x^2)\sum\limits_{n=1}^rq_{2n}x^n\\ &=(1-2(c^2+d)x+(c^2+d)^2x^2-c^2d^2x^3)(ax+(ac^2+ad+2bc)x^2\\ &\quad+(ac^4+3ac^2d+ad^2+4bc^3+3bcd)x^3+q_8x^4+\cdots+q_{2r}x^{r})\\ &=ax-(ac^2+ad-2bc)x^2+cd(ac-b)x^3+0x^4+\cdots+0x^r-(2(c^2+d)q_{2r}\\ &\quad-(c^2+d)^2q_{2r-2}+c^2d^2q_{2r-4})x^{r+1}+((c^2+d)^2q_{2r}-c^2d^2q_{2r-2})x^{r+2}-c^2d^2q_{2r}x^{r+3}\\ &=ax-(ac^2+ad-2bc)x^2+cd(ac-b)x^3-q_{m+2}x^{r+1}+((c^2+d)^2q_m-c^2d^2q_{m-2})x^{r+2}\\ &\quad-c^2d^2q_mx^{r+3}. \end{aligned}\]
Substituting this into the last formula above for \(w_m(x)\), and simplifying, implies \[\label{wmxe1} w_m(x)=\dfrac{q_{m+2}x-((c^2+d)^2q_m-c^2d^2q_{m-2})x^{2}+c^2d^2q_mx^3}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}, \qquad m \geq 6 ~\text{ even}. \tag{19}\]
If \(m=4\), then \[\begin{aligned} \sum\limits_{n\geq1}q_{2n+4}x^n&=\sum\limits_{n\geq3}q_{2n}x^{n-2}\\ &=x^{-1}\left(\dfrac{a-(ac^2+ad-2bc)x+cd(ac-b)x^2}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}-a-(ac^2+ad+2bc)x\right)\\ &=\dfrac{q_6x-((c^2+d)^2q_4-c^2d^2q_2)x^2+c^2d^2q_4x^3}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}, \end{aligned}\] and hence (19) also holds for \(m=4\).
Now suppose \(m \geq 5\) is odd, with \(m=2r-1\) for some \(r \geq 3\). Upon writing \[\begin{aligned} w_m(x)&=\sum\limits_{n\geq1}q_{2n+2r-1}x^n=\sum\limits_{n\geq r+1}q_{2n-1}x^{n-r}\\ &=x^{-r}\left(\dfrac{(ac+b)x^2-(ac^3+bd-bc^2)x^3}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}-\sum\limits_{n=1}^rq_{2n-1}x^n\right), \end{aligned}\] and performing a similar calculation as before, we have that (19) also holds for \(m \geq 5\) odd. A separate calculation for \(m=3\) (similar to that given in the \(m=4\) case above) shows that (19) holds for \(m=3\) as well, and hence for all \(m \geq 3\). By (3) and (19), we then have for \(m \geq 3\), \[\begin{aligned} k_m(x)&=\dfrac{-\dfrac{1}{s}w_m(-sx)}{1+\dfrac{1}{s}w_m(-sx)}\\ &=\dfrac{\dfrac{-\dfrac{1}{s}(-sq_{m+2}x-s^2((c^2+d)^2q_m-c^2d^2q_{m-2})x^2-c^2d^2s^3q_mx^3)}{1+2s(c^2+d)x+s^2(c^2+d)^2x^2+c^2d^2s^3x^3}}{1-\dfrac{-\dfrac{1}{s}(-sq_{m+2}x-s^2((c^2+d)^2q_m-c^2d^2q_{m-2})x^2-c^2d^2s^3q_mx^3)}{1+2s(c^2+d)x+s^2(c^2+d)^2x^2+c^2d^2s^3x^3}}\\ &=\tfrac{q_{m+2}x+s((c^2+d)^2q_m-c^2d^2q_{m-2})x^2+(cds)^2q_mx^3}{1+(2s(c^2+d)-q_{m+2})x+s((c^2+d)^2(s-q_m)+c^2d^2q_{m-2})x^2+(cds)^2(s-q_m)x^3}, \end{aligned}\] which establishes (16). If \(m=2\), then \[\begin{aligned} w_2(x)&=\sum\limits_{n\geq1}q_{2n+2}x^n=x^{-1}\sum\limits_{n\geq2}q_{2n}x^n=\dfrac{a-(ac^2+ad-2bc)x+cd(ac-b)x^2}{(1-c^2x)(1-(c^2+2d)x+d^2x^2)}-a\\ &=\dfrac{(ac^2+ad+2bc)x-(a(c^2+d)^2-cd(ac-b))x^2+ac^2d^2x^3}{1-2(c^2+d)x+(c^2+d)^2x^2-c^2d^2x^3}, \end{aligned}\] and applying (3) yields (17).
Now suppose \(m \leq 1\). If \(m\) is even and \(m=-2p\) for some \(p\geq 0\), then \[\begin{aligned} w_m(x)&=\sum\limits_{n\geq1}q_{2n-2p}x^n=\sum\limits_{n\geq 1-p}q_{2n}x^{n+p}=x^p\sum\limits_{n\geq1}q_{2n}x^n\\ &=\dfrac{x^{p+1}(a-(ac^2+ad-2bc)x+cd(ac-b)x^2)}{1-2(c^2+d)x+(c^2+d)^2x^2-c^2d^2x^3}, \end{aligned}\] and hence \[k_m(x)=\dfrac{-\dfrac{1}{s}w_m(-sx)}{1+\dfrac{1}{s}w_m(-sx)}=\dfrac{\dfrac{(-sx)^p(ax+s(ac^2+ad-2bc)x^2+cds^2(ac-b)x^3)}{1+2s(c^2+d)x+s^2(c^2+d)^2x^2+c^2d^2s^3x^3}}{1-\dfrac{(-sx)^p(ax+s(ac^2+ad-2bc)x^2+cds^2(ac-b)x^3)}{1+2s(c^2+d)x+s^2(c^2+d)^2x^2+c^2d^2s^3x^3}},\] which yields the even case of (18). A similar argument applies to the odd case, upon writing \(m=1-2p\) for some \(p \geq0\) and proceeding as above, which completes the proof. ◻
Letting \(c=d=1\) in Theorem 2.4 gives the following result for determinants involving the sequence \(r_{2n+m}\).
Corollary 2.5. Let \(\ell_m(x)=\ell_m(x;s)\) for an integer \(m\) be given by \[\ell_m(x):=\sum\limits_{n\geq1}\det(s;r_{2+m},r_{4+m},\ldots,r_{2n+m})x^n.\]
If \(m \geq 3\), then \[\label{gnfunth2c1e1} \ell_m(x)=\dfrac{r_{m+2}x+s(4r_m-r_{m-2})x^2+s^2r_mx^3}{1+(4s-r_{m+2})x+s(4s-4r_m+r_{m-2})x^2+s^2(s-r_m)x^3}, \tag{20}\] with \[\label{gnfunth2c1e2} \ell_2(x)=\dfrac{2(a+b)x+s(3a+b)x^2+as^2x^3}{1+2(2s-a-b)x-s(3a+b-4s)x^2+s^2(s-a)x^3}. \tag{21}\]
If \(m \leq 1\), then \[\label{gnfunth2c1e3} \ell_m(x)= \begin{cases} \dfrac{(-sx)^p(ax+2s(a-b)x^2+s^2(a-b)x^3)}{1+4sx+4s^2x^2+s^3x^3-(-sx)^p(ax+2s(a-b)x^2+s^2(a-b)x^3)}, & m=-2p;\\ \dfrac{(-sx)^{p}((a+b)x+asx^2)}{1+4sx+4s^2x^2+s^3x^3-(-sx)^{p}((a+b)x+asx^2)}, & m=1-2p, \end{cases} \tag{22}\] where \(p\) denotes a non-negative integer.
As particular cases of the results in the prior section, one can obtain simple explicit formulas for determinants with entries in \(k_n\). We start with following new and somewhat curious relation between the Padovan subsequence \(P_{5n+2}\) and \(k_{2n+1}\).
Theorem 3.1. If \(n \geq 1\), then \[\label{eq0} \det(-1;k_3,k_5,\ldots,k_{2n+1})=P_{5n+2}. \tag{23}\]
Proof. Letting \(a=b=1\), \(m=0\) and \(s=-1\) in (22) gives \[\sum\limits_{n\geq1}d_nx^n=\dfrac{x}{1-5x+4x^2-x^3},\] where \(d_n=\det(-1;k_3,\ldots,k_{2n+1})\). From the form of its generating function, we have \(d_n=5d_{n-1}-4d_{n-2}+d_{n-3}\) for \(n \geq 4\), with \(d_1=1\), \(d_2=5\) and \(d_3=21\). Observe that \(P_n\) satisfies the recurrence \[\label{Pnthme1} P_n=5P_{n-5}-4P_{n-10}+P_{n-15}, \qquad n \geq 15. \tag{24}\]
To realize (24), note that it may be verified directly for \(n=15\), \(16\) and \(17\), and then follows by induction for \(n \geq 18\) using the defining recurrence \(P_n=P_{n-2}+P_{n-3}\). Let \(e_n=P_{5n+2}\) for \(n \geq 1\). By (24), we have \(e_n=5e_{n-1}-4e_{n-2}+e_{n-3}\) for \(n \geq 4\), with initial values \(e_1=1\), \(e_2=5\) and \(e_3=21\). This implies \(d_n=e_n\) for all \(n \geq 1\), as desired. ◻
It is also possible to find a simple explicit formula for the determinant in the following specific cases.
Theorem 3.2. Let \(n \geq 1\), unless stated otherwise. Then we have \[ \det(-1;k_1,k_2,\ldots,k_n) =2^{n-3}, \qquad n \geq 3, \label{eq1}\ \tag{25}\] \[\det(1;k_2,k_3,\ldots,k_{n+1}) =\sum\limits_{k=1}^{\left\lfloor\dfrac{n+1}{3}\right\rfloor}(-1)^{n-k}\binom{n-k}{2k-1}, \label{eq2}\ \tag{26}\] \[ \det(1;k_3,k_4,\ldots,k_{n+2}) =\sum\limits_{k=0}^{\left\lfloor\dfrac{n-1}{3}\right\rfloor}(-1)^{n-k-1}\binom{n-2k-1}{k}, \label{eq3}\ \tag{27}\] \[ \det(-1;k_3,k_4,\ldots,k_{n+2}) =\sum\limits_{k=0}^{\left\lfloor\dfrac{n-1}{3}\right\rfloor}(-1)^{k}3^{n-3k-1}\binom{n-2k-1}{k}, \label{eq4}\ \tag{28}\] \[ \det(1;k_4,k_5,\ldots,k_{n+3}) =0, \qquad n \geq 4, \label{eq5}\ \tag{29}\] \[\det(-1;k_1,k_3,\ldots,k_{2n-1}) =\sum\limits_{k=0}^{n-2}\binom{n+2k}{3k+2}, \label{eq6}\ \tag{30}\] \[ \det(-1;k_2,k_4,\ldots,k_{2n}) =\sum\limits_{k=2}^{n}\binom{n-2}{k-2}p_k, \label{eq7}\ \tag{31}\] \[\det(1;k_4,k_6,\ldots,k_{2n+2}) =\sum\limits_{k=0}^{n+1}(-1)^{n-k}\binom{n+2k+1}{3k}, \label{eq8}\ \tag{32}\] \[ \det(1;k_5,k_7,\ldots,k_{2n+3}) =0, \qquad n \geq 4. \label{eq9} \tag{33}\]
Proof. Let \(\alpha_m^+=j_m(x;1)\) and \(\alpha_m^-=j_m(x;-1)\) for a fixed integer \(m\), where \(j_m(x)\) is as defined in Corollary 2.3 and is evaluated at \(a=b=1\) in both instances. Note \[\alpha_m^{\pm}=\sum\limits_{n\geq1}\det(\pm1;k_{m+2},k_{m+3},\ldots,k_{m+n+1})x^n, \qquad m \in \mathbb{Z},\] by the definitions, where \(k_n=0\) if \(n \leq0\). Letting \(m=s=-1\) in (15) gives \(\alpha_{-1}^-=\dfrac{x^3}{1-2x}\), which implies (25). Letting \(m=0,s=1\) gives \(\alpha_0^+=-\dfrac{x^2}{(1+x)^2-x^3}\). On the other hand, \[\begin{aligned} \sum\limits_{n\geq 2}x^n\sum\limits_{k=1}^{\left\lfloor\dfrac{n+1}{3}\right\rfloor}(-1)^{n-k}\binom{n-k}{2k-1}&=\sum\limits_{k\geq1}(-1)^k\sum\limits_{n \geq 3k-1}\binom{n-k}{2k-1}(-x)^n\\ &=\sum\limits_{k\geq1}(-1)^k\cdot\dfrac{(-x)^{3k-1}}{(1+x)^{2k}}\\ &=-\sum\limits_{k\geq1}\dfrac{x^{3k-1}}{(1+x)^{2k}}\\ &=-\dfrac{x^2}{(1+x)^2-x^3}\\ &=\alpha_0^+, \end{aligned}\] which implies (26). Letting \(m=1\) and \(s=1\) or \(-1\) in (15) gives \(\alpha_1^+=\dfrac{x}{1+x-x^3}\) and \(\alpha_1^-=\dfrac{x}{1-3x+x^3}\), and a similar computation as above involving the respective right-hand side quantities yields (27) and (28). Finally, letting \(m=2,s=1\) gives \(\alpha_2^+=2x-x^3\), which immediately implies (29).
Now let \(\beta_m^{\pm}=\ell_m(x;\pm1)\), where it is assumed \(\ell_m(x)\) from Corollary 2.5 is evaluated at \(a=b=1\). Note \(\beta_m^{\pm}=\sum\limits_{n\geq1}\det(\pm1;k_{m+3},k_{m+5},\ldots,k_{m+2n+1})x^n\), by the definitions. Letting \(m=s=-1\) in (22) gives \(\beta_{-1}^-=\dfrac{x^2(2-x)}{1-4x+2x^2}\). Also, we have \[\begin{aligned} \sum\limits_{n\geq2}x^n\sum\limits_{k=2}^n\binom{n-2}{k-2}p_k &=\sum\limits_{k\geq1}p_{k+1}\sum\limits_{n \geq k+1}\binom{n-2}{k-1}x^n\\ &=\sum\limits_{k\geq1}p_{k+1}\dfrac{x^{k+1}}{(1-x)^k}\\ &=x\tau\left(\dfrac{x}{1-x}\right)\\ &=\dfrac{x^2(2-x)}{1-4x+2x^2}\\ &=\beta_{-1}^{-}, \end{aligned}\] which implies (21), where \[\tau(y)=\sum\limits_{k\geq1}p_{k+1}y^k=\dfrac{2y+y^2}{1-2y-y^2},\] denotes the Pell number generating function. Letting \((m,s)=(-2,-1)\) and \((1,1)\) in (22) gives \(\beta_{-2}^-=\dfrac{x^2}{1-4x+3x^2-x^3}\) and \(\beta_1^+=\dfrac{x(2+x)}{1+2x+3x^2+x^3}\), and a comparable calculation involving the respective right-hand side quantities yields (30) and (32). Finally, letting \(s=1\) in (21) gives \(\beta_2^+=x(x+2)^2\), which immediately implies (33). ◻
Remark 3.3. As a consequence of our results, one obtains apparently new combinatorial interpretations for several OEIS sequences in terms of certain Toeplitz–Hessenberg matrices. For instance, we have \(\det(1;k_3,\ldots,k_{n+2})=\text{A176971}(n+2)\), \(\det(-1;k_3,\ldots,k_{n+2})=\text{A076264}(n-1)\) and \(\det(1;k_4,\ldots,k_{2n+2})=(-1)^n\text{A185963}(n+1)\) for all \(n \geq 1\), where \(\text{A}\#\#\#\#\#\#(m)\) denotes the OEIS sequence parameterized as in the indicated entry. Note that \(\det(1;k_3,\ldots,k_{n+2})\) is also given by \(P_{1-n}\) for \(n \geq 1\), where \(P_{-m}\) for \(m \geq0\) denotes the extension of the Padovan numbers to negative indices. Further, we have that \(\det(-1;k_2,\ldots,k_{2n})=\text{A003480}(n-1)\) for \(n \geq 2\), with this determinant also expressible as \[\dfrac{1}{4\sqrt{2}}\left((2+\sqrt{2})^n-(2-\sqrt{2})^n\right).\]
Expanding the last expression using the binomial theorem, and equating with the right side of (31), yields the identity \[\sum\limits_{k=0}^{\left\lfloor\dfrac{n-1}{2}\right\rfloor}\binom{n}{2k+1}2^{n-k-2}=\det(-1;k_2,\ldots,k_{2n})=\sum\limits_{k=2}^{n}\binom{n-2}{k-2}p_k, \qquad n \geq 2.\]
Note that \(\det(-1;k_2,\ldots,k_{2n})\) is also given for \(n \geq 2\) by \(2^{(n-2)/2}p_n\) if \(n\) is even and by \(2^{(n-5)/2}Q_n\) if \(n\) is odd, where \(Q_n\) denotes the \(n\)-th Pell–Lucas number.
By Lemma 1.1, the determinant formulas in Theorems 3.1 and 3.2 imply the following identities involving \(k_n\), where we make use of the notation from that lemma.
Corollary 3.4. Let \(n \geq 1\) unless stated otherwise. Then we have \[\begin{aligned} \sum\limits_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}k_1^{s_1}k_2^{s_2}\cdots k_{n}^{s_n}&= 2^{n-3}, \qquad n \geq 3,\\ \sum\limits_{\widetilde{s}=n}(-1)^{|s|}{|s|\choose s_1,\ldots,s_n}k_2^{s_1}k_3^{s_2}\cdots k_{n+1}^{s_n}&=\sum\limits_{k=1}^{\left\lfloor\dfrac{n+1}{3}\right\rfloor}(-1)^k\binom{n-k}{2k-1},\\ \sum\limits_{\widetilde{s}=n}(-1)^{|s|-1}{|s|\choose s_1,\ldots,s_n}k_3^{s_1}k_4^{s_2}\cdots k_{n+2}^{s_n}&=\sum\limits_{k=0}^{\left\lfloor\dfrac{n-1}{3}\right\rfloor}(-1)^{k}\binom{n-2k-1}{k},\\ \sum\limits_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}k_3^{s_1}k_4^{s_2}\cdots k_{n+2}^{s_n}&=\sum\limits_{k=0}^{\left\lfloor\dfrac{n-1}{3}\right\rfloor}(-1)^{k}3^{n-3k-1}\binom{n-2k-1}{k}, \\ \sum\limits_{\widetilde{s}=n}(-1)^{|s|}{|s|\choose s_1,\ldots,s_n}k_4^{s_1}k_5^{s_2}\cdots k_{n+3}^{s_n}&=0, \qquad n \geq 4,\\ \sum\limits_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}k_1^{s_1}k_3^{s_2}\cdots k_{2n-1}^{s_n}&=\sum\limits_{k=0}^{n-2}\binom{n+2k}{3k+2},\\ \sum\limits_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}k_2^{s_1}k_4^{s_2}\cdots k_{2n}^{s_n}&=\sum\limits_{k=2}^{n}\binom{n-2}{k-2}p_k,\\ \sum\limits_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}k_3^{s_1}k_5^{s_2}\cdots k_{2n+1}^{s_n}&=P_{5n+2},\\ \sum\limits_{\widetilde{s}=n}(-1)^{|s|}{|s|\choose s_1,\ldots,s_n}k_4^{s_1}k_6^{s_2}\cdots k_{2n+2}^{s_n}&=\sum\limits_{k=0}^{n+1}(-1)^k\binom{n+2k+1}{3k},\\ \sum\limits_{\widetilde{s}=n}(-1)^{|s|}{|s|\choose s_1,\ldots,s_n}k_5^{s_1}k_7^{s_2}\cdots k_{2n+3}^{s_n}&=0, \qquad n \geq 4. \end{aligned}\]
Remark 3.5. Let \(\ell_n=L_n-1\) for \(n \geq 1\), with \(\ell_n=0\) otherwise; see A001610 in [13]. By taking \(a=2\) and \(b=1\) in Corollaries 2.3 and 2.5, and extracting the coefficient of \(x^n\) in the resulting generating functions, one can obtain Lucas number analogues of the results in this section involving translates of \(\ell_n\). We leave it to the interested reader to explore these further results as well as possible additional identities involving \(k_n\) obtained by considering other values of the fixed integer \(m\).
Recall the definition of the determinant of an \(n \times n\) matrix \(A\) given by \[\label{dete1} \det(A)=\sum\limits_{\pi \in \mathcal{S}_n}(-1)^{\text{sgn}(\pi)}a_{1,\sigma(1)}a_{2,\sigma(2)}\cdots a_{n,\sigma(n)}, \tag{34}\] where \(A=(a_{i,j})_{1\leq i,j \leq n}\) and \(\text{sgn}(\pi)\) denotes the sign of the permutation \(\pi\). In the case when \(A\) is Toeplitz–Hessenberg, all \(\pi \in \mathcal{S}_n\) contribute zero to the sum in (34) with the exception of those in which every cycle consists of a set of consecutive integers in the natural order. Assuming that cycles of such a permutation \(\pi\) are arranged from left to right in increasing order of their smallest (= first) elements, one may regard these permutations \(\pi\) as compositions of \(n\), with the various cycle lengths corresponding to part sizes. Let \(\mathcal{C}_{n,m}\) for \(1 \leq m \leq n\) denote the set of compositions of a positive integer \(n\) with \(m\) parts and let \(\mathcal{C}_n=\cup_{m=1}^n\mathcal{C}_{n,m}\) for \(n \geq 1\). Let \(c=(c_1,c_2,\ldots)\) denote an arbitrary member of \(\mathcal{C}_n\). Then, in the case when \(A\) is Toeplitz–Hessenberg, formula (34) may be written as \[\label{dete2} \det(A)=\sum\limits_{c \in \mathcal{C}_n}(-a_0)^{n-\mu(c)}a_{c_1}a_{c_2}\cdots, \tag{35}\] where \((a_i)_{i\geq0}\) is the sequence associated with \(A\) and \(\mu(c)\) denotes the number of parts of the composition \(c\).
Assuming \(a_i\) for each \(i \geq 1\) is a non-negative integer, one may interpret the right side of (35) combinatorially as follows. Let \(\Omega_i\) for \(i \geq 1\) denote a combinatorial structure enumerated by \(a_i\), where one takes \(\Omega_i\) to be empty in cases when \(a_i=0\). We overlay the part \(c_i\) of \(c\) with some \(\lambda^{(i)} \in \Omega_{c_i}\) for each \(i\) and consider the concatenation \(\lambda=\lambda^{(1)}\lambda^{(2)}\cdots\) in which the ending section of each \(\lambda^{(i)}\) is distinguished in some way (alternatively, one may consider the set of vectors of the form \((\lambda^{(1)},\lambda^{(2)},\ldots)\), where the number of components can range from \(1\) to \(n\)). Let \(\Upsilon_{n,m}\) for \(1 \leq m \leq n\) denote the set of all \(\lambda\) that arise in this way from members of \(\mathcal{C}_{n,m}\) and let \(\Upsilon_n=\cup_{m=1}^n\Upsilon_{n,m}\). Then, by (35), we have \[\det(A)=\sum\limits_{\lambda \in \Upsilon_n}\text{wght}(\lambda),\] where the weight of \(\lambda \in \Upsilon_{n,m}\) is given by \((-a_0)^{n-m}\).
Here, we will consider several cases when \(a_0=\pm1\) and \(\Omega_i\) is a certain set of tilings. For other examples of weighted composition sums, see, e.g., [14, p. 46] and also related work on \(m\)-color compositions [1] and \(f(m)\)-color compositions [4, 10] of \(n\) for various functions \(f\) of \(m\). Note that when \(a_0=-1\), each member of \(\Upsilon_n\) is weighted by unity and hence \(\det(A)=|\Upsilon_n|\) in this case. On the other hand, if \(a_0=1\), then we have \(\det(A)=\sigma(\Upsilon_n)\), where the sign of \(\lambda \in \Upsilon_{n,m}\) is defined as \((-1)^{n-m}\) and \(\sigma(S)\) denotes the sum of the signs of the members of a set \(S\). In the proofs below, the \(\Omega_i\) for \(i \geq 1\) will be sets of tilings of length \(i\) or \(2i\) in which the final tile is distinguished in some way from all others. Then members \(\lambda=\lambda^{(1)}\lambda^{(2)}\cdots \in \Upsilon_n\) in this case correspond to certain types of tilings of length \(n\) or \(2n\) in which the starting points of the various subtilings \(\lambda^{(i)}\) can be determined by the relative positions of the distinguished tiles within \(\lambda\). The problem of computing \(\det(A)\) then reduces to one of finding \(|\Upsilon_n|\) when \(a_0=-1\) or \(\sigma(\Upsilon_n)\) when \(a_0=1\). We remark that a comparable strategy involving lattice paths instead of tilings has been employed in, for example, [6, 7] to establish formulas for Motzkin and Schröder number determinants by combinatorial arguments.
We now apply the combinatorial interpretation described above for \(\det(A)\) when \(A\) is Toeplitz–Hessenberg in establishing the formulas from Theorems 3.1 and 3.2. We first recall some terminology and notation. By a tile, we mean a \(1 \times m\) rectangular piece for some \(m \geq 1\) capable of covering \(m\) consecutive positions. A (linear) tiling of length \(n\) is a covering of the numbers \(1,2,\ldots,n\), written in a row, by non-overlapping tiles of varying lengths, but which are otherwise indistinguishable. Squares and dominos refer to tiles of length \(1\) or \(2\), respectively, and are denoted by \(s\) and \(d\). The set of square-and-domino tilings of length \(n\) (wherein \(m=1\) or \(2\) for all tiles) is denoted by \(\mathcal{F}_n\) and has cardinality given by \(F_{n+1}\) for all \(n \geq 0\) (see, e.g., [3, Chapter 1]). We extend the set \(\mathcal{F}_n\) by allowing a third kind of tile, denoted by \(t_i\), which covers \(i\) consecutive numbers for some \(i \geq 1\). Note that when \(i=1\) or \(2\), a \(t_i\) will be considered as a second kind of tile that is distinct from a square or domino. Finally, a tile will be described as terminal if it is last in the sequence of tiles comprising some tiling, and as non-terminal otherwise. The same descriptors will be applied to parts of a composition.
We now define several classes of tilings. First, let \(\mathcal{U}_n\) denote the set of linear tilings of length \(n\) using \(s\), \(d\) or \(t_i\) pieces for any \(i \geq 1\). Let \(\mathcal{A}_n\), \(\mathcal{B}_n\) and \(\mathcal{D}_n\) be the subsets of \(\mathcal{U}_n\) consisting of those tilings that end in a \(t_i\) for some \(i\) such that only \(t_i\) pieces for which \(i \geq 3\), \(i \geq 2\) or \(i \geq 1\), respectively, are allowed. Further, let \(\mathcal{E}_n\) be the set of marked tilings of length \(n\) derived from members of \(\mathcal{U}_n\) by always marking the final piece as well as any \(t_i\) and optionally marking any non-terminal squares and dominos. Define the sign of \(\lambda \in \mathcal{U}_n\) by \((-1)^{n-\mu(\lambda)}\) and the sign of \(\rho \in \mathcal{E}_n\) by \((-1)^{n-\nu(\rho)}\), where \(\mu(\lambda)\) denotes the number of \(t_i\) in \(\lambda\) and \(\nu(\rho)\) the number of marked pieces in \(\rho\).
We also need to consider several sets consisting of tilings of even length (i.e., that have semi-length indexed by \(n\) for \(n \geq 1\)). Let \(\mathcal{G}_n\) be the subset of \(\mathcal{U}_{2n}\) consisting of those tilings satisfying (a) \(i \geq 4\) in all \(t_i\) pieces, (b) the final tile is a \(t_i\) and (c) the last number covered by any \(t_i\) is even. Let \(\mathcal{H}_n\), \(\mathcal{I}_n\) and \(\mathcal{J}_n\) denote the respective subsets of \(\mathcal{A}_{2n}\), \(\mathcal{B}_{2n}\) and \(\mathcal{D}_{2n}\) consisting of those tilings that satisfy the following property: the last number covered by any \(t_i\) piece is even. Let \(\mathcal{K}_n\) be the subset of \(\mathcal{E}_{2n}\) whose members satisfy this same property with regard to any marked piece. Finally, define the sign of \(\lambda \in \mathcal{G}_n\), \(\mathcal{H}_n\), \(\mathcal{I}_n\) or \(\mathcal{J}_n\) by \((-1)^{n-\mu(\lambda)}\) and the sign of \(\rho \in \mathcal{K}_n\) by \((-1)^{n-\nu(\rho)}\).
The cardinality and the sum of signs of the sets \(\mathcal{A}_n\) through \(\mathcal{K}_n\) above can be expressed in terms of determinants as follows. For example, a member \(\lambda \in \mathcal{A}_n\) may be decomposed as \(\lambda=\lambda^{(1)}\cdots \lambda^{(m)}\) for some \(m \geq 1\) such that each \(\lambda^{(j)}\) is of the form \(\lambda^{(j)}=\alpha t_{\ell}\) for some possibly empty square-and-domino tiling \(\alpha\) and \(\ell \geq 3\). Let \(p_j:=|\lambda^{(j)}|\), so that \(p_1+\cdots+p_m=n\) with \(p_j \geq 3\) for all \(j\), where \(|\sigma|\) denotes the length of (i.e., number of positions covered by) a tiling \(\sigma\). Considering cases based on the value of \(\ell\), we have that there are \[\sum\limits_{i=1}^{p_j-2}F_i=F_{p_j}-1=k_{p_j},\] possibilities for \(\lambda^{(j)}\). Then it is seen that \(\det(-1;k_1,\ldots,k_n)\) gives the cardinality of the set \(\mathcal{A}_n\) for \(n \geq 1\). Note that the associated sets \(\Omega_r\) for \(r \geq 3\) in this case would consist of the tilings of length \(r\) expressible as \(\alpha t_\ell\) as described, with \(\Omega_1\) and \(\Omega_2\) both taken to be empty. Also, we have that \(\det(1;k_1,\ldots,k_n)\) gives \(\sigma(\mathcal{A}_n)\) for each \(n \geq 1\), where the sign of \(\lambda=\lambda^{(1)}\cdots \lambda^{(m)}\) is \((-1)^{n-m}\). By similar reasoning, we have that \(\det(-1;k_2,\ldots,k_{n+1})\), \(\det(-1;k_3,\ldots,k_{n+2})\) and \(\det(-1;k_4,\ldots,k_{n+3})\) give \(|\mathcal{B}_n|\), \(|\mathcal{D}_n|\) and \(|\mathcal{E}_n|\), respectively, and changing \(-1\) to \(1\) in each case gives \(\sigma(\mathcal{B}_n)\), \(\sigma(\mathcal{D}_n)\) and \(\sigma(\mathcal{E}_n)\).
A similar interpretation can be given for the determinants above involving the sequence \(k_{2n+s}\) for a fixed \(s\). For example, \(\tau \in \mathcal{G}_n\) is expressible as \(\tau=\tau^{(1)}\cdots \tau^{(m)}\) for some \(m \geq 1\) wherein \(\tau^{(j)}=\beta t_{\ell}\) for some possibly empty square-and-domino tiling \(\beta\) and \(\ell \geq 4\). Let \(|\tau^{(j)}|:=2p_j\) for \(1 \leq j \leq m\) so that \(p_1+\cdots+p_m=n\) with \(p_j \geq 2\) for all \(j\). Further, upon considering cases on \(\ell\), there are \(\sum\limits_{i=1}^{2p_j-3}F_i=F_{2p_j-1}-1=k_{2p_j-1}\) possibilities for each \(\tau^{(j)}\). Hence, it is seen that \(\det(-1;k_1,\ldots,k_{2n-1})\) gives \(|\mathcal{G}_n|\) for \(n \geq 1\), with \(\det(1;k_1,\ldots,k_{2n-1})\) yielding \(\sigma(\mathcal{G}_n)\), where the sign of \(\tau=\tau^{(1)}\cdots \tau^{(m)}\) is given by \((-1)^{n-m}\). By similar reasoning, we have that \(\det(-1;k_2,\ldots,k_{2n})\), \(\det(-1;k_3,\ldots,k_{2n+1})\), \(\det(-1;k_4,\ldots,k_{2n+2})\) and \(\det(-1;k_5,\ldots,k_{2n+3})\) give \(|\mathcal{H}_n|\), \(|\mathcal{I}_n|\), \(|\mathcal{J}_n|\) and \(|\mathcal{K}_n|\), respectively, and replacing \(-1\) by \(1\) yields the determinant expression for the sum of the signs of the set in question in each case.
By finding the cardinality and/or the sum of the signs of the sets \(\mathcal{A}_n\) through \(\mathcal{K}_n\) above, one can provide combinatorial proofs as follows of Theorems 3.1 and 3.2.
Proof of Eq. (25). By the preceding, we must show \(|\mathcal{A}_n|=2^{n-3}\) for \(n \geq 3\). Given \(\lambda \in \mathcal{A}_n\), we first put a \(0\) over each position covered by the terminal \(t_i\). Then working from right to left, we put a run of \(1\)’s or \(0\)’s over the positions covered by each tile, alternating between runs of \(1\)’s and \(0\)’s and starting with \(1\)’s. Finally, we consider the resulting binary sequence from left to right and delete the last three \(0\)’s (recall that all \(t_i\) pieces have \(i\geq 3\) within members of \(\mathcal{A}_n\)) and let \(f(\lambda)\) be the sequence of length \(n-3\) that is obtained. One may verify that \(f\) is a bijection, whence \(|\mathcal{A}_n|=2^{n-3}\). To reverse \(f\), consider cases on whether a binary sequence \(\sigma\) of length \(n-3\) where \(n>3\) ends in \(0\) or \(1\), noting that \(f^{-1}(\sigma)\) ends in \(t_i\) with \(i>3\) if and only if \(\sigma\) ends in \(0\). Further, any runs of either \(0\) or \(1\) in \(\sigma\) of length at least three outside of a possible terminal run of \(0\)’s correspond to the positions of any non-terminal \(t_i\) pieces in \(f^{-1}(\sigma)\). ◻
Proof of Eq. (26). By the preceding, we show that \(\sigma(\mathcal{B}_n)\) is given by the right side of (26). Given \(\lambda \in \mathcal{B}_n\), identify, if it exists, the rightmost \(d\) or non-terminal \(t_2\) piece within \(\lambda\) and switch to the other option and let \(\lambda'\) denote the resulting member of \(\mathcal{B}_n\). Then \(\lambda \mapsto \lambda'\) is a sign-changing of involution on \(\mathcal{B}_n\) whose set of survivors \(\mathcal{B}_n'\) consists of all \(\pi\) expressible as \[\pi=s^{i_1}t_{j_1}s^{i_2}t_{j_2}\cdots s^{i_k}t_{j_k},\] for some \(k \geq 1\), where \(i_r\geq0\) for all \(r \in [k]\) and \(j_r \geq 3\) for \(1 \leq r \leq k-1\), with \(j_k \geq 2\). Note that \(k \leq \left\lfloor \dfrac{n+1}{3} \right\rfloor\), by the conditions on the \(i_r\) and \(j_r\). Further, for each \(k\), there are \[\binom{n-(3k-1)+2k-1}{2k-1}=\binom{n-k}{2k-1},\] possible \(\pi\) of the stated form, each having sign \((-1)^{n-k}\), as they may be viewed as weak compositions of \(n-3k+1\) with \(2k\) parts. Considering all possible \(1 \leq k \leq \left\lfloor \dfrac{n+1}{3} \right\rfloor\) implies \(\sigma(\mathcal{B}_n)=\sigma(\mathcal{B}_n')\) is given by the right side of (26), as desired. ◻
Proof of Eq. (27). We show that \(\sigma(\mathcal{D}_n)\) is given by the right side of (27). We first define the following three-part sign-changing involution on \(\mathcal{D}_n\):
It is understood that one applies the mapping (a) first and then (b) to the survivors of (a) and finally (c) to the survivors of (a) and (b). For \(1 \leq n \leq 5\), one may check directly that all members of \(\mathcal{D}_n\) are paired by (a)–(c) except for the following tilings: \(t_1\), \(st_1\), \(dt_1\) and \(dt_1st_1\), with all members of \(\mathcal{D}_4\) paired. This implies \(d_1=1\), \(d_2=-1\), \(d_3=1\), \(d_4=0\) and \(d_5=-1\), where \(d_n=\sigma(\mathcal{D}_n)\), which agrees with the right side of (27) in each case.
So assume \(n \geq 6\) and let \(\mathcal{D}_n'\) denote the set of survivors when the involution (a)–(c) is applied to \(\mathcal{D}_n\). One may verify that \(\mathcal{D}_n'\) for \(n \geq 6\) consists of all \(\rho \in \mathcal{D}_n\) expressible as either \(\rho=dt_1\rho'st_1\) or \(\rho=dt_1\rho'dt_1\), where \(\rho'\) is a tiling consisting of \(s\) or \(dt_1\) pieces (i.e., each \(d\) in \(\rho'\) must be directly followed by a \(t_1\)). Then \(\rho'\) having length \(n-5\) or \(n-6\) and consisting of \(s\) and \(dt_1\) pieces implies \[\label{sigDn'} \sigma(\mathcal{D}_n')=\sum\limits_{k\geq0}(-1)^{n-k}\left[\binom{n-5-2k}{k}+\binom{n-6-2k}{k}\right], \tag{36}\] where here \(\binom{m}{k}:=0\) if \(m<0\).
To show that \(\sigma(\mathcal{D}_n)\) is given by the right side of (27), we consider a further structure as follows. Let \(L\) denote the set of square-and-tromino tilings of length \(n-1\), where a tromino is a tile of length three. Define the sign of a member of \(L\) by \((-1)^{n-1-k}\), where \(k\) denotes the number of trominos. This implies \[\sigma(L)=\sum\limits_{k\geq0}(-1)^{n-1-k}\binom{n-1-2k}{k}.\]
Define an involution on \(L\) by replacing a terminal \(t\) with \(s^3\), and vice versa, where \(t\) denotes a tromino. The set \(L'\) of survivors of this involution consists of the members of \(L\) ending in exactly one or two squares, i.e., that end in \(-ts\) or \(-ts^2\). Considering the number of trominos in a member of \(L'\) implies \(\sigma(L')=\sigma(\mathcal{D}_n')\), by (36). Thus, we have \(\sigma(\mathcal{D}_n)=\sigma(\mathcal{D}_n')=\sigma(L')=\sigma(L)\), which implies the desired result. ◻
Proof of Eq. (28). We show that \(|\mathcal{D}_n|\) is given by the right side of (28). Let \(M\) denote the set of tri-colored square-and- tromino tilings of length \(n-1\) in which a square can come in the three colors red, white and green (denoted \(r\), \(w\) and \(g\)). Define the sign of a member of \(M\) by \((-1)^k\), where \(k\) denotes the number of trominos. Note that the right side of (28) is seen to give \(\sigma(M)\). Define an involution on \(M\) by identifying the rightmost tromino or occurrence of consecutive squares colored green, green, red (i.e., an occurrence of \(ggr\)) and switching to the other alternative. Note that the set \(M'\) of survivors of this involution consists of tilings that contain only squares (i.e., \(k=0\)) and in which there are no occurrences of \(ggr\). Since each member of \(M'\) has positive sign, we have \(\sigma(M)=|M'|\), and so to complete the proof of (28), it suffices to define a bijection between \(\mathcal{D}_n\) and \(M'\). To do so, let \(\lambda \in \mathcal{D}_n\) and consider making the following replacements of tiles within \(\lambda\): \(t_1\rightarrow w\), \(s \rightarrow r\), \(d \rightarrow gr\) and \(t_i\rightarrow g^{i-1}w\) for \(i \geq 2\). Note that \(\lambda\) ending in a \(t_i\) for some \(i \geq 1\) implies the final square in the sequence of squares so obtained is white, which we delete. Let \(f(\lambda)\) denote the resulting sequence of squares of length \(n-1\). One may verify \(f(\lambda) \in M'\) for all \(\lambda\) and that \(f\) yields the desired bijection between \(\mathcal{D}_n\) and \(M'\). ◻
Proof of Eq. (29). To show \(\sigma(\mathcal{E}_n)=0\) for \(n \geq 4\), we define a sign-changing involution on \(\mathcal{E}_n\) as follows. Consider the rightmost non-terminal \(s\) or \(d\), if it exists, and either mark it if unmarked or vice versa. Let \(\mathcal{E}_n'\) denote the subset of \(\mathcal{E}_n\) containing those tilings for which the preceding operation is not defined. We extend the involution to \(\mathcal{E}_n'\) as follows. Let \(\pi \in \mathcal{E}_n'\) and we consider cases based on the final piece of \(\pi\). If it is an \(s\) or \(d\), then \(n \geq 4\) implies there exists a penultimate tile \(x\), which must be a \(t_i\) for some \(i \geq 1\) as \(\pi \in \mathcal{E}_n'\). If \(i \geq 2\), then replace \(x\) with \(t_{i-1},~t_1\), and perform the reverse operation if \(i=1\). Note that \(n \geq 4\) implies \(\pi\) must contain at least three tiles altogether if \(x=t_1\). On the other hand, if the final piece of \(\pi\) is a \(t_i\) for some \(i \geq 1\), then perform the operation just described using the last two tiles of \(\pi\). This defines an involution on the entirety of \(\mathcal{E}_n'\) and completes the proof. ◻
Proof of Eq. (31). We seek to show that \(|\mathcal{H}_n|\) is given by the right side of (31). As previously mentioned, the sequence \(d(-1;k_2,\ldots,k_{2n})\) coincides with A003480\((n-1)\) for \(n \geq 2\). One of the combinatorial interpretations for A003480\((n)\) is that it enumerates the set of \((m+1)\)-color compositions of \(n\), which will be denoted here by \(\mathcal{R}_n\). We then proceed by showing that \(|\mathcal{H}_n|=|\mathcal{R}_{n-1}|\) for \(n \geq 2\) and that \(|\mathcal{R}_{n-1}|\) is given by the right side of (31). Recall now that an \((m+a)\)-color composition of the positive integer \(n\), where \(a\) is a fixed non-negative integer, is one in which each part of size \(i\) is colored in one of \(i+a\) ways. The color choice for a particular part is typically denoted by a subscript. Thus, an \((m+a)\)-color composition of \(n\) may be represented as a sequence \((i_1)_{j_1}, \ldots, (i_m)_{j_m}\) for some \(m \geq 1\) such that \(i_1+\cdots+i_m=n\), each part \(i_r\) is positive and \(1 \leq j_r \leq i_r+a\) for all \(r \in [m]\).
We first show \[|\mathcal{R}_n|=\sum\limits_{k=1}^n\binom{n-1}{k-1}p_{k+1},\] for all \(n \geq 1\). By a Pell tiling, we mean a square-and-domino tiling in which the squares come in two colors. Recall that there are \(p_{k+1}\) Pell tilings of length \(k\). Consider now a composition \(\lambda\) of \(n\) with \(k\) parts for some \(k \geq 1\), represented as \(\lambda=(i_1,\ldots,i_k)\), and a Pell tiling \(\rho\) of length \(k\). If the number \(r\), where \(1 \leq r \leq k\), is covered by a square (which comes in one of two colors) within \(\rho\), then let the subscript of the \(r\)-th part of \(\lambda\) be either \(1\) or \(i_r+1\), depending on the color of the square. On the other hand, if \(r\) and \(r+1\) for some \(1 \leq r \leq k-1\) are covered by a domino within \(\rho\), then replace the parts \(i_r, i_{r+1}\) with the single colored part \((i_r+i_{r+1})_{i_r+1}\). We then concatenate the resulting sequence of colored parts to obtain a member of \(\mathcal{R}_n\). Note that all members of \(\mathcal{R}_n\) arise uniquely in this manner as \(k\), \(\lambda\) and \(\rho\) vary, which implies the purported formula for \(|\mathcal{R}_n|\).
To show \(|\mathcal{H}_n|=|\mathcal{R}_{n-1}|\), we prove that both sets are equinumerous with a third set defined as follows. Let \(\mathcal{P}_n\) denote the set of marked, underlined \(m\)-color compositions of \(n\) wherein (i) a part of size \(>1\) may be underlined, (ii) the final part is always \(>1\) and underlined and (iii) a part of the form \(x_x\) for some \(x\geq 1\) may be marked (denoted by a prime) if not underlined and it directly follows an underlined part or occurs as the first part of a composition. Below, it is shown that \(\mathcal{H}_n\), \(\mathcal{P}_n\) and \(\mathcal{R}_{n-1}\) are equinumerous for all \(n \geq 2\), which implies the desired result.
Let \(\pi \in \mathcal{H}_n\) be decomposed as \(\pi=\pi^{(1)}\cdots \pi^{(r)}\) for some \(r \geq 1\), where each section \(\pi^{(j)}\) ends in a \(t_i\) for some \(i \geq 3\) and contains no other \(t_i\). That is, \(\pi^{(j)}\) can be expressed as either \[\label{keydec1} \pi^{(j)}=\rho_jt_{2\ell_j} \text{ or } \pi^{(j)}=\rho_jsd^{\ell_j-m_j}t_{2m_j-1}, \qquad 1 \leq j \leq r, \tag{37}\] where \(\ell_j \geq 2\) and \(\rho_j \in \mathcal{F}_{2k_j}\) with \(k_j \geq0\) for each \(j\) in either case and \(2 \leq m_j \leq \ell_j\) in the second case. Note that there are \(\ell_j\) possibilities for the tiles in \(\pi^{(j)}-\rho_j\) for a given \(\rho_j\).
We seek to transform each section \(\pi^{(j)}\) of \(\pi\) to a sequence of colored parts. Before doing so, we need to define a certain bijection between a class of tilings and \(m\)-color compositions. Let \(\mathcal{C}_p^*\) denote the set of \(m\)-color compositions of \(p\). Recall \(|\mathcal{C}_p^*|=F_{2p}\) for all \(p \geq 1\); see, e.g., [1]. We first construct a certain bijection \(f_p\) between \(\mathcal{F}_{2p-1}\) and \(\mathcal{C}_p^*\) for \(p \geq 1\), which will be needed in transforming the \(\pi^{(j)}\). Suppose \(\tau \in \mathcal{F}_{2p-1}\) is decomposed as \[\tau=d^{a_0}sd^{b_0}sd^{a_1}sd^{b_1}\cdots sd^{a_t}sd^{b_t}, \qquad a_i,b_i \geq 0,\] for some \(0 \leq t \leq p-1\). To obtain \(f_p(\tau)\), we replace the section \(sd^{a_i}sd^{b_i}\) with the (colored) part \((a_i+b_i+1)_{b_i+1}\) for \(1 \leq i \leq t\), and \(d^{a_0}sd^{b_0}\) with \((a_0+b_0+1)_{b_0+1}\), and then reverse the order of the parts. That is, \[f_p(\tau)=(a_t+b_t+1)_{b_t+1}\cdots(a_0+b_0+1)_{b_0+1} \in \mathcal{C}_p^*.\]
One may verify \(f_p\) is a bijection.
Let \(\mathcal{F}_{2p-1}'\) denote the subset of \(\mathcal{F}_{2p-1}\) consisting of those members for which \(a_t=0\) in the decomposition of \(\tau\) above. Note that \(|\mathcal{F}_{2p-1}'|=F_{2p-1}\); for a bijection \(\jmath\) between \(\mathcal{F}_{2p-1}'\) and \(\mathcal{F}_{2p-2}\), consider removing the \(s\) that directly precedes the (possibly empty) string \(d^{b_t}\). Further, we have that \(\mathcal{F}_{2p-1}'\) corresponds under \(f_p\) to the subset of \(\mathcal{C}_p^*\) whose members have first part \(x_x\) for some \(x \geq 1\). Now let \(\alpha \in \mathcal{F}_{2p}\) and we define a mapping \(g_p\) on \(\mathcal{F}_{2p}\) as follows. If \(\alpha=s\alpha'\), then let \(g_p(\alpha)=f_p(\alpha')\). If \(\alpha=d\alpha''\), then let \(g_p(\alpha)=f_p(\jmath^{-1}(\alpha''))\). In the latter case, we also mark the initial colored part of \(g_p(\alpha)\), which must be of the form \(x_x\). Then we have that \(g_p\) for \(p \geq 1\) provides a bijection between \(\mathcal{F}_{2p}\) and the set of marked members of \(\mathcal{C}_p^*\) wherein an initial part \(x_x\) may be marked. Further, if \(\alpha\) is the empty tiling of length zero, then we define \(g_0(\alpha)\) to be the empty \(m\)-color composition of zero with no parts.
Now assume \(\pi=\pi^{(1)}\cdots \pi^{(r)}\), where the \(\pi^{(j)}\) are as in (37). Then define \[h(\pi)=\prod_{j=1}^rg_{k_j}(\rho_j)\underline{(\ell_j)_{q_j}},\] where \(q_j=m_j-1\) if \(\pi^{(j)}\) ends in \(t_{2m_j-1}\) and \(q_j=\ell_j\) if \(\pi^{(j)}\) ends in \(t_{2\ell_j}\). Note that by the product of the various marked, underlined \(m\)-color subcompositions, we mean their concatenation in the natural order starting with \(j=1\). One may verify that \(h(\pi) \in \mathcal{P}_n\) for all \(\pi\) and that \(h\) provides the desired bijection between \(\mathcal{H}_n\) and \(\mathcal{P}_n\).
Let \(\pi \in \mathcal{P}_n\). We implement the following sequence of operations on \(\pi\). First reduce the final part of \(\pi\) by one, keeping its subscript the same. We then look for the rightmost non-terminal underlined part of \(\pi\), say \(\underline{a_b}\), if it exists. If \(\underline{a_b}\) is not followed by a marked part \(x_x'\) for some \(x \geq 1\), then replace \(\underline{a_b}\) with \((a-1)_b1_2\). If \(\underline{a_b}\) is followed by \(x_x'\), then replace \(\underline{a_b}\) with \((a-1)_b(x+1)_{x+2}\). We then look for the rightmost underlined part of those remaining and proceed just as before. Finally, if \(\pi\) starts with \(x_x'\) for some \(x\), then we replace it with \(x_{x+1}\). Let \(j(\pi)\) denote the resulting composition, which is seen to belong to \(\mathcal{R}_{n-1}\). For example, if \[\pi=2_2'1_14_2\underline{3_1}2_2'4_43_22_1\underline{4_3}5_53_2\underline{2_2} \in \mathcal{P}_{35},\] then \[j(\pi)=2_31_14_22_13_44_43_22_13_31_25_53_21_2 \in \mathcal{R}_{34}.\]
Note that parts which are neither underlined nor marked in \(\pi\) are unchanged by \(j(\pi)\).
To reverse \(j\), add \(1\) to the final part (keeping its subscript the same) and underline it. We then look for the rightmost part of the form \(x_{x+1}\). If \(x_{x+1}\) is initial, then replace it with \(x_x'\). Otherwise, we consider whether or not \(x>1\). If \(x>1\), and the predecessor of \(x_{x+1}\) is say \(c_d\), then we replace \(c_dx_{x+1}\) with \(\underline{(c+1)_d}(x-1)_{x-1}'\). If \(x=1\), then replace \(c_d1_2\) with \(\underline{(c+1)_d}\). We then look for the rightmost remaining part of the form \(x_{x+1}\), if it exists, and perform the appropriate operation as described above. Repeat until there are no longer any parts \(x_{x+1}\). One may verify that this procedure is the inverse of \(j\), and hence \(j\) is a bijection, as desired. ◻
Proof of Eq. (30). We seek to show \(|\mathcal{G}_n|\) is given by the right side of (30). Note first that \(\mathcal{G}_n\) corresponds to the subset of \(\mathcal{H}_n\) in which \(\ell_j\geq 3\) in the second form of \(\pi^{(j)}\) in (37) with \(3 \leq m_j \leq \ell_j\). We then modify the bijection \(h\) in the proof of (31) above by letting the subscript \(q_j\) be given by \(q_j=m_j-2\) if \(\pi^{(j)}\) ends in \(t_{2m_j-1}\) and \(q_j=\ell_j-1\) if \(\pi^{(j)}\) ends in \(t_{2\ell_j}\). This then implies \(|\mathcal{G}_n|=|\mathcal{P}_{n}'|\), where \(\mathcal{P}_n'\) denotes the subset of \(\mathcal{P}_n\) containing those compositions in which no part of the form \(y_y\) where \(y \geq 2\) is underlined.
Let \(\lambda=\lambda^{(1)}\cdots \lambda^{(s)} \in \mathcal{P}_n'\) for some \(s\geq 1\), where each section \(\lambda^{(\ell)}\) ends in an underlined part and contains no other underlined parts. Note that each \(\lambda^{(\ell)}\) is of the form \[\lambda^{(\ell)}=a(a_1)_{b_1}\cdots(a_{t-1})_{b_{t-1}}\underline{(a_t)_{b_t}}, \qquad t \geq 1,\] where \(1\leq b_i \leq a_i\) for \(1 \leq i \leq t-1\), with \(1 \leq b_t<a_t\), and \(a\) is either empty or consists of a single (marked) copy of \(x_x\) for some \(x\geq 1\). Then \(\lambda^{(\ell)}\) may be construed as a weak composition \(x_0x_1y_1\cdots x_ty_t\), by putting \(x_j=a_j-b_j\) and \(y_j=b_j\) for \(j \in [t]\), with \(x_0=0\) or \(x\) (depending on whether \(a\) is empty or equals \(x_x'\)). Note that \(x_j \geq0\) for each \(j \in [t-1]\), with \(x_t \geq 1\), whereas \(y_j\geq 1\) for all \(j \in [t]\).
Let \(\mathcal{Q}_n\) denote the set of marked weak compositions of \(n\) which may decomposed as \(\nu^{(1)}\cdots \nu^{(s)}\) for some \(s \geq 1\) such that each \(\nu^{(\ell)}\) is of the form \(x_0x_1y_1\cdots x_ty_t\) just described and whose final part is marked and no others. From the preceding, we then have \(|\mathcal{Q}_n|=|\mathcal{P}_n'|=|\mathcal{G}_n|\) for all \(n \geq 2\). Let \(\mathcal{T}_{n,k}\) denote the set of weak compositions \(d_1d_2\cdots d_{3k}\) of \(n\) in which \(d_{3i} \geq 1\) for each \(i \in [k]\), \(d_{3k-1}\geq 1\) and \(d_j \geq0\) for all other \(j\). Let \(\mathcal{T}_n=\cup_{k=1}^{n-1}\mathcal{T}_{n,k}\) and note \[|\mathcal{T}_n|=\sum\limits_{k=1}^{n-1}\binom{n+2k-2}{3k-1}.\]
To complete the proof, it suffices to define a bijection between \(\mathcal{T}_n\) and \(\mathcal{Q}_n\). Let \(d=d_1\cdots d_{3k} \in \mathcal{T}_{n,k}\) for some \(1 \leq k \leq n-1\) and consider the largest index \(i>1\), denoted by \(i_0\), such that \(d_{3i-2}>0\). Let us assume for now that \(i_0\) exists. We then replace the section \(d_{3i_0-2}d_{3i_0-1}\cdots d_{3k}\) of \(d\) with the sequence of parts \[(d_{3i_0-2}-1)d_{3i_0-1}d_{3i_0}d_{3i_0+2}d_{3i_0+3}\cdots d_{3k-1}d_{3k}',\] wherein the final part is marked (indicated by \('\)). We then repeat this operation on the subcomposition \(d_1\cdots d_{3i_0-3}\) of \(d\), where in addition, we now add \(1\) to the part directly preceding the part that is marked in the second replacement string (which cancels out the \(1\) that was taken away from \(d_{3i_0-2}\) in the first replacement). We repeat until no index \(i\) with \(d_{3i-2}>0\) and \(i>1\) exists.
At this point, the remaining section of \(d\), say \(d_1\cdots d_{3p}\) for some \(p \geq 1\) is such that \(d_4=\cdots=d_{3p-2}=0\). We then replace \(d_1\cdots d_{3p}\) with \[d_1d_2d_3d_5d_6\cdots d_{3p-4}d_{3p-3}(d_{3p-1}+1)d_{3p}'.\]
Let \(d'\) denote the resulting sequence of marked parts obtained by making all of the replacements as described above. If no \(i_0\) exists in \(d\), then let \[d'=d_1d_2d_3d_5d_6\cdots d_{3k-4}d_{3k-3}d_{3k-1}d_{3k}'.\]
Note that \(d' \in \mathcal{Q}_n\) in all cases since \(d_{3k-1}\geq 1\), by assumption. One may verify that the mapping \(d \mapsto d'\) is a bijection between \(\mathcal{T}_n\) and \(\mathcal{Q}_n\). It may be reversed by considering the position of the leftmost marked part within a member \(\beta\) of \(\mathcal{Q}_n\) and then using this part and those to its left to recreate the initial sequence of \(3y\) parts in the pre-image \(\delta\) of \(\beta\) under \(d\), where the leftmost marked part of \(\beta\) is the \((2y+1)\)-st part from the left. Then use the leftmost remaining marked part in \(\beta\) and those that remain to its left to recreate the next sequence of \(3z\) parts in \(\delta\) for some \(z \geq 1\) wherein the first part is positive. Continue in this manner, working from left to right, until no marked parts remain. ◻
Proof of Eq. (23). We show \(|\mathcal{I}_n|=P_{5n+2}\) for \(n \geq 1\). Let \(\mathcal{V}_n\) denote the set of tilings of length \(n\) using only dominos and trominos (termed Padovan tilings). Then we have \(|\mathcal{V}_n|=P_{n+3}\) and thus it suffices to show \(|\mathcal{I}_n|=|\mathcal{V}_{5n-1}|\) for all \(n \geq 1\). Note that \(\rho \in \mathcal{I}_n\) implies it may be decomposed as \(\rho=\rho^{(1)}\cdots \rho^{(r)}\) for some \(r \geq 1\) such that \(\rho^{(j)}\) for each \(j\) ends in a \(t_i\) with \(i \geq 2\) and contains no other \(t_i\). The \(\rho^{(j)}\) will be referred to as the units of \(\pi\). We wish to define a bijection \(f_n\) between \(\mathcal{V}_{5n-1}\) and \(\mathcal{I}_n\) for each \(n \geq 1\). To do so, we will construct a member of \(\mathcal{I}_n\) by interpreting a Padovan tiling as an encoding for the sequence of steps of a procedure which successively constructs the units of the member of \(\mathcal{I}_n\), starting with the last. Let \(f_1(d^2)=t_2\) and let \(f_2\) be given by \[d^3t\mapsto s^2t_2,\quad d^2td \mapsto (t_2)^2,\quad dtd^2 \mapsto st_3, \quad td^3 \mapsto t_4, \quad t^3 \mapsto dt_2.\]
Now assume \(n \geq 3\) and we define \(f_n\) recursively as follows. Let \(\pi \in \mathcal{V}_{5n-1}\). We consider several cases based on the possible ending sequences of \(\pi\). If \(\pi=\pi'td\), then let \(f_n(\pi)=f_{n-1}(\pi')t_2\). If \(\pi=\pi'\alpha\), where \(\alpha\) is one of \(td^2t\), \(dtdt\), \(t^2d^2\) or \(d^5\), then let \(f_n(\pi)=f_{n-2}(\pi')\alpha'\), where \(\alpha'\) is one of \(t_4\), \(st_3\), \(s^2t_2\) or \(dt_2\), respectively. If \(\pi=\pi'(d^2t^2)^j\) for some \(j \geq 1\) maximal, then let \(f_n(\pi)\) be obtained by adding \(4j\) to the subscript of the final \(t_i\) piece in \(f_{n-2j}(\pi')\).
Henceforth, assume \(\pi \in \mathcal{V}_{5n-1}\) does not have any of the endings already covered above. Then \(\pi=\pi'\beta\), where \(\beta \in \{d^3t,dtd^2,td^3,t^3,tdt^2,t^2dt,td^4\}\). We replace \(\beta\) with one of the endings \(\beta'\) of length four given respectively by \(\{s^2t_2, st_3,t_4,dt_2,d''t_3,d''st_2,t_5''\}\), where \(d''\) denotes the right half of a domino and \(t_5''\) the final four parts of a \(t_5\) piece. We wish to “grow” these endings \(\beta'\) so as to form the final unit of \(f_n(\pi)\), which will have length at least \(6\), with the terminal \(t_i\) piece having length at most \(5\). Note that, by the cases from the preceding paragraph, we have already mapped onto the subset of \(\mathcal{I}_n\) whose members have final unit length \(2\) or \(4\) or have terminal \(t_i\) with \(i \geq 6\).
Suppose \(\pi\in \mathcal{V}_{5n-1}\) has exactly \(p\) tiles altogether and consider the sequence \(\pi_1\cdots \pi_p\), where \(\pi_j=2\) or \(3\) depending on if the \((p-j+1)\)-st piece of \(\pi\) for \(1 \leq j \leq p\) is a \(d\) or a \(t\). For each \(r \geq 2\), let \(i_r\) denote the smallest \(i\) such that \(\pi_1+\cdots+\pi_i\geq 5r-1\). Let \(S_r:=\sum\limits_{j=1}^{i_r}\pi_j\) and let \(r'\) be the smallest \(r \geq 2\), if it exists, such that \(S_r=5r\). By the assumptions on \(\pi\), we have that either \(r' \geq 3\) or does not exist.
Note that \(S_2=9\) or \(11\) for each \(\pi\) currently under consideration, with the ending of \(f_n(\pi)\) being determined by the seven cases of \(\beta\) above. We then augment this ending by adding tiles to the beginning of it in several steps based on the relative values of consecutive \(S_r\) so as to create the final unit of \(f_n(\pi)\). Assume for now that \(r'\) exists. Let \(2 \leq r \leq r'-2\) and first suppose \(S_r=5r-1\). If \(S_{r+1}=5r+4\), then we add \(s^2\) to the beginning of the current suffix for \(f_n(\pi)\) if \(\pi_{i_r+1}=d\), \(\pi_{i_{r+1}}=t\) or add \(d\) to the beginning if \(\pi_{i_r+1}=t\), \(\pi_{i_{r+1}}=d\); note \(i_{r+1}=i_r+2\) in both cases. If \(S_{r+1}=5r+6\), then \(i_{r+1}=i_r+3\) and only \(\pi_{i_r+1}=\pi_{i_r+2}=d\), \(\pi_{i_{r+1}}=t\) is possible, in which case we prepend \(d''s\) to the current suffix for \(f_n(\pi)\). Now suppose \(S_r=5r+1\). If \(S_{r+1}=5r+4\), then \(i_{r+1}=i_r+1\) with \(\pi_{i_{r+1}}=t\), in which case we prepend \(sd'\) or \(st_5'\), whichever is appropriate, where \(d'\) or \(t_5'\) denotes the first part (covering a single number) of a \(d\) or \(t_5\). If \(S_{r+1}=5r+6\), then \(i_{r+1}=i_r+2\) with \(\pi_{i_r+1}=d\), \(\pi_{i_{r+1}}=t\), and we prepend \(d''d'\) or \(d''t_5'\) in this case, whichever is appropriate.
At this point, we have made \(r'-3\) additions as described (sequentially in the natural order, starting with \(r=2\)), beginning with \(\beta'\) above, so as to obtain a tiling of length \(2r'-2\). Note that this tiling contains only a single (terminal) \(t_i\) and might possibly start with \(d''\) or \(t_5''\). Suppose now \(r=r'-1\) so that \(S_{r+1}=5r+5\). If \(S_r=5r-1\), then either \(\pi_{i_r+1}=\pi_{i_r+2}=\pi_{i_{r+1}}=d\) or \(\pi_{i_r+1}=\pi_{i_{r+1}}=t\), and we prepend \(s^2\) or \(d\) to the existing tiling of length \(2r'-2\) in the respective cases. If \(S_r=5r+1\), then \(\pi_{i_r+1}=\pi_{i_{r+1}}=d\), and we prepend \(sd'\) (or possibly \(st_5'\) whenever \(r'=3\)).
In all cases, let \(\gamma\) denote the tiling of length \(2r'\geq 6\) that results after this last addition. Note that \(\gamma\) consists of a square-and-domino tiling followed by a single \(t_i\), where \(2~\!\leq~\!i\!~\!\leq 5\). Let \(\pi=\pi'\tau\), where \(\tau\) has length \(5r'\). We then let \(f_n(\pi)=f_{n-r'}(\pi')\gamma\), which covers all cases of \(\pi\) under current consideration where \(r'\) exists. If no \(r'\) exists, then let \(\nu\) denote the tiling of length \(2n\) that would result if none of the \(S_r\) for \(2 \leq r \leq n\) were divisible by \(5\). Note that \(\nu \in \mathcal{I}_n\) and contains a single unit, in which case we let \(f_n(\pi)=\nu\). This completes the definition of \(f_n(\pi)\) for all possible \(\pi\). One may verify that \(f_n\) is a bijection from \(\mathcal{V}_{5n-1}\) to \(\mathcal{I}_n\) by considering the various possibilities for endings of members in both sets. ◻
Proof of Eq. (32). We show \(\sigma(\mathcal{J}_n)\) is given by the right side of (32). Define a sign-reversing involution on \(\mathcal{J}_n\) by identifying the rightmost \(s\) covering an even number or non-terminal \(t_1\) and changing to the other option. Let \(\mathcal{J}_n'\) denote the set of survivors of this involution. Define a unit analogously as in the proof of (23), with the descriptors terminal and non-terminal being applied to units as they have been above for individual tiles. Suppose \(\alpha\) is a non-terminal unit of \(\pi \in \mathcal{J}_n'\). Then \(\alpha=d^a\beta\), where \(a \geq0\) and either \(\beta=t_{2b}\) with \(b \geq 1\) or \(\beta=sd^{b-c}t_{2c-1}\) with \(b \geq c \geq 2\). One may represent \(\alpha\) as a three-part weak composition \(u_1+u_2+u_3\) where \(u_3\geq 1\), which will be denoted by \(c_\alpha\). This can be realized by putting \(u_1=a, u_2=0, u_3=b\) if \(\beta=t_{2b}\) or \(u_1=a, u_2=b-c+1, u_3=c-1\) if \(\beta=sd^{b-c}t_{2c-1}\). A terminal unit \(\alpha\) has the same form as described above except \(c=1\) is possible as well. This has the effect of replacing the requirement that \(u_3\) be positive in \(c_\alpha\) with the weaker condition \(u_2+u_3 \geq 1\). Let \(\mathcal{J}_{n,k}'\) for \(1 \leq k \leq n\) denote the subset of \(\mathcal{J}_n'\) whose members contain \(k\) units. Upon putting together the various \(c_\alpha\), we see that members of \(\mathcal{J}_{n,k}'\) are synonymous with weak compositions \(x_1,\ldots,x_{3k}\) of \(n\) in which \(x_{3i}\geq 1\) for all \(i \in [k-1]\), with \(x_{3k-1}+x_{3k} \geq 1\).
To enumerate the members of \(\mathcal{J}_{n,k}'\), consider whether or not \(x_{3k-1}>0\). If \(x_{3k-1}>0\), then there are \(\binom{n+2k-1}{3k-1}\) possible members of \(\mathcal{J}_{n,k}'\), whereas if \(x_{3k-1}=0\), whence \(x_{3k}>0\), there are \(\binom{n+2k-2}{3k-2}\). Thus, we have \[\label{sigJn} \sigma(\mathcal{J}_n)=\sigma(\mathcal{J}_n')=\sum\limits_{k=1}^n(-1)^{n-k}\left[\binom{n+2k-1}{3k-1}+\binom{n+2k-2}{3k-2}\right], \qquad n \geq 1. \tag{38}\]
It is possible to show that the right sides of (32) and (38) coincide by making use of the recurrence for binomial coefficients. However, one can provide a more combinatorial proof by considering a further structure as follows. Let \(\mathcal{W}_{n,k}\) for \(0 \leq k \leq n+1\) denote the set of weak compositions \((\pi_1,\ldots,\pi_{3k+1})\) of \(n+1\) such that \(\pi_{3i}\geq 1\) for all \(i \in [k]\). Define the sign of a member of \(\mathcal{W}_{n,k}\) by \((-1)^{n-k}\). Then the right side of (32) is seen to give \(\sigma(\mathcal{W}_n)\), where \(\mathcal{W}_n=\cup_{k=0}^{n+1}\mathcal{W}_{n,k}\).
We now pair certain members of \(\mathcal{W}_{n,k}\) for \(0 \leq k \leq n\) with members of \(\mathcal{W}_{n,k+1}\). Consider \(\pi=(\pi_1,\ldots,\pi_{3k+4})\in \mathcal{W}_{n,k+1}\) for which \(\pi_{3k+2}=0\), \(\pi_{3k+3}=1\) and \(\pi_{3k+4}=0\). Upon deleting the part \(\pi_{3k+3}=1\), and adding \(1\) to \(\pi_{3k+1}\), one has that such \(\pi \in \mathcal{W}_{n,k+1}\) are paired with members of \(\mathcal{W}_{n,k}\) whose last part is positive for all \(0 \leq k \leq n\). Thus, it remains to count members of \(\mathcal{W}_{n,k}\) for \(1 \leq k \leq n\) where \(\pi_{3k+1}=0\), but where it is not the case that \(\pi_{3k-1}=0, \pi_{3k}=1\) holds as well. Note that if \(\pi_{3k}>1\), then it is seen that there are \[\binom{n+1-(k+1)+3k-1}{3k-1}=\binom{n+2k-1}{3k-1},\] possibilities. On the other hand, if \(\pi_{3k}=1\), then \(\pi_{3k-1}>0\) and there are \(\binom{n+2k-2}{3k-2}\) such members of \(\mathcal{W}_{n,k}\). Considering all possible \(k\), we have that \(\sigma(\mathcal{W}_n)\) is given by the right side of (38), which implies the desired formula for \(\sigma(\mathcal{J}_n)\). ◻
Proof of Eq. (33). We show \(\sigma(\mathcal{K}_n)=0\) for \(n \geq 4\). Recall that \(\mathcal{K}_n\) consists of tilings of length \(2n\) using \(s\), \(d\) and \(t_i\) for \(i \geq 1\) in which only pieces ending at even positions may be marked and \(t_i\) are always marked, as is the final piece. We first define an involution on \(\mathcal{K}_n\) in two steps as follows. Let \(\pi \in \mathcal{K}_n\) and suppose that an \(s\) or the right half of a \(d\) covers an even number strictly less than \(2n\). Consider the rightmost such piece within \(\pi\), and either mark it if unmarked or vice versa, which reverses the sign. The survivors of this involution have no non-terminal \(s\) or \(d\) ending in an even position.
Let \(\lambda \in \mathcal{K}_n\) denote such a survivor. We pair the various \(\lambda\) according to their endings as follows: \[\begin{aligned} &\alpha t_{2j} \longleftrightarrow \alpha t_{2j-2}d, \quad j\geq 2,\\ &\beta sd^at_{2b-1} \longleftrightarrow \beta sd^{a-1}t_{2b-1}d, \quad a,b \geq 1, \end{aligned}\] where \(\alpha\) or \(\beta\) may be empty. Now let \(S\) denote the subset of \(\mathcal{K}_n\) consisting of those tilings that have not been paired at this point. Note that members of \(\mathcal{K}_n\) ending in \(s\) or a \(t_i\) for \(i\) odd cannot have a \(t_j\) as the penultimate tile, as all \(t_j\) are marked and thus end in even positions. Hence, \(\pi \in S\) implies \(\pi\) ends in either (i) –\(t_2\), (ii) –\(st_{2b-1}\) for some \(b \geq 1\) or (iii) –\(sd^cs\) for some \(c \geq0\). Let \(S_1\), \(S_2\) and \(S_3\) denote the subsets of \(S\) whose members have the respective ending as described.
We shall show that \(\sigma(S_i)=0\) for \(i=1,2,3\) and all \(n \geq 4\). We decompose \(\pi \in S\) into units as \(\pi=\pi^{(1)}\cdots\pi^{(r)}\) for some \(r \in [n]\), where each \(\pi^{(j)}\) ends in a marked piece and contains no other marked pieces. Note that \(\pi\) has sign \((-1)^{n-r}\), by the definitions. The possibilities for a non-terminal unit within \(\pi\) are \(t_{2j}\) for some \(j \geq 1\) or \(sd^at_{2b-1}\) for \(a \geq0\), \(b\geq 1\), whereas a terminal unit can be one of \(t_2\), \(st_{2b-1}\) or \(sd^cs\) (which distinguish the subsets \(S_i\) of \(S\)). Note that a non-terminal unit whose sum of tile lengths is \(2p\) for some \(p \geq 1\) is one of \(p+1\) possible tile sequences–namely, \(t_{2p}\) or \(sd^{p-b}t_{2b-1}\) for \(1 \leq b \leq p\).
Let \(k\) denote half the sum of the lengths of all the non-terminal units of \(\pi\), where \(0 \leq k < n\). Then the sequence of non-terminal units may be viewed as a composition of \(k\) in which each part of size \(i\) comes in one of \(i+1\) colors, i.e., as an \((m+1)\)-color composition of \(k\). Let \(\mathcal{C}_{k}'\) denote the set of \((m+1)\)-color compositions of \(k\) and define the sign of \(\rho \in C_k'\) to be \((-1)^{k-\upsilon(\rho)}\), where \(\upsilon(\rho)\) is the number of parts of \(\rho\). In Lemma 4.1 below, it is shown bijectively that \(\sigma(\mathcal{C}_k')=0\) for all \(k \geq 3\). We apply this involution to the non-terminal units within a member of \(S\) for which \(k \geq 3\). Note \(n \geq 4\) implies \(k \geq 3\) for all members of \(S_1\), whence \(\sigma(S_1)=0\).
The unpaired members of \(S\) at this point are those in \(S_2\) or \(S_3\) for which \(k=0,1,2\). In \(S_2\), that would be the members (a) \(\pi=\alpha s t_{2n-5}\), where \(\alpha \in \{t_4,st_3,st_1t_2,t_2^2,sdt_1,t_2st_1,\\ (st_1)^2\},\) (b) \(\pi=\beta st_{2n-3}\), where \(\beta \in \{st_1,t_2\}\), or (c) \(\pi=st_{2n-1}\). Note that among these ten members of \(S_2\), exactly half have an even number of units, which we pair with the others in some way. Since all other members of \(S_2\) wherein \(k\geq 3\) have already been paired, we get \(\sigma(S_2)=0\). Likewise, we have \(\sigma(S_3)=0\), and hence \(\sigma(\mathcal{K}_n)=\sigma(S)=0\), as desired. ◻
Lemma 4.1. If \(k \geq 3\), then \(\sigma(\mathcal{C}_k')=0\).
Proof. Denote a colored part \(i\) within a member of \(\mathcal{C}_k'\) by \(i_j\), where \(j \in [i+1]\) denotes the color applied to \(i\). Consider, if it exists, the rightmost part \(i_j\) within \(\tau \in \mathcal{C}_k'\) such that either (i) \(i \geq 2\) with \(j \in [i]\) or (ii) \(i=j=1\), with this part not starting \(\tau\) if (ii). Let \(\tau^*\) be obtained from \(\tau\) by either replacing \(i_j\) with \((i-1)_j,1_1\) if (i) occurs or merging \(1_1\) with its predecessor (wherein \(1\) is added to the preceding part, but not its subscript) if (ii) occurs. The set of survivors of the sign-changing involution \(\tau \mapsto \tau^*\) consists of those compositions whose parts are all of the form \(i_{i+1}\) where \(i \geq 1\), except for possibly the first part, which could be \(1_1\) as well. In either case, we replace the last part \(\ell_{\ell+1}\) with \((\ell-1)_\ell,1_2\) if \(\ell \geq 2\) or merge the final two parts if \(\ell=1\). Note that \(k \geq 3\) implies that an initial part \(1_1\), if it occurs, is unaffected by either of these operations. ◻