Hessenberg–Toeplitz Matrix Determinants with Schröder and Fine Number Entries

Taras Goy

Faculty of Mathematics and Computer Science

Vasyl Stefanyk Precarpathian National University

Ivano-Frankivsk 76018

Ukraine

<EMAIL_ADDRESS>

Mark Shattuck

Department of Mathematics

University of Tennessee

Knoxville, TN 37996

USA

<EMAIL_ADDRESS>

###### Abstract

In this paper, we find determinant formulas of several Hessenberg–Toeplitz
matrices whose nonzero entries are derived from the small and large Schröder
and Fine number sequences. Algebraic proofs of these results can be given
which make use of Trudi’s formula and the generating function of the
associated sequence of determinants. We also provide direct arguments of our
results that utilize various counting techniques, among them sign-changing
involutions, on combinatorial structures related to classes of lattice paths
enumerated by the Schröder and Fine numbers. As a consequence of our results,
we obtain some new formulas for the Schröder and Catalan numbers as well as
for some additional sequences from the OEIS in terms of determinants of
certain Hessenberg–Toeplitz matrices.

##  1 Introduction

Let $S_{n}$ denote the $n$-th _large_ Schröder number given by

$S_{n}=\frac{1}{n}\sum_{k=1}^{n}2^{k}\binom{n}{k}\binom{n}{k-1},\qquad n\geq
1,$

with $S_{0}=1$. The _small_ Schöder number $s_{n}$ is defined as
$s_{n}=\frac{1}{2}S_{n}$ for $n\geq 1$, with $s_{0}=1$. The $n$-th Fine
number, denoted here by $t_{n}$, is given by

$t_{n}=3\sum_{k=1}^{\lfloor\frac{n+1}{2}\rfloor}\binom{2n-2k}{n-1}-\binom{2n}{n},\qquad
n\geq 1,$

with $t_{0}=0$. The first several terms of the sequences $s_{n}$ and $t_{n}$
for $n\geq 0$ are as follows:

$\\{s_{n}\\}_{n\geq
0}=\\{1,1,3,11,45,197,903,4279,20793,103049,518859,\ldots\\}$

and

$\\{t_{n}\\}_{n\geq 0}=\\{0,1,0,1,2,6,18,57,186,622,2120,\ldots\\}.$

We will make use of in our proofs the (ordinary) generating functions for
$S_{n}$, $s_{n}$ and $t_{n}$, which are given respectively by

$\displaystyle\sum_{n\geq 0}S_{n}x^{n}$
$\displaystyle=\frac{1-x-\sqrt{1-6x+x^{2}}}{2x},$ $\displaystyle\sum_{n\geq
0}s_{n}x^{n}$ $\displaystyle=\frac{1+x-\sqrt{1-6x+x^{2}}}{4x},$
$\displaystyle\sum_{n\geq 0}t_{n}x^{n}$
$\displaystyle=\frac{1+2x-\sqrt{1-4x}}{2(2+x)}.$

Let $C_{n}=\frac{1}{n+1}\binom{2n}{n}$ denote the $n$-th Catalan number (see
A000108 in [17]) and recall

$\sum_{n\geq 0}C_{n}x^{n}=\frac{1-\sqrt{1-4x}}{2x}.$

The preceding three sequences are closely aligned with $C_{n}$. For example,
we have for $n\geq 1$,

$S_{n}=\sum_{k=0}^{n}\binom{n+k}{2k}C_{k}\quad\text{ and }\quad
t_{n+1}=\frac{1}{2}\sum_{k=2}^{n}\frac{C_{k}}{(-2)^{n-k}}.$

Additional relations for the Fine numbers are given by $C_{n}=2t_{n+1}+t_{n}$
and

$t_{n+1}=C_{n}-\sum_{k=0}^{n-1}C_{k}t_{n-k}.$

The sequences $S_{n}$, $s_{n}$ and $t_{n}$ arise in various settings in
enumerative and algebraic combinatorics and give the cardinalities of some
important classes of first quadrant lattice paths [2, 3, 4, 5, 6, 16]. See
entries A006318, A001003 and A000957, respectively, in [17] for further
information. Here, we will be interested in some new combinatorial properties
of these numbers related to their occurrence in certain Hessenberg–Toeplitz
matrices.

Many relations for Schröder and Fine numbers have previously been found (see,
e.g., [6, 19, 20] and references contained therein), and determinants of
matrices with Schröder or Fine number entries and their generalizations have
attracted recent attention. A couple of basic results in this direction
involve Hankel determinants for the Schröder numbers, namely,
$\det\\!\big{(}S_{i+j}\big{)}_{i,j=0}^{n-1}=2^{\binom{n}{2}}$ and
$\det\\!\big{(}S_{i+j+1}\big{)}_{i,j=0}^{n-1}=2^{\binom{n+1}{2}}$. The
comparable formulas for the Fine numbers (see [6]) are given by
$\det\\!\big{(}t_{i+j+1}\big{)}_{i,j=0}^{n-1}=1$ and
$\det\\!\big{(}t_{i+j+2}\big{)}_{i,j=0}^{n-1}=1-n$. These results have been
generalized in different ways by considering various families of Catalan-like
sequences; see, e.g., [7, 14] and reference contained therein.

In [18], Qi presents negativity results for a class of Toeplitz–Hessenberg
determinants whose elements contain the products of the factorial and the
large Schröder numbers. By using Cramer’s rule together with a generating
function approach, Deutsch [5] obtained the following Fine–Catalan determinant
relation

$t_{n}=(-1)^{n-1}\left|\begin{array}[]{ccccccc}C_{0}&1&1&\cdots&0&0\\\
C_{1}&C_{0}&1&\cdots&0&0\\\ C_{2}&C_{1}&C_{0}&\cdots&0&0\\\
\cdots&\cdots&\cdots&\ddots&\cdots&\cdots\\\
C_{n-2}&C_{n-3}&C_{n-4}&\cdots&C_{0}&1\\\
C_{n-1}&C_{n-2}&C_{n-3}&\cdots&C_{1}&C_{0}\end{array}\right|,$ (1)

which was later rediscovered by the authors in [8] (formula (2.21) with
$a=-1$). In [8], the authors found determinants of several families of
Toeplitz–Hessenberg matrices having various subsequences of the Catalan
sequence for the nonzero entries. These determinant formulas may also be
rewritten equivalently as identities involving sums of products of Catalan
numbers and multinomial coefficients. Comparable results featuring
combinatorial arguments have been found for the generalized Fibonacci
(Horadam), tribonacci and tetranacci numbers in [9, 10, 11]. See also [1],
where further results for Horadam number permanents and determinants are
obtained using an algebraic approach.

The organization of this paper is as follows. In the next section, we find
formulas providing algebraic arguments of several Hessenberg–Toeplitz matrices
whose nonzero entries are given by $S_{n}$, $s_{n}$, $t_{n}$ or translates
thereof. As a consequence of our results, one obtains new determinant
expressions, and hence combinatorial interpretations, for $S_{n}$, $s_{n}$ and
$C_{n}$, as well as for several additional sequences occurring in [17].
Further, equivalent multi-sum versions of these determinant identities may be
obtained using Trudi’s formula (see Lemma 1 below). In the third section, we
provide combinatorial proofs of the preceding formulas upon making use of
various counting techniques such as direct enumeration, bijections between
equinumerous structures and sign-changing involutions. In doing so, we draw
upon the well-known combinatorial interpretations of $S_{n}$, $C_{n}$, $s_{n}$
and $t_{n}$ as enumerators of certain classes of first quadrant lattice paths.

##  2 Schröder and Fine number determinant formulas

A Hessenberg–Toeplitz matrix is one having the form

$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),$ (2)

where $a_{0}\neq 0$. The following multinomial expansion of $\det(A_{n})$ in
terms of a sum of products of the $a_{i}$ is known as _Trudi’s formula_ (see,
e.g., [13, Theorem 1]).

######  Lemma 1.

Let $n$ be a positive integer. Then

$\det(A_{n})=\sum_{\widetilde{v}=n}(-a_{0})^{n-|v|}{|v|\choose
v_{1},\ldots,v_{n}}a_{1}^{v_{1}}a_{2}^{v_{2}}\cdots a_{n}^{v_{n}},$ (3)

where

${|v|\choose v_{1},\ldots,v_{n}}=\frac{|v|!}{v_{1}!v_{2}!\cdots
v_{n}!},\quad\widetilde{v}=v_{1}+2v_{2}+\cdots+nv_{n},\quad|v|=v_{1}+v_{2}+\cdots+v_{n},\,\,v_{i}\geq
0.$

Equivalently, we have

$\det(A_{n})=\sum_{k=1}^{n}(-a_{0})^{n-k}\sum\limits_{\begin{smallmatrix}i_{1},\ldots,i_{k}\geq
1\\\ i_{1}+i_{2}+\cdots+i_{k}=n\end{smallmatrix}}a_{i_{1}}a_{i_{2}}\cdots
a_{i_{k}}.$

It is seen that the sum in (3) may be regarded as being over the set of
partitions of the positive integer $n$. The special case of Trudi when
$a_{0}=1$ is known as _Brioschi’s formula_ [15]. Here, we will focus on some
cases of $\det(A_{n})$ when $a_{0}=\pm 1$. For the sake of brevity, we denote
$\det\big{(}A_{n}(\pm 1;a_{1},a_{2},\ldots,a_{n})\big{)}$ by
$D_{\pm}(a_{1},a_{2},\ldots,a_{n})$.

There is the following inversion theorem involving $a_{i}$ and the
corresponding sequence of Hessenberg–Toeplitz determinants when $a_{0}=1$ (see
[12, Lemma 4]):

######  Lemma 2.

Let $(b_{n})_{n\geq 0}$ be defined by $b_{n}=\det(A_{n})$ for $n\geq 1$, where
$A_{n}$ is given by (2) with $a_{0}=b_{0}=1$. If $B_{n}$ denotes the
Hessenberg–Toeplitz matrix associated with $b_{0},\ldots,b_{n}$, then
$a_{n}=\det(B_{n})$ for $n\geq 1$.

We have the following determinant identity formulas involving the large and
small Schröder numbers.

######  Theorem 3.

We have

$\displaystyle D_{+}(S_{1},S_{2},\ldots,S_{n})$
$\displaystyle=(-1)^{n-1}S_{n-1},\qquad n\geq 2,$ (4) $\displaystyle
D_{-}(S_{1},S_{2},\ldots,S_{n})$ $\displaystyle=2\cdot A134425[n-1],$ (5)
$\displaystyle D_{+}(S_{0},S_{1},\ldots,S_{n-1})$
$\displaystyle=(-1)^{n-1}s_{n-1},$ (6) $\displaystyle
D_{-}(S_{0},S_{1},\ldots,S_{n-1})$ $\displaystyle=s_{n},\qquad$ (7)
$\displaystyle D_{+}(s_{1},s_{2},\ldots,s_{n})$
$\displaystyle=(-1)^{n-1}S_{n-1},$ (8) $\displaystyle
D_{-}(s_{1},s_{2},\ldots,s_{n})$ $\displaystyle=A225887[n-1],$ (9)
$\displaystyle D_{+}(s_{0},s_{1},\ldots,s_{n-1})$
$\displaystyle=(-1)^{n-1}A114710[n-1],$ (10) $\displaystyle
D_{-}(s_{0},s_{1},\ldots,s_{n-1})$ $\displaystyle=S_{n-1},\qquad$ (11)
$\displaystyle D_{+}(s_{2},s_{3},\ldots,s_{n+1})$
$\displaystyle=(-1)^{n-1}S_{n-1},\qquad n\geq 2,\qquad$ (12)

where all formulas hold for $n\geq 1$ unless stated otherwise.

Making use of Lemma 1 yields the following multinomial identities for the two
kinds of Schröder numbers.

######  Theorem 4.

We have

$\displaystyle\sum_{\widetilde{v}=n}(-1)^{|v|-1}{|v|\choose
v_{1},\ldots,v_{n}}S_{1}^{v_{1}}S_{2}^{v_{2}}\cdots S_{n}^{v_{n}}$
$\displaystyle=S_{n-1},\quad n\geq 2,$ (13)
$\displaystyle\sum_{\widetilde{s}=n}{|v|\choose
v_{1},\ldots,v_{n}}S_{1}^{v_{1}}S_{2}^{v_{2}}\cdots S_{n}^{v_{n}}$
$\displaystyle=2\cdot A134425[n-1],$ (14)
$\displaystyle\sum_{\widetilde{v}=n}(-1)^{|v|-1}{|v|\choose
v_{1},\ldots,v_{n}}S_{0}^{v_{1}}S_{1}^{v_{2}}\cdots S_{n-1}^{v_{n}}$
$\displaystyle=s_{n-1},$ (15) $\displaystyle\sum_{\widetilde{v}=n}{|v|\choose
v_{1},\ldots,v_{n}}S_{0}^{v_{1}}S_{1}^{v_{2}}\cdots S_{n-1}^{v_{n}}$
$\displaystyle=s_{n},$ (16)
$\displaystyle\sum_{\widetilde{v}=n}(-1)^{|v|-1}{|v|\choose
v_{1},\ldots,v_{n}}s_{1}^{v_{1}}s_{2}^{v_{2}}\cdots s_{n}^{v_{n}}$
$\displaystyle=S_{n-1},$ (17) $\displaystyle\sum_{\widetilde{s}=n}{|v|\choose
v_{1},\ldots,v_{n}}s_{1}^{v_{1}}s_{2}^{v_{2}}\cdots s_{n}^{v_{n}}$
$\displaystyle=A225887[n],$ (18)
$\displaystyle\sum_{\widetilde{v}=n}(-1)^{|v|-1}{|v|\choose
v_{1},\ldots,v_{n}}s_{0}^{v_{1}}s_{1}^{v_{2}}\cdots s_{n-1}^{v_{n}}$
$\displaystyle=A114710[n-1],$ (19)
$\displaystyle\sum_{\widetilde{v}=n}{|v|\choose
v_{1},\ldots,v_{n}}s_{0}^{v_{1}}s_{1}^{v_{2}}\cdots s_{n-1}^{v_{n}}$
$\displaystyle=S_{n-1},$ (20)
$\displaystyle\sum_{\widetilde{v}=n}(-1)^{|v|-1}{|v|\choose
v_{1},\ldots,v_{n}}s_{2}^{v_{1}}s_{3}^{v_{2}}\cdots s_{n+1}^{v_{n}}$
$\displaystyle=S_{n-1},\quad n\geq 2,$ (21)

where all formulas hold for $n\geq 1$ unless stated otherwise.

The identities in Theorems 3 and 4 are seen to be equivalent by (3), so we
need only prove the former.

###### Proof.

Let $f(x)=\sum_{n\geq 1}\det(A_{n})x^{n}$, where $A_{n}$ is given by (2). Then
rewriting (3) in terms of generating functions implies

$f(x)=\sum_{n\geq 1}(-a_{0}x)^{n}\sum_{\widetilde{v}=n}{|v|\choose
v_{1},\ldots,v_{n}}\left(-\frac{a_{1}}{a_{0}}\right)^{v_{1}}\cdots\left(-\frac{a_{n}}{a_{0}}\right)^{v_{n}}=\frac{g(x)}{1-g(x)},$

where $g(x)=\sum_{i\geq 1}(-a_{0})^{i-1}a_{i}x^{i}$.

We consider several cases on $a_{i}$. First let $a_{i}=S_{i}$ for $i\geq 1$.
Then

$g(x)=\sum_{i\geq
1}(-a_{0})^{i-1}S_{i}x^{i}=\frac{1+3a_{0}x-\sqrt{1+6a_{0}x+a_{0}^{2}x^{2}}}{2a_{0}^{2}x}.$

If $a_{0}=1$, then

$\displaystyle f(x)$
$\displaystyle=\frac{g(x)}{1-g(x)}=\frac{1+3x-\sqrt{1+6x+x^{2}}}{-1-x+\sqrt{1+6x+x^{2}}}=2x-\frac{1}{2}\left(1+3x-\sqrt{1+6x+x^{2}}\right)$
$\displaystyle=2x+\sum_{n\geq 2}(-1)^{n-1}S_{n-1}x^{n},$

which implies (4). If $a_{0}=-1$, then

$\displaystyle f(x)$
$\displaystyle=\frac{g(x)}{1-g(x)}=\frac{1-3x-\sqrt{1-6x+x^{2}}}{-1+5x+\sqrt{1-6x+x^{2}}}=\frac{4x}{1-7x+\sqrt{1-6x+x^{2}}}$
$\displaystyle=\sum_{n\geq 1}2\cdot A134425[n-1]x^{n},$

which implies (5), upon recalling the formula $\sum_{n\geq
0}A134425[n]x^{n}=\frac{2}{1-7x+\sqrt{1-6x+x^{2}}}$ (see OEIS article).

Now let $a_{i}=S_{i-1}$ for $i\geq 1$. In this case, we have

$g(x)=\sum_{i\geq
1}(-a_{0})^{i-1}S_{i-1}x^{i}=\frac{-1-a_{0}x+\sqrt{1+6a_{0}x+a_{0}^{2}x^{2}}}{2a_{0}}.$

If $a_{0}=1$, then

$f(x)=\frac{-1-x+\sqrt{1+6x+x^{2}}}{3+x-\sqrt{1+6x+x^{2}}}=\frac{-1+x+\sqrt{1+6x+x^{2}}}{4}=\sum_{n\geq
1}(-1)^{n-1}s_{n-1}x^{n},$

which gives (6), whereas if $a_{0}=-1$, then

$f(x)=\frac{1-x-\sqrt{1-6x+x^{2}}}{1+x+\sqrt{1-6x+x^{2}}}=\frac{1-3x-\sqrt{1-6x+x^{2}}}{4x}=\sum_{n\geq
1}s_{n}x^{n},$

which gives (7).

Similar proofs may be given for (8)–(11). Alternatively, formulas (8) and (11)
follow from (7) and (6), respectively, upon applying Lemma 2 since

$\displaystyle D_{+}(s_{1},\ldots,s_{n})=(-1)^{n-1}S_{n-1}\text{ if and only
if }$ $\displaystyle
D_{-}(S_{0},\ldots,S_{n-1})=D_{+}(S_{0},-S_{1},\ldots,(-1)^{n-1}S_{n-1})=s_{n}$

and

$\displaystyle D_{+}(S_{0},\ldots,S_{n-1})=(-1)^{n-1}s_{n-1}\text{ if and only
if }$ $\displaystyle
D_{-}(s_{0},\ldots,s_{n-1})=D_{+}(s_{0},-s_{1},\ldots,(-1)^{n-1}s_{n-1})=S_{n-1}.$

Finally, to show (12), let $a_{i}=s_{i+1}$ for $i\geq 1$ and $a_{0}=1$ to get

$g(x)=\sum_{i\geq
1}(-1)^{i-1}s_{i+1}x^{i}=\frac{-1-3x+4x^{2}+\sqrt{1+6x+x^{2}}}{4x^{2}}.$

Thus,

$\displaystyle f(x)$
$\displaystyle=\frac{g(x)}{1-g(x)}=\frac{-1-3x+4x^{2}+\sqrt{1+6x+x^{2}}}{1+3x-\sqrt{1+6x+x^{2}}}$
$\displaystyle=3x+\frac{1}{2}\left(-1-3x+\sqrt{1+6x+x^{2}}\right)=3x+\sum_{n\geq
2}(-1)^{n-1}S_{n-1}x^{n},$

which completes the proof. ∎

We have the following Fine number determinant formulas.

######  Theorem 5.

We have

$\displaystyle D_{+}(t_{1},t_{2},\ldots,t_{n})$ $\displaystyle=u_{n},$ (22)
$\displaystyle D_{-}(t_{1},t_{2},\ldots,t_{n})$ $\displaystyle=C_{n-1},$ (23)
$\displaystyle D_{+}(t_{2},t_{3},\ldots,t_{n+1})$
$\displaystyle=(-1)^{n-1}C_{n-1},\quad n\geq 2,$ (24) $\displaystyle
D_{-}(t_{2},t_{3},\ldots,t_{n+1})$ $\displaystyle=A137398[n],$ (25)
$\displaystyle D_{+}(t_{3},t_{4},\ldots,t_{n+2})$
$\displaystyle=(-1)^{n-1}A030238[n-1],$ (26) $\displaystyle
D_{+}(t_{4},t_{5},\ldots,t_{n+3})$ $\displaystyle=(-1)^{n-1}C_{n-1},\qquad
n\geq 3,$ (27)

where all formulas hold for $n\geq 1$ unless stated otherwise and $u_{n}$
denotes the sequence defined recursively by
$u_{n}=u_{n-1}+\sum_{i=1}^{n-2}(-1)^{i+1}C_{i}u_{n-i-1}$ if $n\geq 3$ with
$u_{1}=u_{2}=1$.

###### Proof.

Proofs comparable to those given for (4)–(12) may also be given for (22)–(27).
We illustrate using formula (27). First note that

$\sum_{n\geq 1}t_{n+3}x^{n}=\sum_{n\geq
3}t_{n+1}x^{n-2}=\frac{1}{x^{2}}\left(\frac{2}{1+2x+\sqrt{1-4x}}-1-x^{2}\right),$

and hence we have

$g(x)=\sum_{n\geq
1}(-1)^{n-1}t_{n+3}x^{n}=-\frac{1}{x^{2}}\left(\frac{1+2x-x^{2}+2x^{3}-(1+x^{2})\sqrt{1+4x}}{1-2x+\sqrt{1+4x}}\right).$

This gives

$\displaystyle\sum_{n\geq 3}\det(A_{n})x^{n}$
$\displaystyle=\frac{g(x)}{1-g(x)}-\det(A_{1})x-\det(A_{2})x^{2}$
$\displaystyle=\frac{-1-2x+x^{2}-2x^{3}+(1+x^{2})\sqrt{1+4x}}{1+2x-\sqrt{1+4x}}-2x+2x^{2}$
$\displaystyle=\frac{-1-4x-x^{2}+2x^{3}+(1+2x-x^{2})\sqrt{1+4x}}{1+2x-\sqrt{1+4x}}$
$\displaystyle=\frac{\left(-1-4x-x^{2}+2x^{3}+(1+2x-x^{2})\sqrt{1+4x}\right)\left(1+2x+\sqrt{1+4x}\right)}{4x^{2}}$
$\displaystyle=\frac{-2x^{2}\left(1+2x-2x^{2}-\sqrt{1+4x}\right)}{4x^{2}}=x\left(\frac{1-\sqrt{1+4x}}{-2x}-1+x\right)$
$\displaystyle=x\sum_{n\geq 2}C_{n}(-x)^{n}=\sum_{n\geq
3}(-1)^{n-1}C_{n-1}x^{n},$

which implies (27). ∎

##  3 Combinatorial proofs

In this section, we provide combinatorial proofs of formulas (4)–(12) and
(22)–(27). Let us first recall combinatorial interpretations of the sequences
$S_{n}$, $s_{n}$ and $t_{n}$ which we will make use of in our proofs and
define some related terms. Let $\mathcal{P}_{n}$ denote the set of lattice
paths (called _Schröder_ paths) from the origin to the point $(2n,0)$ that
never go below the $x$-axis using $u=(1,1)$, $d=(1,-1)$ and $h=(2,0)$ steps.
Then $S_{n}=|\mathcal{P}_{n}|$ for all $n\geq 0$, where $\mathcal{P}_{0}$ is
understood to consist of the empty path of length zero. Half the horizontal
distance traversed by a Schröder path $\lambda$ will be referred to here as
the _length_ of $\lambda$ and is denoted by $|\lambda|$. Note that $|\lambda|$
equals the sum of numbers of $u$ and $h$ steps in $\lambda$. (We remark that
the term _semi-length_ is often used in the literature, instead of length, for
the quantity indicated, though we prefer the latter due to brevity.) An $h$
step connecting two points with $y$-coordinate $\ell\geq 0$ is said to be of
_height_ $\ell$. A _low_ $h$ step will refer to an $h$ step of height $0$. The
subset of $\mathcal{P}_{n}$ whose members contain no low $h$ steps will be
denoted by $\mathcal{Q}_{n}$, with its members referred to as _restricted_
Schröder paths. Then it is well-known that $s_{n}=|\mathcal{Q}_{n}|$ for
$n\geq 0$. Hence, since $S_{n}=2s_{n}$ if $n\geq 1$, we have that exactly half
the members of $\mathcal{P}_{n}$ are restricted.

Let $\mathcal{D}_{n}$ denote the subset of $\mathcal{P}_{n}$ whose members
contain no $h$ steps. Members of $\mathcal{D}_{n}$ are referred to as _Dyck_
paths, with $|\mathcal{D}_{n}|=C_{n}$ for $n\geq 0$. A member of
$\mathcal{D}_{n}$ is said to have a _peak_ of height $i$ where $1\leq i\leq n$
if there exists a $u$ directly followed by a $d$ in which the $u$ has ending
height $i$. Let $\mathcal{E}_{n}$ denote the subset of $\mathcal{D}_{n}$ whose
members contain no peaks of height $1$. Then it is well-known that
$t_{n}=\mathcal{E}_{n-1}$ for $n\geq 1$, with $t_{0}=0$.

By a _return_ within a member of $\mathcal{P}_{n}$, we mean an $h$ or $u$ step
that terminates on the $x$-axis. A _terminal_ return is one that has endpoint
$(2n,0)$, with all other returns being referred to as _non-terminal_. By a
_unit_ within $\lambda\in\mathcal{P}_{n}$, we mean a subpath of $\lambda$
occurring between two adjacent returns or prior to the first return. Note that
a low $h$ step comprises its own unit with all other units of the form
$u\sigma d$ for some possibly empty Schröder path $\sigma$. Within members of
$\mathcal{E}_{n}$, all units must have length at least two, whereas members of
$\mathcal{Q}_{n}$ can also contain units of the form $ud$, but not $h$.
Finally, a member of $\mathcal{P}_{n}$ having no non-terminal returns is said
to be _primitive_. A primitive member $\lambda\in\mathcal{P}_{n}$ for $n\geq
2$ is necessarily of the form $\lambda=u\sigma d$, where
$\sigma\in\mathcal{P}_{n-1}$, and hence belongs to $\mathcal{Q}_{n}$.

We compute the determinant of an $n\times n$ Hessenberg–Toeplitz matrix using
the definition of a determinant as a signed sum over the set of permutations
$\sigma$ of $[n]$. In doing so, one need only consider those $\sigma$ whose
cycles when expressed disjointly each comprise a set of consecutive integers.
Such $\sigma$ are clearly in one-to-one correspondence with the compositions
of $n$, upon identifying the various cycle lengths with parts of a
composition. This implies that the determinant of a matrix $A_{n}$ of the form
(2) may be regarded as a weighted sum over the set of compositions of $n$. If
$a_{0}=1$ in this sum, then each part of size $r\geq 1$ has (signed) weight
given by $(-1)^{r-1}a_{r}$ (regardless of its position) and the weight of a
composition is the product of the weights of its constituent parts. One can
then define the sign of a composition as $(-1)^{n-m}$, where $m$ denotes the
number of its parts. On the other hand, when $a_{0}=-1$, every part of size
$r$ now contributes $a_{r}$ towards the weight of the composition. Thus,
assuming $a_{i}\geq 0$ for $i\geq 1$, each term in the determinant sum for
$A_{n}$ is non-negative in this case. Note that computing $\det(A_{n})$ where
$a_{0}=-1$ is equivalent to finding the permanent of the matrix obtained from
$A_{n}$ by replacing $a_{0}=-1$ with $a_{0}=1$.

We now provide combinatorial proofs of the formulas from Theorems 3 and 5
above.

Proofs of (4), (5), (8) and (9):

Let $\mathcal{A}_{n}$ denote the set of marked Schröder paths of length $n$ in
which returns to the $x$-axis may be marked and whose final return is always
marked. Define the sign of $\lambda\in\mathcal{A}_{n}$ by
$(-1)^{n-\mu(\lambda)}$, where $\mu(\lambda)$ denotes the number of marked
returns of $\lambda$. Let $\mathcal{A}_{n}^{\prime}\subseteq\mathcal{A}_{n}$
consist of those members of $\mathcal{A}_{n}$ in which there are no low $h$
steps (marked or unmarked). Then $D_{+}(S_{1},\ldots,S_{n})$ and
$D_{+}(s_{1},\ldots,s_{n})$ give the sum of the signs of all members of
$\mathcal{A}_{n}$ and $\mathcal{A}_{n}^{\prime}$, respectively. To see this,
first suppose $\tau$ is a member of $\mathcal{A}_{n}$ or
$\mathcal{A}_{n}^{\prime}$ and is derived from the (weighted) composition
$\sigma$ in either determinant expansion. That is, $\tau$ is obtained from
$\sigma$ by overlaying a member of $\mathcal{P}_{r}$ or $\mathcal{Q}_{r}$ on
each part of $\sigma$ of size $r$ for every $r$, marking the final return of
each path and finally concatenating the paths in the same order as the parts
of $\sigma$. Then the sequence of part sizes of $\sigma$ corresponds to the
sequence of lengths of the subpaths occurring between adjacent marked returns
of $\tau$ (or prior to the first marked return), and, in particular, the
number of parts of $\sigma$ equals the number of marked returns of $\tau$.
Thus, the sign of $\sigma$ in the determinant expansion corresponds to
$n-\mu(\tau)$, and considering all $\tau$ associated with each $\sigma$
implies $D_{+}(S_{1},\ldots,S_{n})$ and $D_{+}(s_{1},\ldots,s_{n})$ give the
sum of the signs of the members of $\mathcal{A}_{n}$ and
$\mathcal{A}_{n}^{\prime}$, respectively, as claimed.

We define a sign-changing involution on $\mathcal{A}_{n}$ by identifying the
leftmost non-terminal return and either marking it or removing the marking
from it. The set of survivors of this involution consists of the _primitive_
members of $\mathcal{A}_{n}$. If $n\geq 2$, then there are $S_{n-1}$ primitive
members of $\mathcal{A}_{n}$, each of sign $(-1)^{n-1}$, which implies (4).
Since the survivors of the involution all belong to
$\mathcal{A}_{n}^{\prime}$, this establishes (8) as well.

On the other hand, it is seen from the preceding that
$D_{-}(S_{1},\ldots,S_{n})$ and $D_{-}(s_{1},\ldots,s_{n})$ give the
cardinalities of the sets $\mathcal{A}_{n}$ and $\mathcal{A}_{n}^{\prime}$,
respectively, since when $a_{0}=-1$ the sign of $\sigma$ is cancelled out by
the product of the superdiagonal $-1$ factors in the term corresponding to
$\sigma$ in the determinant expansion. We first show (9). Let
$\mathcal{P}_{n}^{*}$ denote the set of colored members of $\mathcal{P}_{n}$
wherein each low $h$ step is colored in one of three ways. Recall one of the
combinatorial interpretations of $A225887[n]$ is that it gives the cardinality
of $\mathcal{P}_{n}^{*}$ for $n\geq 0$. Thus, to complete the proof of (9), it
suffices to define a bijection
$\phi:\mathcal{P}_{n-1}^{*}\rightarrow\mathcal{A}_{n}^{\prime}$. Let $h_{a}$,
$h_{b}$, $h_{c}$ denote the three kinds of colored low $h$ steps within
$\lambda\in\mathcal{P}_{n-1}^{*}$. We decompose $\lambda$ as
$\lambda=\lambda^{(1)}\cdots\lambda^{(r)}$ for some $r\geq 1$, where each
subpath $\lambda^{(i)}$ for $1\leq i\leq r-1$ ends in either $h_{a}$ or
$h_{b}$, with all other low $h$ steps in $\lambda$ (if there are any) equal to
$h_{c}$, and $\lambda^{(r)}$ is possibly empty. Note that if $\lambda$
contains no $h_{a}$ or $h_{b}$ steps, then we take $r=1$ and
$\lambda=\lambda^{(1)}$; further, if $\lambda$ ends in $h_{a}$ or $h_{b}$,
then $r\geq 2$ with $\lambda^{(r)}$ understood to be empty in this case. If
$1\leq i\leq r-1$ and $\lambda^{(i)}$ ends in $h_{a}$ with
$\lambda^{(i)}=\alpha_{i}h_{a}$, where $\alpha_{i}$ is possibly empty, then
let $\overline{\lambda}^{(i)}=u\alpha_{i}d$, where the final $d$ is marked
(i.e., the return to the $x$-axis associated with this $d$ is marked). If
$\lambda^{(i)}=\beta_{i}h_{b}$, then let
$\overline{\lambda}^{(i)}=u\beta_{i}d$, where the final $d$ is unmarked.
Finally, let $\overline{\lambda}^{(r)}=u\lambda^{(r)}d$, where the final $d$
is marked. Define
$\phi(\lambda)=\overline{\lambda}^{(1)}\cdots\overline{\lambda}^{(r)}$ as the
concatenation of the lattice paths $\overline{\lambda}^{(i)}$. Note that
$\phi$ can be reversed, and hence is bijective, as desired, upon considering
the positions of the returns and whether or not they are marked. Further, it
is seen that the number of $h_{c}$ steps within $\lambda$ equals the number of
$h$ steps of height $1$ within $\phi(\lambda)$ for all $\lambda$.

We now show (5). Let $\mathcal{\widetilde{P}}_{n}$ denote the set derived from
members of $\mathcal{P}_{n}$ by stipulating that the low $h$ steps come in one
of four kinds, denoted by $h^{(i)}$ for $1\leq i\leq 4$. Recall that
$A134425[n]$ gives $|\mathcal{\widetilde{P}}_{n}|$ for $n\geq 0$, so for (5),
we need to prove $|\mathcal{A}_{n}|=2|\mathcal{\widetilde{P}}_{n-1}|$ for
$n\geq 1$. We proceed inductively, noting that the $n=1$ case of the equality
is clear. Let $n\geq 2$ and we consider the following cases on members
$\lambda\in\mathcal{A}_{n}$: (i) $\lambda=\lambda^{\prime}h$, (ii)
$\lambda=\lambda^{\prime}\alpha$, where $\alpha\neq h$ is a unit and
$\lambda^{\prime}$ is nonempty, with the final return of $\lambda^{\prime}$
marked, or (iii) $\lambda=\lambda^{\prime}\beta$, where $\beta\neq h$ is a
unit and either $\lambda^{\prime}=\varnothing$ or
$\lambda^{\prime}\neq\varnothing$ with the final return of $\lambda^{\prime}$
not marked. We partition $\rho\in\mathcal{\widetilde{P}}_{n-1}$ as follows:
(I) $\rho$ ends in $h^{(1)}$ or $h^{(2)}$, (II) $\rho=\rho^{\prime}\alpha$,
where $\alpha\neq h^{(i)}$ for any $i$ is a unit and $\rho^{\prime}$ is
possibly empty, or (III) $\rho$ ends in $h^{(3)}$ or $h^{(4)}$.

We now demonstrate for each of (i)–(iii) that there are twice as many members
$\lambda\in\mathcal{A}_{n}$ as there are
$\rho\in\mathcal{\widetilde{P}}_{n-1}$ in the corresponding case (I)–(III).
Upon considering whether or not the final return in $\lambda^{\prime}$ is
marked, it is seen by the induction hypothesis that there are twice as many
$\lambda\in\mathcal{A}_{n}$ for which (i) applies as there are
$\rho\in\mathcal{\widetilde{P}}_{n-1}$ for which (I) applies. The same holds
true of (ii) and (II) as $\lambda^{\prime}$ in (ii) has length one greater
than that of $\rho^{\prime}$ in (II), with $\alpha$ the same in both cases. To
show that the same holds for cases (iii) and (III) above, observe first that
the number of possible $\rho\in\mathcal{\widetilde{P}}_{n-1}$ in (III) is
given by $2|\mathcal{\widetilde{P}}_{n-2}|$. Thus, to complete the proof of
(5), it is enough to prove that there are $2|\mathcal{A}_{n-1}|$ possible
$\lambda\in\mathcal{A}_{n}$ in (iii).

Let $\lambda=\lambda^{\prime}\beta\in\mathcal{A}_{n}$, where $\beta\neq h$ is
a unit and $\lambda^{\prime}$ does not have a marked final return. If
$\lambda^{\prime}=\varnothing$, i.e., $\lambda$ is primitive, then write
$\beta=u\beta^{\prime}d$ and regard $\beta^{\prime}$ as a member of
$\mathcal{A}_{n-1}$ in which only the final return is marked. Otherwise,
consider cases based on the length $\ell$ of $\beta$, where $1\leq\ell\leq
n-1$. If $\ell=1$, i.e., $\beta=ud$, then regard $\lambda^{\prime}$ as a
member of $\mathcal{A}_{n-1}$ by marking its last return. If $\ell\geq 2$,
then let $\beta=u\beta^{\prime}d$, where $\beta^{\prime}$ is nonempty. Then
form the lattice path $\sigma=\lambda^{\prime}\beta^{\prime}$ of length $n-1$,
wherein the last return of $\lambda^{\prime}$ and of $\beta^{\prime}$ are now
both marked (here, it is understood that all other returns of
$\lambda^{\prime}$ remain of the same status regarding whether or not they are
marked and that all non-terminal returns of $\beta^{\prime}$, if any, are
unmarked). Note that $\sigma\in\mathcal{A}_{n-1}$ with $\sigma$ containing at
least two marked returns. It is seen then that each member of
$\mathcal{A}_{n-1}$ arises exactly twice when one performs the operations
described above on the various members of $\mathcal{A}_{n}$ for which (iii)
applies, upon considering whether or not a member of $\mathcal{A}_{n-1}$
contains two or more marked returns, and if it does, additionally taking into
account the position of the rightmost non-terminal marked return. This
establishes the desired equality
$|\mathcal{A}_{n}|=2|\mathcal{\widetilde{P}}_{n-1}|$ for all $n\geq 1$, which
completes the proof of (5). ∎

Proofs of (6), (7), (10) and (11):

Let $\mathcal{A}_{n}$ be as in the previous proof and let
$\mathcal{B}_{n}\subseteq\mathcal{A}_{n}$ consist of those members in which
all marked returns (including the final return) correspond to low $h$ steps.
Let $\mathcal{B}_{n}^{\prime}\subseteq\mathcal{B}_{n}$ consist of those
members in which no low $h$ is unmarked. Define the sign of
$\lambda\in\mathcal{B}_{n}$ by $(-1)^{n-\mu(\lambda)}$, where $\mu(\lambda)$
denotes the number of marked low $h$’s. Reasoning as in the prior proof, we
have that $D_{+}(S_{0},\ldots,S_{n-1})$ and $D_{+}(s_{0},\ldots,s_{n-1})$ give
the sum of the signs of all members of $\mathcal{B}_{n}$ and
$\mathcal{B}_{n}^{\prime}$, respectively. To show (6), we define a sign-
changing involution on $\mathcal{B}_{n}$ by identifying the leftmost non-
terminal low $h$ and either marking it or removing the marking from it. This
involution fails to be defined for paths of the form $\lambda=\alpha h$, where
$\alpha\in\mathcal{Q}_{n-1}$ and $h$ is marked. Thus, there are $s_{n-1}$
survivors of the involution, each of sign $(-1)^{n-1}$, which implies (6). For
(10), we define an involution on $\mathcal{B}_{n}^{\prime}$ by identifying the
leftmost non-terminal (marked) low h step or peak of height $1$ (i.e., unit of
the form $ud$) and replacing one option with the other. This involution is not
defined on members $\rho=\beta h$, where $\beta\in\mathcal{P}_{n-1}$ contains
no low $h$ steps or peaks of height $1$. Note that there are $A114710[n-1]$
such $\rho$ for all $n\geq 1$, each with sign $(-1)^{n-1}$, which implies
(10).

On the other hand, we have that $D_{-}(S_{0},\ldots,S_{n-1})$ and
$D_{-}(s_{0},\ldots,s_{n-1})$ give the cardinalities of the sets
$\mathcal{B}_{n}$ and $\mathcal{B}_{n}^{\prime}$, respectively. To show (7),
consider decomposing $\rho\in\mathcal{B}_{n}$ as
$\rho=\rho^{(1)}\cdots\rho^{(r)}$ for some $r\geq 1$, where each $\rho^{(i)}$
ends in a marked low $h$ step and contains no other marked steps. Write
$\rho^{(i)}=\alpha_{i}h$ for $1\leq i\leq r$, where $\alpha_{i}$ is possibly
empty. Define $\overline{\rho}^{(i)}=u\alpha_{i}d$ and let
$\overline{\rho}=\overline{\rho}^{(1)}\cdots\overline{\rho}^{(r)}$. Then the
mapping $\rho\mapsto\overline{\rho}$ is seen to define a bijection between
$\mathcal{B}_{n}$ and $\mathcal{Q}_{n}$ (to reverse it, consider positions of
the returns in members of $\mathcal{Q}_{n}$), and hence
$|\mathcal{B}_{n}|=s_{n}$, which implies (7). Finally, members of
$\mathcal{B}_{n}^{\prime}$ and $\mathcal{P}_{n-1}$ are seen to be synonymous,
upon removing the marking from all low $h$’s and disregarding the final $h$ in
members of the former, which implies (11). ∎

Proof of (12):

Let $\mathcal{J}_{n,k}$ for $1\leq k\leq n$ denote the set of ordered
$k$-tuples $\lambda=(\lambda_{1},\ldots,\lambda_{k})$ wherein each
$\lambda_{i}$ is a restricted Schröder path having length at least two such
that $\sum_{i=1}^{k}|\lambda_{i}|=n+k$. Define the sign of
$\lambda\in\mathcal{J}_{n,k}$ by $(-1)^{n-k}$ and let
$\mathcal{J}_{n}=\cup_{k=1}^{n}\mathcal{J}_{n,k}$. Then we have that
$D_{+}(s_{2},\ldots,s_{n+1})$ gives the sum of the signs of all members of
$\mathcal{J}_{n}$. We define a sign-changing involution of $\mathcal{J}_{n}$
which makes use of several cases as follows. First suppose that the final
component $\lambda_{k}$ of $\lambda\in\mathcal{J}_{n,k}$ is _not_ primitive.
If $\lambda_{k}=u\sigma d\tau$, where $\sigma$ is a possibly empty Schröder
path and $|\tau|\geq 2$, then replace $\lambda_{k}$ with the two components
$\lambda_{k}=\tau$ and $\lambda_{k+1}=u\sigma dud$, leaving all other
components of $\lambda$ unchanged. We perform the reverse operation, i.e.,
fusing the last two components and dropping $ud$, if the last component
consists of a unit followed by $ud$. This pairs all members of
$\mathcal{J}_{n}$ in which the final component is not primitive except for
those belonging to $\mathcal{J}_{n,1}$ where $\lambda_{1}=u\sigma dud$ for
some $\sigma$.

Now suppose $\lambda_{k}$ within $\lambda$ is primitive. First assume
$|\lambda_{k}|\geq 3$, and we consider the following further subcases:

$\displaystyle(\text{i})~{}$ $\displaystyle\lambda_{k}=u\sigma d,\text{ with
}\sigma\text{ containing no low }h\text{'s}\text{ and }|\sigma|\geq 2,$
$\displaystyle(\text{ii})~{}$
$\displaystyle\lambda_{k}=u\sigma^{\prime}h\sigma^{\prime\prime}d,\text{ with
}\sigma^{\prime}\neq\varnothing\text{ and containing no low }h\text{'s}\text{
and }\sigma^{\prime\prime}\text{ possibly empty},$
$\displaystyle(\text{iii})~{}$ $\displaystyle\lambda_{k}=uh\sigma d,\text{
with }\sigma\neq\varnothing,$

where $\sigma,\sigma^{\prime},\sigma^{\prime\prime}$ denote Schröder paths.
(Note that by $\sigma$ or $\sigma^{\prime}$ not containing a low $h$ in the
preceding, we mean when $\sigma$ or $\sigma^{\prime}$ is viewed by itself
starting from the origin.) Now suppose
$\rho=(\rho_{1},\ldots,\rho_{k})\in\mathcal{J}_{n,k}$, with $\rho_{k}$
primitive and $|\rho_{k}|=2$. We consider the following subcases: (I)
$\rho_{k}=u^{2}d^{2}$, (II) $\rho_{k}=uhd$, with $\rho_{k-1}$ not primitive,
or (III) $\rho_{k}=uhd$, with $\rho_{k-1}$ primitive. Note that $n\geq 2$
implies $k\geq 2$ in (I)–(III) and hence a penultimate component exists in
each case. We now perform the following operations on the members of
$\mathcal{J}_{n,k}$ in (i)–(iii) above (leaving all other components
unchanged):

$\displaystyle(\text{a})~{}$ $\displaystyle\lambda_{k}=u\sigma
d\leftrightarrow\lambda_{k}=\sigma,~{}\lambda_{k+1}=u^{2}d^{2},$
$\displaystyle(\text{b})~{}$
$\displaystyle\lambda_{k}=u\sigma^{\prime}h\sigma^{\prime\prime}d\leftrightarrow\lambda_{k}=\sigma^{\prime}u\sigma^{\prime\prime}d,~{}\lambda_{k+1}=uhd,$
$\displaystyle(\text{c})~{}$ $\displaystyle\lambda_{k}=uh\sigma
d\leftrightarrow\lambda_{k}=u\sigma d,~{}\lambda_{k+1}=uhd.$

Note that the assumptions on $\sigma,\sigma^{\prime},\sigma^{\prime\prime}$ in
(i)–(iii) imply that these operations are well-defined and it is seen that
they are reversible in each case. Hence, they provide bijections between the
members of $\mathcal{J}_{n}$ satisfying (i), (ii) or (iii) and those
satisfying (I), (II) or (III), respectively. Since the number of components
changes by one in all cases, each member of $\mathcal{J}_{n}$ whose final
component is primitive is paired with another of opposite sign. Thus, when
taken together with the pairing defined in the preceding paragraph, we have
that all members of $\mathcal{J}_{n}$ are paired except for
$\lambda=(\lambda_{1})\in\mathcal{J}_{n,1}$ such that $\lambda_{1}=u\sigma
dud$ for some $\sigma\in\mathcal{P}_{n-1}$. There are $S_{n-1}$ possibilities
for these $\lambda$, each having sign $(-1)^{n-1}$, which implies formula
(12). ∎

Proofs of (22) and (23):

We first find a combinatorial interpretation for $D_{-}(t_{1},\ldots,t_{n})$.
A _short_ unit within a member of $\mathcal{D}_{n}$ will refer to a unit
having length one (i.e., is equal $ud$), with all other units being referred
to as _long_. Let $\mathcal{D}_{n}^{\prime}$ denote the subset of
$\mathcal{D}_{n}$ whose members have last unit short and hence
$|\mathcal{D}_{n}^{\prime}|=C_{n-1}$ for $n\geq 1$. Suppose $\rho$ is a
(weighted) composition of $n$ with $m$ parts occurring in the expansion of
$D_{-}(t_{1},\ldots,t_{n})$. On a part of size $r$ within $\rho$, we overlay
$\alpha\in\mathcal{E}_{r-1}$ followed by $ud$. We do this for each part of
$\rho$ and concatenate the resulting lattice paths $\alpha ud$ to obtain a
member of $\mathcal{D}_{n}^{\prime}$ in which there are $m$ short units
altogether. Upon considering all possible $m$, we have that
$D_{-}(t_{1},\ldots,t_{n})$ gives the cardinality of
$\mathcal{D}_{n}^{\prime}$, which implies (23).

To show (22), first note that $D_{+}(t_{1},\ldots,t_{n})$ gives the sum of the
signs of all $\lambda\in\mathcal{D}_{n}^{\prime}$, where the sign of $\lambda$
is defined as $(-1)^{n-\nu(\lambda)}$ and $\nu$ denotes the statistic
recording the number of short units. Let $r_{n}=D_{+}(t_{1},\ldots,t_{n})$ for
$n\geq 1$; clearly, we have $r_{1}=r_{2}=1$, so we may assume $n\geq 3$. Let
$\rho\in\mathcal{D}_{n}^{\prime}$. If the first unit of $\rho$ has length
$i+1$ for some $1\leq i\leq n-2$, then the contribution towards the sum of
signs is given by $(-1)^{i+1}C_{i}r_{n-i-1}$. Summing over all $i$ yields a
total contribution of $\sum_{i=1}^{n-2}(-1)^{i+1}C_{i}r_{n-i-1}$ for members
of $\mathcal{D}_{n}^{\prime}$ whose first unit is long. On the other hand, if
the first unit is short, then there are $r_{n-1}$ possibilities as no
adjustment for the sign is required when prepending a short unit to a member
of $\mathcal{D}_{n-1}^{\prime}$. Combining the prior cases of $\rho$ implies
$r_{n}$ satisfies the desired recurrence and completes the proof. ∎

Proofs of (24) and (25):

Let $\mathcal{L}_{n}$ denote the set of marked members of $\mathcal{E}_{n}$
wherein the first unit is not marked and all other units may be marked. Define
the sign of $\lambda\in\mathcal{E}_{n}$ by $(-1)^{n-\mu(\lambda)}$, where
$\mu(\lambda)$ denotes the number of unmarked units of $\lambda$. Then
$D_{+}(t_{2},\ldots,t_{n+1})$ and $D_{-}(t_{2},\ldots,t_{n+1})$ are seen to
give the sum of signs and cardinality, respectively, of the members of
$\mathcal{L}_{n}$. To show (24), define an involution on $\mathcal{L}_{n}$ by
marking or unmarking the second unit, if it exists. This operation is not
defined on the primitive members of $\mathcal{L}_{n}$, each of which has sign
$(-1)^{n-1}$. Since the primitive members of $\mathcal{L}_{n}$ have
cardinality $C_{n-1}$ for $n\geq 2$, formula (24) is established.

To show (25), let $b_{n}=D_{-}(t_{2},\ldots,t_{n+1})$ for $n\geq 1$ and note

$b_{n}=C_{n-1}+2\sum_{k=1}^{n-3}C_{k}b_{n-k-1},\qquad n\geq 3,$ (28)

with $b_{1}=0$ and $b_{2}=1$, upon considering whether or not a member of
$\mathcal{L}_{n}$ is primitive and, if not, taking into account the length
$k+1$ of the first unit, where $1\leq k\leq n-3$. Here, the factor of 2
accounts for the choice concerning whether or not the second unit is marked in
the latter case. In order to establish $b_{n}=A137398[n]$, we must show that
$b_{n}$ satisfies the defining recurrence for $A137398[n]$, i.e.,

$b_{n}=2b_{n-1}+2b_{n-2}+\sum_{k=1}^{n-3}C_{k}b_{n-k-1},\qquad n\geq 4.$ (29)

Comparing (28) and (29), to complete the proof of (25), it suffices to show

$C_{n-1}+\sum_{k=2}^{n-3}C_{k}b_{n-k-1}=2b_{n-1}+b_{n-2},\qquad n\geq 4.$ (30)

We may assume $n\geq 5$ in (30) since it is seen to hold for $n=4$.

To prove (30), we describe a combinatorial structure enumerated by the left
side of the identity and show that this structure is also enumerated by the
right. We will make use of the same descriptors short and long as before when
referring to units of varying length. Let $\mathcal{Y}_{n}$ denote the set of
all marked Dyck paths of length $n$ containing at least one short unit wherein
long units occurring to the right of the rightmost short unit (if there are
any) may be marked, but where the first such long unit is always unmarked.
Further, we require that the rightmost short unit within a member of
$\mathcal{Y}_{n}$ correspond to the $(2i-1)$-st and $(2i)$-th steps for some
$i\geq 3$. Note that there are $C_{n-1}$ members of $\mathcal{Y}_{n}$ ending
in a short unit, upon appending $ud$ to any member of $\mathcal{D}_{n-1}$.
Otherwise, $\lambda\in\mathcal{Y}_{n}$ is expressible as
$\lambda=\lambda^{\prime}ud\lambda^{\prime\prime}$, where $\lambda^{\prime}$
is any Dyck path with $|\lambda^{\prime}|\geq 2$ and $\lambda^{\prime\prime}$
is nonempty and consists of long units that may be marked, except for the
first, which is always unmarked. Then there are $C_{k}b_{n-k-1}$ possibilities
for $\lambda$ in which $|\lambda^{\prime}|=k$ and considering all possible
$k\in[2,n-3]$ implies that there are $\sum_{k=2}^{n-3}C_{k}b_{n-k-1}$ members
of $\mathcal{Y}_{n}$ that end in a long unit. Thus, we have that the left-hand
side of (30) gives $|\mathcal{Y}_{n}|$.

We now show that $2b_{n-1}+b_{n-2}$ also gives $|\mathcal{Y}_{n}|$. First let
us take two copies of each $\alpha\in\mathcal{L}_{n-1}$, where it is assumed
for now that $\alpha$ contains at least one marked unit. Then write
$\alpha=\alpha_{1}\cdots\alpha_{\ell-1}\alpha_{\ell}\cdots\alpha_{r}$, where
the $\alpha_{i}$ denote the units of $\alpha$, the leftmost marked unit is
$\alpha_{\ell}$ and $2\leq\ell\leq r$. Within the first copy of $\alpha$, we
insert $ud$ directly between the units $\alpha_{\ell-1}$ and $\alpha_{\ell}$.
Within the second copy of $\alpha$, we replace $\alpha_{\ell-1}$ with
$ud\alpha_{\ell}^{\prime}ud$, where
$\alpha_{\ell-1}=u\alpha_{\ell-1}^{\prime}d$. In both cases, we remove the
mark from the unit $\alpha_{\ell}$ and leave all other units of $\alpha$
undisturbed. On the other hand, if $\alpha\in\mathcal{L}_{n-2}$ contains a
marked unit and is decomposed into units as above, then we insert $udud$
between the units $\alpha_{\ell-1}$ and $\alpha_{\ell}$ and remove the mark
from $\alpha_{\ell}$. Note that the operations described in this paragraph
yield uniquely all members of $\mathcal{Y}_{n}$ not ending in $ud$ and can be
reversed by considering the position of the rightmost short unit and taking
into account whether there are one or more short units. If there are more than
one, then consider further whether or not the leftmost and rightmost short
units are adjacent.

So it remains to show

$2|\\{\alpha\in\mathcal{L}_{n-1}:\alpha\text{ has no marked
units}\\}|+|\\{\alpha\in\mathcal{L}_{n-2}:\alpha\text{ has no marked
units}\\}|$

equals the number of members of $\mathcal{Y}_{n}$ ending in $ud$ (recall that
this number is $C_{n-1}$). Note that this equality is equivalent to the known
relation $2t_{n}+t_{n-1}=C_{n-1}$ for $n\geq 2$; for a combinatorial proof, we
refer the reader to [6, Section 3]. This completes the proof of (30), as
desired. ∎

Proof of (26):

Let $\mathcal{M}_{n,k}$ for $1\leq k\leq n$ denote the set of ordered
$k$-tuples $(\lambda_{1},\ldots,\lambda_{k})$ such that each $\lambda_{i}$ is
a nonempty Dyck path all of whose units are long, with
$\sum_{i=1}^{k}|\lambda_{i}|=n+k$. Let members of $\mathcal{M}_{n,k}$ have
sign $(-1)^{n-k}$. Then it is seen that $D_{+}(t_{3},\ldots,t_{n+2})$ gives
the sum of the signs of all members of $\mathcal{M}_{n}$, where
$\mathcal{M}_{n}=\cup_{k=1}^{n}\mathcal{M}_{n,k}$. Before defining an
involution on $\mathcal{M}_{n}$, let us recall a definition. By a _valley_ of
height $j$ within a Dyck path where $j\geq 0$, we mean a $d$ directly followed
by a $u$ step in which the $u$ has starting height $j$. A _special_ valley
will refer to one of height $1$. Let
$\lambda=(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{M}_{n,k}$ and suppose
first that the component $\lambda_{k}$ contains at least one special valley.
We decompose $\lambda_{k}$ as $\lambda_{k}=\alpha\bf{du}\beta$, where $\alpha$
and $\beta$ contain $2a$ and $2b$ steps respectively and $\bf{du}$ denotes the
rightmost special valley. Note that $a,b\geq 1$, with $|\lambda_{k}|=a+b+1$.
Let $\lambda^{*}$ be obtained from $\lambda$ by replacing $\lambda_{k}$ with
the two components $\lambda_{k}=\alpha d^{2}$ and $\lambda_{k+1}=u^{2}\beta$,
keeping all other components of $\lambda$ the same. One may verify
$\lambda_{k}\in\mathcal{E}_{a+1}$, $\lambda_{k+1}\in\mathcal{E}_{b+1}$, and
hence $\lambda^{*}\in\mathcal{M}_{n,k+1}$, with $\lambda_{k+1}$ containing no
special valleys. If it is the case that $\lambda\in M_{n,k}$ for some $k>1$
with $\lambda_{k}$ containing no special valleys, then $\lambda^{*}$ is
obtained from $\lambda$ by reversing the operation described above. The
mapping $\lambda\mapsto\lambda^{*}$ is an involution of $\mathcal{M}_{n}$
which always changes the sign and is not defined on
$\mathcal{M}_{n}^{\prime}\subseteq\mathcal{M}_{n}$ consisting of those
$\lambda=(\rho)\in\mathcal{M}_{n,1}$ such that $\rho$ contains no special
valleys.

To enumerate the members of $\mathcal{M}_{n}^{\prime}$, note that $\rho$ can
be decomposed into units as $\rho=\rho_{1}\cdots\rho_{j}$ for some $j\geq 1$,
where $\rho_{i}=u^{2}\rho_{i}^{\prime}d^{2}$ for each $i$ with
$\rho_{i}^{\prime}$ possibly empty. Let $a(n,j)$ denote the number of members
of $\mathcal{D}_{n}$ that have $j$ returns. Then removal of the initial $u$
and the final $d$ from each unit $\rho_{i}$ within $\rho$ implies that there
are $a(n+1-j,j)$ possible $\rho$, and summing over all $j$ yields
$|\mathcal{M}_{n}^{\prime}|=\sum_{j=1}^{\lfloor(n+1)/2\rfloor}a(n+1-j,j)$.
Recall that one of the combinatorial properties for $A030238[n]$ is that it is
given explicitly as $\sum_{j=1}^{\lfloor(n+2)/2\rfloor}a(n+2-j,j)$. Hence,
$|\mathcal{M}_{n}^{\prime}|=A030238[n-1]$ for $n\geq 1$. Since each member of
$\mathcal{M}_{n}^{\prime}$ has sign $(-1)^{n-1}$, the proof of (26) is
complete. ∎

Proof of (27):

Let $\mathcal{T}_{n,k}$ denote the set of ordered $k$-tuples
$(\lambda_{1},\ldots,\lambda_{k})$ such that each $\lambda_{i}$ is a Dyck path
of length at least three all of whose units are long, with
$\sum_{i=1}^{k}|\lambda_{i}|=n+2k$. Let members of $\mathcal{T}_{n,k}$ have
sign $(-1)^{n-k}$ and let $\mathcal{T}_{n}=\cup_{k=1}^{n}\mathcal{T}_{n,k}$.
Then we have that $D_{+}(t_{4},\ldots,t_{n+3})$ gives the sum of signs of all
members of $\mathcal{T}_{n}$. Let
$\mathcal{T}_{n}^{\prime}\subseteq\mathcal{T}_{n}$ consist of
$(\lambda_{1})\in\mathcal{T}_{n,1}$ such that $\lambda_{1}$ is expressible as
$\lambda_{1}=u^{2}d^{2}\alpha$, where $\alpha$ is a unit. Note that $n\geq 3$
implies $|\alpha|\geq 3$ and hence $\alpha$ is long, as required. As there are
$C_{n-1}$ possibilities for $\lambda_{1}$, we have
$\sigma(\mathcal{T}_{n}^{\prime})=(-1)^{n-1}C_{n-1}$, where $\sigma(S)$
denotes the sum of the signs of the members of a subset $S$ of
$\mathcal{T}_{n}$. Below, we define in several steps a sign-changing
involution on the entirety of $\mathcal{T}_{n}-\mathcal{T}_{n}^{\prime}$ when
$n\geq 3$, which implies (27).

We first partition $\mathcal{T}_{n}-\mathcal{T}_{n}^{\prime}$ into three
subsets $\mathcal{U}_{n}$, $\mathcal{V}_{n}$ and $\mathcal{W}_{n}$ given by

$\displaystyle(\text{i})~{}$
$\displaystyle\mathcal{U}_{n}=\\{(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{T}_{n}-\mathcal{T}_{n}^{\prime}:\lambda_{k}\
\text{ not primitive}\\},$ $\displaystyle(\text{ii})~{}$
$\displaystyle\mathcal{V}_{n}=\\{(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{T}_{n}-\mathcal{T}_{n}^{\prime}:\lambda_{k}\
\text{ primitive and contains no special peaks}\\},$
$\displaystyle(\text{iii})~{}$
$\displaystyle\mathcal{W}_{n}=\\{(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{T}_{n}-\mathcal{T}_{n}^{\prime}:\lambda_{k}\
\text{ primitive and contains at least one special peak}\\},$

where $k\geq 1$ in each case and a _special_ peak is one of height two. We
first define involutions on $\mathcal{U}_{n}$ and $\mathcal{V}_{n}$. Let
$(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{U}_{n}$ and suppose
$\lambda=\alpha\beta$, where $|\alpha|\geq 2$ and $\beta$ is a unit. Then we
replace the component $\lambda_{k}$ with the two components
$\lambda_{k}=\alpha$ and $\lambda_{k+1}=u^{2}d^{2}\beta$, if $|\alpha|\geq 3$,
or perform the inverse operation if $|\alpha|=2$ (i.e., $\alpha=u^{2}d^{2}$).
Note that the possible case where $k=1$ and $\lambda_{1}=u^{2}d^{2}\beta$ has
been excluded from consideration since such members of $\mathcal{T}_{n}$
belong to $\mathcal{T}_{n}^{\prime}$. Thus, the two operations defined above
taken together yield an involution, which we will denote by $\phi$, that is
defined on all of $\mathcal{U}_{n}$.

Now suppose $(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{V}_{n}$. Then either
$|\lambda_{k}|\geq 4$ and is primitive with no special peaks or
$\lambda_{k}=u^{3}d^{3}$. In the former case, we decompose $\lambda_{k}$ as
$\lambda_{k}=u\alpha d$, where $\alpha\geq 3$. If $|\lambda_{k}|\geq 4$, then
replace the component $\lambda_{k}=u\alpha d$ with the two components
$\lambda_{k}=\alpha$ and $\lambda_{k+1}=u^{3}d^{3}$, keeping all other
components the same. Note that $\lambda_{k}$ containing no special peaks
implies that the penultimate component $\alpha$ in the resulting member of
$\mathcal{T}_{n}$ contains no short units, as required. If the final component
$\lambda_{k}$ equals $u^{3}d^{3}$, then perform the inverse operation, noting
that $n\geq 3$ implies $k\geq 2$ in this case. Thus, the two operations taken
together yield an involution, which we will denote by $\psi$, that is defined
on all of $\mathcal{V}_{n}$.

Define the subset $\mathcal{W}_{n}(1)$ of $\mathcal{W}_{n}$ as follows:

$\displaystyle\mathcal{W}_{n}(1)=\\{(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{W}_{n}:$
$\displaystyle\,\lambda_{k}=u\alpha ud\beta d,\text{ where }|\alpha|\geq
1\text{ and }\beta\text{ contains only long units }$ $\displaystyle\text{ and
is possibly empty}\\}.$

In Lemma 6 below, it is shown $\sigma(W_{n}(1))=0$.

Now define the subset $\mathcal{W}_{n}(2)$ of $\mathcal{W}_{n}$ as consisting
of those $(\lambda_{1},\ldots,\lambda_{k})$ such that one of the following two
conditions holds:

$\displaystyle(\text{a})~{}$ $\displaystyle k\geq 1\text{ and
}\lambda_{k}=u(ud)\beta d,\text{ where }\beta\text{ consists of two or more
long units, or}$ $\displaystyle(\text{b})~{}$ $\displaystyle k\geq 2\text{ and
}\lambda_{k}=u(ud)\tau d,\text{ where }\tau\text{ is a single long unit, and
}\lambda_{k-1}=u(ud)\beta d,\text{ where }\beta\text{ consists }$
$\displaystyle\text{of one or more long units}.$

Define an involution of $\mathcal{W}_{n}(2)$ by breaking apart or combining
the final two components as indicated:

$\lambda_{k}=u(ud)\beta
d\leftrightarrow\lambda_{k}=u(ud)\beta^{\prime}d,\,\lambda_{k+1}=u(ud)\tau d,$

where $\beta$ consists of two or more long units, the first of which is
denoted by $\tau$, and $\beta^{\prime}=\beta-\tau$.

Let
$\mathcal{W}_{n}^{\prime}=\mathcal{W}_{n}-\mathcal{W}_{n}(1)-\mathcal{W}_{n}(2)$.
Note that $(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{W}_{n}^{\prime}$
implies $\lambda_{k}=u(ud)\tau d$, where $\tau$ is a long unit. We decompose
$\mathcal{W}_{n}^{\prime}$ as
$\mathcal{W}_{n}^{\prime}=\cup_{i=1}^{4}\mathcal{W}_{n}^{\prime}(i)$, where
$\mathcal{W}_{n}^{\prime}(i)$ for $1\leq i\leq 4$ consists of those
$(\lambda_{1},\ldots,\lambda_{k})$ in $\mathcal{W}_{n}^{\prime}$ satisfying
respectively

$\displaystyle(\text{1})~{}$ $\displaystyle k=1,$ $\displaystyle(\text{2})~{}$
$\displaystyle k\geq 2\text{ and }\lambda_{k-1}\text{ is not primitive},$
$\displaystyle(\text{3})~{}$ $\displaystyle k\geq 2\text{ and
}\lambda_{k-1}\text{ is primitive with no special peaks, or}$
$\displaystyle(\text{4})~{}$ $\displaystyle k\geq 2\text{ and
}\lambda_{k-1}=u\alpha(ud)\beta d,\text{ where }|\alpha|\geq 1\text{ and
}\beta,\text{ possibly empty, consists of long units}.$

Below, it is shown in Lemma 7 that $\sigma(\mathcal{W}_{n}^{\prime})=0$ using
the cases above, and hence $\sigma(\mathcal{W}_{n})=0$. This implies
$\sigma(\mathcal{T}_{n}-\mathcal{T}_{n}^{\prime})=0$, as desired. ∎

######  Lemma 6.

If $n\geq 2$, then $\sigma(\mathcal{W}_{n}(1))=0$.

###### Proof.

The result is readily shown if $n=2$, so we may assume $n\geq 3$. We pair
members of $\mathcal{W}_{n}(1)$ of opposite sign by either breaking apart the
last component or combining the last two components as indicated:

$\lambda_{k}=u\alpha ud\beta d,\,|\alpha|\geq
2\leftrightarrow\lambda_{k}=u\alpha d,\,\lambda_{k+1}=u(ud)^{2}\beta d.$

The set of survivors of this involution consists of those $k$-tuples
$(\lambda_{1},\ldots,\lambda_{k})$ such that either (i) $k\geq 2$ and
$\lambda_{k}=u(ud)^{2}\beta d$, with $\beta$ consisting of long units if
nonempty and $\lambda_{k-1}$ not primitive, or (ii) $k=1$ and
$\lambda_{1}=u(ud)^{2}\beta d$, with $\beta$ as in (i). Note that $n\geq 3$
implies $\beta\neq\varnothing$ in the latter case. On the survivors satisfying
condition (i), we apply the involution $\phi$ defined above to the
$(k-1)$-tuple comprising the first $k-1$ components and then append
$\lambda_{k}$ to the resulting vector. Thus, all members satisfying (i) are
paired except for those in which $k=2$ with $\lambda_{1}=u^{2}d^{2}\tau$ and
$\lambda_{2}=u(ud)^{2}\beta d$, where $\beta$ consists of long units and
$\tau$ is a single (long) unit.

Suppose $|\tau|=i+1$ in the decomposition of $\lambda_{1}$. This implies

$|\beta|=(n+4)-|\lambda_{1}|-3=n-2-i$

in $\lambda_{2}$, and thus $\beta\in\mathcal{E}_{n-2-i}$. Hence summing over
all $i$ yields $\sum_{i=1}^{n-2}C_{i}t_{n-1-i}$ possible ordered pairs
$(\lambda_{1},\lambda_{2})$. Further, the survivors in case (ii) above have
cardinality $t_{n}$ since $\beta$ has length $n-1$ and contains only long
units. Thus, the sum of the signs of the remaining unpaired members of
$\mathcal{W}_{n}(1)$ is given by

$(-1)^{n-2}\sum_{i=1}^{n-2}C_{i}t_{n-1-i}+(-1)^{n-1}t_{n}=0,$

as desired, upon observing the recurrence
$t_{n}=\sum_{i=1}^{n-2}C_{i}t_{n-1-i}$ for $n\geq 3$. Note that this
recurrence may be easily realized combinatorially by considering the length
$i+1$ of the first unit within a member of $\mathcal{E}_{n-1}$. Thus, if
desired, it is straightforward to pair the remaining members of
$\mathcal{W}_{n}(1)$ of opposite sign upon considering the position of the
first return within a member of $\mathcal{E}_{n-1}$. ∎

######  Lemma 7.

If $n\geq 3$, then
$\sigma(\cup_{i=1}^{3}\mathcal{W}_{n}^{\prime}(i))=-\sigma(\mathcal{W}_{n}^{\prime}(4))=(-1)^{n-1}C_{n-2}$,
and hence $\sigma(\mathcal{W}_{n}^{\prime})=0$.

###### Proof.

We consider several cases on
$\lambda=(\lambda_{1},\ldots,\lambda_{k})\in\mathcal{W}_{n}^{\prime}$ whose
last component $\lambda_{k}$ is given by $\lambda_{k}=u(ud)\tau d$, where
$\tau$ is a long unit. If $\lambda\in\mathcal{W}_{n}^{\prime}(1)$, then $k=1$
implies $|\tau|=n$ and thus
$\sigma(\mathcal{W}_{n}^{\prime}(1))=(-1)^{n-1}C_{n-1}$. If
$\lambda\in\mathcal{W}_{n}^{\prime}(2)$, we apply the mapping $\phi$ defined
above to $\lambda^{\prime}=(\lambda_{1},\ldots,\lambda_{k-1})$ and then append
$\lambda_{k}$ to $\phi(\lambda^{\prime})$. This operation yields an involution
on $\mathcal{W}_{n}^{\prime}(2)$ that is not defined for those members in
which $k=2$ with $\lambda_{1}=u^{2}d^{2}\sigma$ and $\sigma$ is a unit. Upon
considering $|\sigma|=i+1$ for $1\leq i\leq n-3$, one gets

$\sum_{i=1}^{n-3}C_{i}C_{n-2-i}=C_{n-1}-2C_{n-2}$

unpaired members of $\mathcal{W}_{n}^{\prime}(2)$, by the recurrence for the
Catalan numbers. If $\lambda\in\mathcal{W}_{n}^{\prime}(3)$, we apply the
mapping $\psi$ defined above to $\lambda^{\prime}$ and then append
$\lambda_{k}$ to $\psi(\lambda^{\prime})$. This operation yields an involution
on $\mathcal{W}_{n}^{\prime}(3)$ except for those members where $k=2$ and
$\lambda_{1}=u^{3}d^{3}$, of which there are $C_{n-2}$ possibilities.
Combining the contributions from $W_{n}^{\prime}(i)$ for $1\leq i\leq 3$
yields

$\sigma(\cup_{i=1}^{3}W_{n}^{\prime}(i))=(-1)^{n-1}C_{n-1}+(-1)^{n-2}(C_{n-1}-2C_{n-2})+(-1)^{n-2}C_{n-2}=(-1)^{n-1}C_{n-2}.$

For the second statement, let $T$ denote the subset of
$\mathcal{W}_{n}^{\prime}(4)$ consisting of those members where $k=2$ and
$\lambda_{1}=u(ud)^{2}d$. Since $\sigma(T)=(-1)^{n-2}C_{n-2}$, we need to show
$\sigma(\mathcal{W}_{n}^{\prime}(4)-T)=0$. Note that within the final
component $\lambda_{k}=u(ud)\tau d$ of
$\lambda\in\mathcal{W}_{n}^{\prime}(4)-T$, we must have $2\leq|\tau|\leq n-2$.
We may then apply the involution $g$ from Lemma 6 to $\lambda^{\prime}$ (as
$|\tau|\leq n-2$), and to the resulting vector $g(\lambda^{\prime})$, we
append the component $\lambda_{k}$. This operation is seen to yield a sign-
changing involution of $\mathcal{W}_{n}^{\prime}(4)-T$, which completes the
proof. ∎

## References

  * [1] H. Belbachir, A. Belkhir and I.-E. Djellas, Permanent of Toeplitz-Hessenberg matrices with generalized Fibonacci and Lucas entries, Appl. Appl. Math. 17(2) (2022), 558–570.
  * [2] D. Callan, Some bijections and identities for the Catalan and Fine numbers, Sém. Lothar. Combin. 53 (2006), Article B53e.
  * [3] Z. Chen and H. Pan, Identities involving weighted Catalan, Schröder and Motzkin paths, Adv. Appl. Math. 86 (2017), 81–98.
  * [4] E. Y. P. Deng and W.-J. Yan, Some identities on the Catalan, Motzkin and Schröder numbers, Discrete Appl. Math. 156(14) (2008), 2781–2789.
  * [5] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.
  * [6] E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math. 241 (2001), 241–265.
  * [7] M. Elouafi, A unified approach for the Hankel determinants of classical combinatorial numbers, J. Math. Anal. Appl. 431(2) (2015), 1253–1274.
  * [8] T. Goy and M. Shattuck, Determinant formulas of some Toeplitz–Hessenberg matrices with Catalan entries, Proc. Indian Acad. Sci. Math. Sci. 129(4) (2019), Article 46.
  * [9] T. Goy and M. Shattuck, Determinants of Toeplitz–Hessenberg matrices with generalized Fibonacci entries, Notes Number Theory Discrete Math. 25(4) (2019), 83–95.
  * [10] T. Goy and M. Shattuck, Determinant identities for Toeplitz–Hessenberg matrices with tribonacci number entries, Trans. Comb. 9(2) (2020), 89–109.
  * [11] T. Goy and M. Shattuck, Some Toeplitz–Hessenberg determinant identities for the tetranacci numbers, J. Integer Seq. 23 (2020), Article 20.6.8.
  * [12] T. Komatsu and J. L. Ramírez, Some determinants involving incomplete Fubini numbers, An. Şt. Univ. Ovidius Constanţa Ser. Mat. 26 (2018), 143–170.
  * [13] M. Merca, A note on the determinant of a Toeplitz-Hessenberg matrix, Spec. Matrices 1 (2013), 10–16.
  * [14] L. Mu and Y. Wang, Hankel determinants of shifted Catalan-like numbers, Discrete Math. 340(6) (2017), 1389–1396.
  * [15] T. Muir, The Theory of Determinants in the Historical Order of Development, Vol. 3, Dover Publications, 1960.
  * [16] L. V. Shapiro and C. J. Wang, A bijection between $3$-Motzkin paths and Schröder paths with no peak at odd height, J. Integer Seq. 12 (2009), Article 09.3.2.
  * [17] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Available at https://oeis.org, 2020.
  * [18] F. Qi, On negativity of Toeplitz-Hessenberg determinants whose elements contain large Schröder numbers, Palestine J. Math. 11(4) (2022), 373–378.
  * [19] F. Qi and B.-N. Guo, Explicit and recursive formulas, integral representations, and properties of the large Schröder numbers, Kragujevac J. Math. 41(4) (2017), 121–141.
  * [20] F. Qi, X.-T. Shi and B.-N. Guo, Two explicit formulas of the Schröder numbers, Integers 16 (2016), #A23.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 11C20,
15B05.

_Keywords:_ Hessenberg–Toeplitz matrix, Trudi’s formula, Schröder number, Fine
number, Catalan number, Schröder path, Dyck path.