<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf
Determinants of Some Hessenberg--Toeplitz Matrices with Motzkin Number Entries\\
\vskip .1in } \vskip 1cm \large
Taras Goy\\
Faculty of Mathematics and Computer Science\\
Vasyl Stefanyk Precarpathian National University \\
Ivano-Frankivsk 76018\\
Ukraine\\
\href{mailto:taras.goy@pnu.edu.ua}{\tt taras.goy@pnu.edu.ua} \\
\vskip .2 in
Mark Shattuck\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN 37996\\
USA\\
\href{mailto:mark.shattuck2@gmail.com}{\tt mark.shattuck2@gmail.com} \\
\end{center}

\vskip .2 in

\begin{abstract}
In this paper, we find formulas for the determinants of some
Hessenberg--Toeplitz matrices whose nonzero entries are derived from the
Motzkin number sequence and its translates.  We provide both algebraic
and combinatorial proofs of our results, making use of generating
functions for the former and various counting methods, such as direct
enumeration, sign-changing involutions, and bijections, for the latter.
In the process, it is shown that three important classes of lattice
paths---namely, the Motzkin paths, the Riordan paths, and the so-called
Motzkin left factors---have their cardinalities given as determinants
of certain Hessenberg--Toeplitz matrices with Motzkin number entries.
Further formulas are found for determinant identities involving 
two sequences from the On-Line Encyclopedia of Integer Sequences,
which are subsequently explained bijectively.
\end{abstract}


\section{Introduction}

The Motzkin numbers, denoted by $M_n$, have been widely studied in enumerative and algebraic combinatorics. They are defined recursively by
\begin{equation*}
M_{n}=M_{n-1}+\sum_{i=0}^{n-2}M_{i}M_{n-2-i}, \quad n \geq 2,
\end{equation*}
or equivalently by
\begin{equation*}
M_{n}=\frac{2n+1}{n+2}M_{n-1}+\frac{3n-3}{n+2}M_{n-2}, \quad n \geq 2,
\end{equation*}
with initial values $M_0=M_1=1$.  The first several terms of the Motzkin sequence $(M_n)_{n \geq0}$ are given by
\begin{equation*}
1,\, 1,\, 2,\, 4,\, 9,\, 21,\, 51,\, 127,\, 323,\, 835,\, 2188,\, 5798,\, 15511,\, 41835,\, 113634, \ldots\,.
\end{equation*}
See sequence \seqnum{A001006} from the {\it On-Line Encyclopedia
of Integer Sequences} (OEIS) \cite{Sl} for further information on
this sequence.  Here we are interested in some new combinatorial
aspects of Motzkin numbers related to their occurrence in certain
Hessenberg--Toeplitz matrices.

Let $R_n$ denote the $n$-th Riordan number \seqnum{A005043} and $L_n$ the $n$-th term of sequence \seqnum{A005773}  for $n \geq 0$.  The first ten terms of $(R_n)_{n\geq0}$ and $(L_n)_{n\geq0}$ are given respectively by
\begin{equation*}
1,\, 0,\, 1,\, 1,\, 3,\, 6,\, 15,\, 36,\, 91,\, 232, \ldots \quad \text{ and }\quad 1,\, 1,\, 2,\, 5,\, 13,\, 35,\, 96,\, 267,\, 750,\, 2123, \ldots.
\end{equation*}
The $R_n$ and $L_n$ are closely aligned with the Motzkin numbers in that they satisfy the simple relations $M_n=R_{n}+R_{n+1}$ and $M_n=3L_{n+1}-L_{n+2}$ for $n\geq0$, which can be shown using generating functions or bijectively.   The $M_n$, $R_n$, and $L_n$ sequences enumerate important classes of first quadrant lattice paths in which there are three kinds of steps---up, down, and horizontal. See \cite{Bern} for further combinatorial properties of the Motzkin and Riordan numbers.  In establishing our results, we will make use of their (ordinary) generating function formulas
\begin{equation*}
M(x):=\sum_{n \geq0}M_nx^n = \frac{1-x-\sqrt{1-2x-3x^2}}{2x^2} \,,
\end{equation*}
\begin{equation*}
R(x):=\sum_{n \geq0}R_nx^n = \frac{1+x-\sqrt{1-2x-3x^2}}{2x(1+x)} \,,
\end{equation*}
and
\begin{equation*}L(x):=\sum_{n\geq0}L_nx^n = \frac{3x-1-\sqrt{1-2x-3x^2}}{6x-2}\,.
\end{equation*}
A variety of different parameters have been considered on Motzkin paths in the literature; see, e.g., \cite{baril,barnabei,chang,chen,fang,florez,gan,oste,sapounakis,shapiro}.

On the other hand, relatively little has been written on determinants of matrices with Motzkin number entries. The main results in this direction are those of Aigner \cite{aigner}, who showed that the
determinant of the Hankel matrix $\big(M_{i+j-2}\big)_{i,j=1}^n$ is 1 for all $n$, while the determinant of the Hankel matrix $\big(M_{i+j-1}\big)_{i,j=1}^n$ is $1, 0, -1, -1, 0, 1$ for
$n=1,\ldots,6$, repeating modulo 6 thereafter. Later, in \cite{cameron}, Cameron and Yip used combinatorial methods to evaluate Hankel determinants
for the sequence of sums of consecutive $t$-Motzkin numbers.

In \cite{GSh-Indian}, 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 could also be expressed equivalently as identities involving sums of products of Catalan numbers and multinomial coefficients. Further comparable results featuring combinatorial arguments have been found for the generalized Fibonacci, tribonacci, and tetranacci numbers \cite{GSh-NNTDM,GSh-Trans,GSh-JIS}.


This paper is organized as follows.  In the next section, we find formulas giving algebraic proofs for the determinants of five Hessenberg--Toeplitz matrices whose entries are derived from translates of the Motzkin number sequence.  In particular, we find new expressions involving determinants for the sequences $M_n$, $R_n$, and $L_n$.  An equivalent multi-sum version of these expressions may be given using a result known as Trudi's formula (see Lemma \ref{lem1} below).  Further formulas are found for determinants of matrices with entries from the $R_n$ and $L_n$ sequences and a related recurrence for sequence \seqnum{A109190} is shown.  In the third section, we provide combinatorial proofs of all of our results where we make use of the definition of an $n \times n$ determinant as a signed sum over the set of permutations of $[n]=\{1,\ldots,n\}$.  We employ various counting techniques, perhaps most notably sign-changing involutions, in providing these proofs and draw upon the combinatorial interpretations of $M_n$, $R_n$, and $L_n$ as enumerators of certain classes of lattice paths.


\section{Determinant formulas of matrices with Motzkin number entries}

A Hessenberg--Toeplitz matrix is one having the form
\begin{equation}\label{DetHess}
A_n:= A_n(a_0; a_1,\ldots,a_n)=\left(\begin{array}{ccccccc}
a_1        &amp; a_0      &amp; 0   &amp;  \cdots       &amp; 0      &amp; 0 \\
a_2        &amp; a_1       &amp; a_0   &amp; \cdots        &amp; 0      &amp; 0 \\
a_3        &amp; a_2       &amp; a_1      &amp; \cdots        &amp; 0      &amp; 0 \\
\cdots     &amp; \cdots    &amp; \cdots &amp; \ddots &amp; \cdots &amp; \cdots \\
a_{n-1}   &amp; a_{n-2}  &amp; a_{n-3} &amp; \cdots  &amp; a_1    &amp; a_0 \\
a_{n}     &amp; a_{n-1}&amp; a_{n-2}   &amp; \cdots &amp; a_2    &amp; a_1
\end{array}\right)\!,
\end{equation}
where $a_0\neq 0$.  The following result is known as \emph{Trudi's formula} \cite[Theorem 1]{MM1} and gives a multinomial expansion of $\det(A_n)$ in terms of a sum of products of the $a_i$.
\begin{lemma}\label{lem1}
	Let $n$ be a positive integer.  Then
	\begin{equation}\label{Trudi}
	\det(A_n)=\sum_{\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},
	\end{equation}
where $	{|s|\choose s_1,\ldots,s_n}=\frac{|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,$ $s_i\geq 0$.
Equivalently, we have
	\begin{equation*}
	\det(A_n) =\sum_{k=1}^n(-a_0)^{n-k}\sum\limits_{\begin{smallmatrix} i_1,\ldots,i_k\geq1\\ i_1+i_2+\cdots+i_{k}=n \end{smallmatrix}}a_{i_1}a_{i_2}\cdots a_{i_k}.
	\end{equation*}
\end{lemma}

The case $a_0=1$ of Trudi's formula is known as \emph{Brioschi's formula} \cite{Muir}. Note that the sum in \eqref{Trudi} may be regarded as being over the set of partitions of the positive integer $n$. Here, we will focus on some cases of $\det(A_n)$ when $a_0=\pm 1$.  To simplify notation, we will write $D_{\pm}(a_1, a_2,\ldots, a_n)$ in place of $\det\!\big(A_n(\pm1; a_1, a_2,\ldots, a_n)\big)$.

Let $C_n=\frac{1}{n+1}{2n\choose n}$ denote the $n$-th Catalan number \cite[\seqnum{A000108}]{Sl}. We have the following Hessenberg--Toeplitz determinant formulas and the corresponding multi-sum Motzkin number identities upon applying \eqref{Trudi}.
\begin{theorem} \label{Theo1} We have
	\begin{align}
	D_{+}(M_0, M_1,\ldots,M_{n-1})&amp;=(-1)^{n-1}R_{n-1}=\sum_{k=0}^{n-1}(-1)^{k}{n-1\choose k}C_{k}, \label{Theo1e1}\\
	D_{+}(M_1,M_2,\ldots,M_{n})&amp;=(-1)^{n-1}M_{n-2}=\sum_{k=1}^{n-1}(-1)^{k}{n-2\choose k-1}C_{k}, \quad n \geq 2,\label{Theo1e2}\\
	D_{-}(M_0,M_1,\ldots,M_{n-1})&amp;=L_n=\sum_{k=0}^{n-1}(-1)^{n-k-1}(2k+1){n-1\choose k}C_k,\label{Theo1e3}\\
	D_{-}(M_1,M_2,\ldots,M_n)&amp;=\frac12\,\seqnum{A111961}(n), \label{Theo1e3b}\\
	D_{+}(M_2,M_3,\ldots,M_{n+1})&amp;=(-1)^{n-1}R_{n-1}, \quad n \geq 2,\label{Theo1e4}
	\end{align}
which hold for $n \geq 1$ unless stated otherwise.
\end{theorem}
\begin{corollary} \label{Theo2} We have
	\begin{align}
	\sum_{\widetilde{s}=n}(-1)^{|s|-1}{|s|\choose s_1,\ldots,s_n}M_0^{s_1}M_1^{s_2}\cdots M_{n-1}^{s_n}&amp;=
	R_{n-1},\label{F1}\\
	\sum_{\widetilde{s}=n}(-1)^{|s|-1}{|s|\choose s_1,\ldots,s_n}M_1^{s_1}M_2^{s_2}\cdots M_{n}^{s_n}&amp;=M_{n-2}, \quad n\geq2, \label{F2}\\
	\sum_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}M_0^{s_1}M_1^{s_2}\cdots M_{n-1}^{s_n}&amp;=L_n,\label{F3}\\
	\sum_{\widetilde{s}=n}{|s|\choose s_1,\ldots,s_n}M_1^{s_1}M_2^{s_2}\cdots M_{n}^{s_n}&amp;=\frac12\,\seqnum{A111961}(n), \label{F3a}\\
	\sum_{\widetilde{s}=n}(-1)^{|s|-1}{|s|\choose s_1,\ldots,s_n}M_2^{s_1}M_3^{s_2}\cdots M_{n+1}^{s_n}&amp;=R_{n-1},\quad n\geq2,\label{F4}
	\end{align}
which hold for $n \geq 1$ unless stated otherwise.
\end{corollary}

The identities in the preceding theorem and corollary are equivalent, so we need only to prove the former where we will draw upon \eqref{Trudi}.
\begin{proof} We proceed to show \eqref{Theo1e1}--\eqref{Theo1e4} and will make use of generating functions.  Let $f(x)=\sum_{n \geq 1}\det(A_n)x^n$, where $A_n$ is of the form \eqref{DetHess}.  By Trudi's formula, we have
\begin{equation*}
f\left(\!-\frac{x}{a_0}\right)=\sum_{n\geq 1}x^n\sum_{\widetilde{s}=n}
	 {|s|\choose s_1,\ldots,s_n}
	\left(-\frac{a_1}{a_0}\right)^{s_1}\cdots\left(-\frac{a_n}{a_0}\right)^{s_n}=\frac{h(x)}{1-h(x)},
\end{equation*}
where $h(x)\!:=-\frac{1}{a_0}\sum_{i\geq 1}a_ix^i$, upon considering the contribution from each term of the expansion $\frac{h(x)}{1-h(x)}=h(x)+h^2(x)+h^3(x)+\cdots$. Thus, we get
\begin{equation*}
f(x)=\frac{g(x)}{1-g(x)},
\end{equation*}
where $g(x):=\sum_{i\geq 1}(-a_0)^{i-1}a_ix^i$.
	
We now consider various cases on $a_i$.  First suppose $a_i=M_{i-r}$ for $i \geq 1$, where $r \geq 1$ is fixed and $M_j:=0$ if $j&lt;0$.  In this case, we have
	\begin{align*}
	g(x)&amp;=\sum_{i\geq1}(-a_0)^{i-1}M_{i-r}x^i=\sum_{i\geq0}(-a_0)^{i+r-1}M_ix^{i+r}=(-a_0)^{r-1}x^r\sum_{i \geq0}M_i(-a_0x)^i\\
	&amp;=(-a_0)^{r-1}x^rM(-a_0x).
	\end{align*}
If $r=a_0=1$ in the preceding, then we get
	\begin{equation*}
	g(x)=xM(-x)=\frac{1+x-\sqrt{1+2x-3x^2}}{2x}
	\end{equation*}
and
	\begin{align*}
	\sum_{n\geq1}D_+(M_0,\ldots,M_{n-1})x^n&amp;=f(x)=\frac{g(x)}{1-g(x)}=\frac{x-1+\sqrt{1+2x-3x^2}}{2(1-x)}\\
	&amp;=xR(-x)=\sum_{n\geq1}(-1)^{n-1}R_{n-1}x^n,
	\end{align*}
	which yields the first part of formula \eqref{Theo1e1}.  If $r=1$ and $a_0=-1$, then we get $g(x)=xM(x)$ and
	\begin{align*}
	\sum_{n\geq1}D_{-}(M_0,\ldots,M_{n-1})x^n&amp;	=f(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{3x-1+\sqrt{1-2x-3x^2}}\\&amp;=L(x)-1=\sum_{n\geq 1}L_nx^n,
	\end{align*}
	which yields the first part of \eqref{Theo1e3}.
	
Now suppose $a_i=M_{i+r}$, where $r \geq 0$.  In this case, we have
	\begin{align*}
	g(x)&amp;=\sum_{i \geq 1}(-a_0)^{i-1}M_{i+r}x^i=-\frac{1}{a_0}\sum_{i\geq r+1}M_i(-a_0x)^{i-r}\\
	&amp;=\frac{1}{(-a_0)^{r+1}x^r}\left(M(-a_0x)-\sum_{i=0}^rM_i(-a_0x)^i\right)\!.
	\end{align*}
	If $r=0$ and $a_0=1$ in the preceding, then
\begin{equation*}
g(x)=1-M(-x)=\frac{2x^2-x-1+\sqrt{1+2x-3x^2}}{2x^2}
\end{equation*}
	and
	\begin{equation*}
	f(x)=\frac{g(x)}{1-g(x)}=\frac{2x^2-x-1+\sqrt{1+2x-3x^2}}{x+1-\sqrt{1+2x-3x^2}}\,.
	\end{equation*}
	Hence, we have
	\begin{align*}
	\sum_{n\geq2}D_+(M_1,\ldots,M_{n})x^n&amp;=f(x)-x=\frac{\sqrt{1+2x-3x^2}-x-1}{2}\\
	&amp;=\sum_{n\geq 2}(-1)^{n-1}M_{n-2}x^n,
	\end{align*}
	which yields the first part of \eqref{Theo1e2}.  If $r=0$ and $a_0=-1$, then $g(x)=M(x)-1$ and 	\begin{equation*}
	f(x)=\frac{M(x)-1}{2-M(x)}=\frac{K(x)-1}{2}\,,
	\end{equation*}
where
	\begin{equation*}
	K(x):=\sum_{n\geq0}\seqnum{A111961}(n)x^n=\frac{1}{\sqrt{1-2x-3x^2}-x}\,,
	\end{equation*}
which implies \eqref{Theo1e3b}. If $r=a_0=1$, then
	\begin{equation*}
	g(x)=\frac{1}{x}\big(M(-x)-1+x\big)=\frac{1+x-2x^2+2x^3-\sqrt{1+2x-3x^2}}{2x^3}
	\end{equation*}
	and
		\begin{equation*}
		f(x)=\frac{1+x-2x^2+2x^3-\sqrt{1+2x-3x^2}}{2x^2-x-1+\sqrt{1+2x-3x^2}}\,.
		\end{equation*}
	Hence, we have
	\begin{align*}
	\sum_{n\geq2}D_+(M_2,\ldots,M_{n+1})x^n&amp;=f(x)-2x=\frac{x-1+\sqrt{1+2x-3x^2}}{2(1-x)}-x\\
	&amp;=\sum_{n\geq2}(-1)^{n-1}R_{n-1}x^n,
	\end{align*}
	which implies \eqref{Theo1e4}.  Finally, the second parts of \eqref{Theo1e1}--\eqref{Theo1e3} may be shown by computing the respective generating functions using the formula $\sum_{n\geq 0}C_nx^n=\frac{1-\sqrt{1-4x}}{2x}$, the details of which we leave to the reader.
\end{proof}

The $R_n$ and $L_n$ sequences satisfy the following further determinant identities.
\begin{theorem}\label{Theo3}
	We have
 \begin{align}
	D_-(R_0,R_1,\ldots,R_{n-1})&amp;=M_{n-1},\label{Theo3e1}\\
	D_+(R_0,R_1,\ldots,R_{n-1})&amp;=(-1)^{n-1}\seqnum{A344507}(n-1),\label{Theo3e2}\\
	D_-(R_1,R_2,\ldots,R_n)&amp;=\frac12\,\seqnum{A109190}(n),\label{Theo3e3}\\
	D_+(R_1,R_2,\ldots,R_n)&amp;=(-1)^{n-1}M_{n-2}, \quad n \geq 2, \label{Theo3e4}\\
	D_+(R_3,R_4,\ldots,R_{n+2})&amp;=(-1)^{n-1}M_{n-2}, \quad n \geq 3, \label{Theo3e5}
\end{align}
	which hold for $n \geq 1$ unless stated otherwise.
\end{theorem}
\begin{theorem}\label{Theo4} We have
\begin{align}
	D_-(L_1,L_2,\ldots,L_{n})&amp;=\seqnum{A059738}(n-1),\label{Theo4e1}\\
	D_+(L_1,L_2,\ldots,L_n)&amp;=(-1)^{n-1}M_{n-1}, \label{Theo4e2}\\
	D_-(L_2,L_3,\ldots,L_{n+1})&amp;=u_n,\label{Theo4e3}\\
	D_+(L_2,L_3,\ldots,L_{n+1})&amp;=(-1)^{n-1}M_{n-2}, \quad n \geq 2, \label{Theo4e4}
\end{align}
which hold for $n \geq 1$ unless stated otherwise, where $u_n$ denotes the sequence satisfying 	\begin{equation*}
u_n=4u_{n-1}+M_{n-2}+2\sum_{i=0}^{n-3}M_iu_{n-2-i}
\end{equation*}
for $n \geq 3$, with $u_1=2$ and $u_2=9$.
\end{theorem}
\begin{proof}
	Proofs similar to those presented above for \eqref{Theo1e1}--\eqref{Theo1e4} may be given for \eqref{Theo3e1}--\eqref{Theo4e4}.  Alternatively, two of the preceding formulas follow from the previous identities and an inversion theorem \cite[Lemma~4]{KP}, which can be paraphrased as follows:

Let $(b_n)_{n\geq0}$ be the sequence defined by $b_n=\det(A_n)$ for $n\geq 1$ with $b_0=1$, where $A_n$ is given by \eqref{DetHess} with $a_0=1$.  Then $a_n=\det(B_n)$ for $n \geq 1$, where $B_n$ is the Hessenberg--Toeplitz matrix associated with $b_0,\ldots,b_n$.
	
Note that formulas \eqref{Theo3e1} and \eqref{Theo4e2} then follow respectively from \eqref{Theo1e1} and \eqref{Theo1e3} since
	\begin{align*}
	&amp;D_+(M_0,\ldots,M_{n-1})=(-1)^{n-1}R_{n-1} \text{ if and only if }\\ &amp;D_-(R_0,\ldots,R_{n-1})=D_+(R_0,-R_1,\ldots,(-1)^{n-1}R_{n-1})=M_{n-1}
	\end{align*}
	and
	\begin{align*}
	&amp;D_+(L_1,\ldots,L_n)=(-1)^{n-1}M_{n-1} \text{ if and only if }\\
	&amp;D_-(M_0,\ldots,M_{n-1})=D_+(M_0,-M_1,\ldots,(-1)^{n-1}M_{n-1})=L_n.
	\end{align*}
\end{proof}

The sequence \seqnum{A109190} used in formula \eqref{Theo3e3} above for $D_-(R_1,\ldots,R_n)$ was conjectured previously by Mathar to satisfy a certain linear fourth-order recurrence (see discussion in the OEIS entry).  We close this section by providing a proof of this conjectured recurrence.
\begin{proposition}\label{Prop1}
	The sequence $a_n=\seqnum{A109190}(n)$ is given recursively by
	\begin{equation}\label{Prop1e1}
	na_n=(4n-3)a_{n-1}+3(n-1)a_{n-2}-2(7n-15)a_{n-3}-12(n-3)a_{n-4}, \quad n \geq 4,
	\end{equation}
	with initial values $a_0=1,a_1=0,a_2=a_3=2$. Hence, if $d_n=D_-(R_1,\ldots,R_n)$, then $d_n$ satisfies the same recurrence for $n \geq 5$, but with initial values $d_1=0$, $d_2=d_3=1$, $d_4=4$.
\end{proposition}
\begin{proof} The second statement follows from the first and \eqref{Theo3e3}, so we need only show the first.  Let
\begin{equation*}
f(x):=\sum_{n\geq0}a_nx^n=\frac{1}{x+\sqrt{1-2x-3x^2}}.
\end{equation*}
Then we have
	\begin{align*}
	&amp;\sum_{n\geq4} \big(na_n-(4n-3)a_{n-1}-3(n-1)a_{n-2}+2(7n-15)a_{n-3}+12(n-3)a_{n-4}\big)x^n\\
	&amp;=x(f'-4x-6x^2)-x(f+4xf'-1-18x^2)-3x^2(f+xf'-1)+2x^3(6f+7xf'-6)\\
	&amp;\quad+12x^4(f+xf')\\
	&amp;=x(1-4x-3x^2+14x^3+12x^4)f'-x(1+3x-12x^2-12x^3)f+x-x^2.
	\end{align*}
Recurrence \eqref{Prop1e1} holds if and only if the last quantity is zero, i.e.,
	\begin{equation}\label{Prop1e2}
	(1-4x-3x^2+14x^3+12x^4)f'=(1+3x-12x^2-12x^3)f+x-1\,.
	\end{equation}
	Now observe that $f'=\left(\frac{1+3x-\sqrt{1-2x-3x^2}}{\sqrt{1-2x-3x^2}}\right)\!f^2$ so that \eqref{Prop1e2} is equivalent to
	\begin{align}
	(1-4x-3x^2+14x^3+12x^4)(1+3x-&amp;\sqrt{1-2x-3x^2})f^2\notag\\
	=(1+3x-12x^2-12x^3)&amp;\sqrt{1-2x-3x^2}f+(x-1)\sqrt{1-2x-3x^2}.\label{Prop1e3}
	\end{align}
	Note the factorization
	$12x^4+14x^3-3x^2-4x+1=(4x^2+2x-1)(3x^2+2x-1)$
	and that $f$ may be rewritten as $f=\frac{x-\sqrt{1-2x-3x^2}}{4x^2+2x-1}$.  Upon clearing fractions, we then have that \eqref{Prop1e3} is equivalent to
	\begin{align*}
	&amp;-(1-2x-3x^2)(1+3x-\sqrt{1-2x-3x^2})(1-2x-2x^2-2x\sqrt{1-2x-3x^2})\\
	&amp;=\big((1+3x-12x^2-12x^3)(x-\sqrt{1-2x-3x^2})+(x-1)(4x^2+2x-1)\big)\sqrt{1-2x-3x^2},
	\end{align*}
	i.e.,
	\begin{align*}
	&amp;-(1-2x-3x^2)\big(1+3x-12x^2-12x^3-(1+4x^2)\sqrt{1-2x-3x^2}\big)\\
	&amp;=-(1-2x-3x^2)(1+3x-12x^2-12x^3)\\
	&amp;\quad+\big(x(1+3x-12x^2-12x^3)+(x-1)(4x^2+2x-1)\big)\sqrt{1-2x-3x^2}\,.
	\end{align*}
	The last equation is easily verified, which completes the proof of \eqref{Prop1e1}.
\end{proof}


\section{Combinatorial proofs}

In this section, we give combinatorial proofs of formulas \eqref{Theo1e1}--\eqref{Theo1e4} and \eqref{Theo3e1}--\eqref{Theo4e4} above.  Before doing so, let us recall the combinatorial interpretations of several integer sequences which we will make use of here and specify some further terminology.  Let $\mathcal{M}_n$ denote the set of lattice paths (called \emph{Motzkin} paths) from the origin to the point $(n,0)$ that never dip below the $x$-axis using $u=(1,1)$, $d=(1,-1)$, and $h=(1,0)$ steps.  Then $M_n=|\mathcal{M}_n|$ for all $n \geq0$, where $\mathcal{M}_0$ is understood to consist of the empty path of length zero. The number of steps in a Motzkin path $\lambda$ will be denoted by $|\lambda|$. A $u$ step ($d$ step) is said to terminate at \emph{height} $j$ if it joins the points $(i-1,j-1)$ and $(i,j)$ (the points $(i-1,j+1)$ and $(i,j)$) for some $i$. By the \emph{level} of an $h$ step within a member of $\mathcal{M}_n$, we are referring to the $y$-coordinate of the two points in the path connected by the $h$.  A \emph{low} $h$ will refer to an $h$ step at level zero (i.e., one that begins and ends on the $x$-axis).  Let $\mathcal{M}_n^*$ denote the subset of $\mathcal{M}_n$ whose members contain no low $h$'s.  Then it is well-known that $|\mathcal{M}_n^*|=R_n$ for all $n \geq 0$ (see, e.g., the discussion in \seqnum{A005043}), and members of $\mathcal{M}_n^*$ are referred to as \emph{Riordan} paths.

A member of $\mathcal{M}_{2n}$ that contains no $h$ steps is called a \emph{Dyck} path (of semilength $n$); i.e., it is a lattice path starting at the origin and terminating on the $x$-axis with $2n$ steps consisting  of $u$'s and $d$'s that never goes below the $x$-axis.  Then $C_n$ enumerates the set $\mathcal{C}_n$ of Dyck paths of semilength $n$. Let $\mathcal{L}_n$ for $n \geq 1$ denote the set of lattice paths starting at the origin and terminating on the line $x=n-1$  using $u$, $d$, and $h$ steps that never go below the $x$-axis (which are referred to as \emph{Motzkin left factors} \cite[p.\ 111]{AS}).  Note that $|\mathcal{L}_n|=L_n$ for all $n \geq 1$.
By an \emph{internal return} within a Motzkin path of length $n$, we mean a point $(i,0)$ on the $x$-axis with $0&lt;i&lt;n$ where a $d$ or $h$ step terminates.  A member of $\mathcal{M}_n$ for which there are no internal returns will be described as being \emph{primitive}. Note that $\lambda \in \mathcal{M}_{n}$ for $n \geq 2$ is primitive if and only if $\lambda=u\lambda'd$ for some $\lambda' \in \mathcal{M}_{n-2}$, with the single member of $\mathcal{M}_1$ also assumed to be primitive.  Finally, a \emph{unit} of a lattice path will refer to a section lying between two consecutive returns to the $x$-axis or to the section lying to the left of the first return.  Thus, a member of $\mathcal{M}_n$ is primitive if and only if it contains exactly one unit.

When computing 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]$, one need consider only those $\sigma$ each of whose cycles when expressed disjointly with the smallest element first in each cycle comprises a set of consecutive integers in increasing order.  Such $\sigma$ are in one-to-one correspondence with the compositions of $n$, upon identifying the various cycle lengths with parts of a composition, and hence they number $2^{n-1}$.  Thus, the determinant sum for a matrix $A_n$ of the form \eqref{DetHess} may be regarded as a weighted sum over the set of compositions of $n$.  In this sum when $a_0=1$, a 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.  The sign of a composition is then given by $(-1)^{n-m}$, where $m$ denotes the number of its parts.  On the other hand, when $a_0=-1$, every part of size $r$ is weighed by $a_r$ and each term in the determinant sum for $A_n$ is non-negative assuming $a_i \geq 0$ for $i \geq 1$.  Equivalently, when one computes $\det(A_n)$ where $a_0=-1$, one is in fact finding the permanent of the matrix obtained from $A_n$ by replacing $a_0=-1$ with $a_0=1$.  For other examples of weighted composition sums with combinatorial weights, see, e.g., \cite{MS} as well as the related literature on $n$-color compositions.

To find a combinatorial explanation of a purported formula for $\det(A_n)$ when $a_0=1$, we make frequent use of sign-changing involutions defined on a (signed) structure $S$ whose sum of signs coincides with $\det(A_n)$, which has the effect of cancelling out some of the terms in the formula.  We then show that the sum of the signs of the remaining unpaired members of $S$ (often referred to as the set of \emph{survivors} of the involution) is given by the formula for $\det(A_n)$, which is clear in several instances or requires a further enumeration in others.  When $a_0=-1$, then all terms in the expansion of $\det(A_n)$ are non-negative and some structure $T$ is found whose cardinality is seen to coincide with $\det(A_n)$. An expression for the cardinality of $T$ is subsequently found establishing its equality with $\det(A_n)$, which is done by a direct enumeration and/or bijection.

We now provide combinatorial proofs of the formulas from Theorems \ref{Theo1}, \ref{Theo3}, and \ref{Theo4} above.

\subsection{Proof of Eq.~\eqref{Theo1e1}}

We first develop a combinatorial interpretation for $D_+(M_0,\ldots,M_{n-1})$.  Let $\sigma$ denote a composition of $n$ with parts $\sigma_1,\ldots,\sigma_m$ for some $m \geq 1$.  For each part $\sigma_i$, we overlay a lattice path $\lambda_i \in \mathcal{M}_{\sigma_i-1}$ followed by an $h$.  We then color any low $h$ within $\lambda_i$ black
and each appended $h$ step white.  Then let $\lambda=\lambda_1h\lambda_2h\cdots\lambda_mh$ be the (colored) Motzkin path obtained as the concatenation of the paths $\lambda_ih$ for $1 \leq i \leq m$.  Let $\mathcal{A}_n$ denote the set of all lattice paths that arise when one considers all possible compositions $\sigma$ of $n$.  Define the sign of $\lambda$ as $(-1)^{n-m}$, where $m$ denotes the number of white low $h$ steps of $\lambda$ (equivalently, the number of parts in the underlying composition $\sigma$).  Then, by the interpretation of the determinant of a Hessenberg--Toeplitz matrix as a (signed) weighted sum over the set of compositions of $n$, we have that $D_+(M_0,\ldots,M_{n-1})$ gives the sum of the signs of all members of $\mathcal{A}_n$.

Note that members of $\mathcal{A}_n$ must end in a white $h$ step.  We then define a sign-changing involution on $\mathcal{A}_n$ by switching the color of the rightmost non-terminal low $h$ step.  This operation is not defined on the subset $\mathcal{A}_n^*$ of $\mathcal{A}_n$ consisting of those paths whose only low $h$ step is the terminal (white) $h$.  Note that members of $\mathcal{A}_n^*$ and $\mathcal{M}_{n-1}^*$ are clearly synonymous, upon deleting the terminal $h$, with each member of $\mathcal{A}_n^*$ having sign $(-1)^{n-1}$.  Thus, we get $D_+(M_0,\ldots,M_{n-1})=(-1)^{n-1}R_{n-1}$.  To establish the other formula in \eqref{Theo1e1}, we must show equivalently for all $n \geq 0$ that $R_n=\sum_{k=0}^n(-1)^k {n\choose k}C_{n-k}$.  Let $\mathcal{B}_n$ denote the subset of $\mathcal{C}_n$ consisting of those lattice paths $\rho=\rho_1\rho_2\cdots \rho_{2n} \in \mathcal{C}_n$ such that $\rho_{2i-1}\rho_{2i} \neq ud$ for all $1 \leq i \leq n$, i.e., there are no peaks at odd height.  By an inclusion-exclusion argument considering the number $k$ of peaks at odd height within a member of $\mathcal{C}_n$, we have $|\mathcal{B}_n|=\sum_{k=0}^n(-1)^k {n\choose k}C_{n-k}$.  On the other hand, by the bijection from \cite{Cal} between $\mathcal{B}_n$ and $\mathcal{M}_n^*$ (see also \cite{Tir}), we have $|\mathcal{B}_n|=R_n$, which completes the proof of \eqref{Theo1e1}.  \hfill \qed

\subsection{Proof of Eq.~\eqref{Theo1e2}}

Let $\sigma$ be a composition of $n$ with parts $\sigma_1,\ldots,\sigma_m$.  On each $\sigma_i$, we overlay $\lambda_i \in \mathcal{M}_{\sigma_i}$ and then let $\lambda=\lambda_1\cdots\lambda_m$.  Further, we mark the final step of each subpath $\lambda_i$ and define the sign of $\lambda$ as $(-1)^{n-m}$.  Let $\mathcal{D}_n$ denote the set of all the members of $\mathcal{M}_n$ so marked.  Then we have that $D_+(M_1,\ldots,M_{n})$ gives the sum of the signs of the members of $\mathcal{D}_n$.  Consider the rightmost non-terminal step that is either a (i) low $h$ or (ii) $d$ step terminating on the $x$-axis. We then either mark this step if it is unmarked or remove the marking from it if marked.  This operation yields an involution on $\mathcal{D}_n$ that is not defined on the primitive members of $\mathcal{D}_n$, which number $M_{n-2}$ and are each of sign $(-1)^{n-1}$.  This establishes the first formula in \eqref{Theo1e2}. For the second, we show equivalently that $M_{n-1}=\sum_{k=0}^{n-1}(-1)^k  {n-1\choose k}C_{n-k}$, upon replacing $n$ by $n+1$.  Let $\mathcal{E}_n$ denote the set of Dyck paths $\rho=\rho_1\rho_2\cdots \rho_{2n} \in \mathcal{C}_n$ in which $\rho_{2i}\rho_{2i+1}\neq ud$ for all $1 \leq i \leq n-1$.  By an inclusion-exclusion argument, we have $|\mathcal{E}_n|=\sum_{k=0}^{n-1}(-1)^k  {n-1\choose k} C_{n-k}$.  By the bijection from \cite{Cal}, we have $|\mathcal{E}_n|=M_{n-1}$, as desired, which completes the proof.  \hfill \qed


\subsection{Proof of Eq.~\eqref{Theo1e3}}

Let $\mathcal{A}_n$ be as in the proof above for \eqref{Theo1e1}.  Note that, by changing each $1$ to $-1$ along the superdiagonal of $A_n(1;M_0,\ldots,M_{n-1})$, one introduces an extra sign factor to each term in the determinant expansion of $D_+(M_0,\ldots,M_{n-1})$ that is equal to the sign of the member of $\mathcal{A}_n$ corresponding to the term.  Thus, $D_-(M_0,\ldots,M_{n-1})$ gives $|\mathcal{A}_n|$ instead of the sum of the signs of members of $\mathcal{A}_n$.  Let $\mathcal{M}_{n}'$ denote the set of colored Motzkin paths of length $n$ in which each low $h$ comes in one of two colors (say blue and green).  Then members of $\mathcal{A}_{n+1}$ are synonymous with members of $\mathcal{M}_n'$, and to establish the first formula, it suffices to define a bijection between $\mathcal{M}_n'$ and $\mathcal{L}_{n+1}$ for $n \geq 0$. Given $\rho \in \mathcal{M}_n'$, replace each green low $h$  with $u$, leaving all other steps the same and ignoring the coloring of any blue $h$.  Let $\widetilde{\rho}$ denote the resulting lattice path and note that $\widetilde{\rho} \in \mathcal{L}_{n+1}$.  Then the mapping $\rho \mapsto \widetilde{\rho}$ is reversible, upon considering the final height $t$ of $\widetilde{\rho}$ and the rightmost $u$ step terminating at a height $i$ for $1 \leq i \leq t$.  Thus, we have $|\mathcal{M}_n'|=L_{n+1}$, which implies the first formula in \eqref{Theo1e3}.

For the second formula in \eqref{Theo1e3}, we show
\begin{equation}\label{Theo1e3p1}
|\mathcal{M}_n'|=\sum_{k=0}^n(-1)^{n-k}(2k+1) {n\choose k}C_k, \qquad n \geq 0.
\end{equation}
Note that the right side of \eqref{Theo1e3p1} may be rewritten as
	\begin{equation*}
	\sum_{k=0}^n(-1)^{k}(2(n-k)+1) {n\choose k}C_{n-k}=2n\sum_{k=0}^{n-1}(-1)^k {n-1\choose k}C_{n-k}+\sum_{k=0}^n(-1)^k {n\choose k}C_{n-k}.
	\end{equation*}
In the combinatorial proofs of \eqref{Theo1e1} and \eqref{Theo1e2} above, it was seen that 	\begin{equation*}\sum_{k=0}^{n-1}(-1)^k {n-1\choose k}C_{n-k}=M_{n-1} \quad\text{and}\quad
\sum_{k=0}^n(-1)^k {n\choose k}C_{n-k}=R_n.
\end{equation*}
Thus, to establish \eqref{Theo1e3p1}, we need to show
\begin{equation}\label{Theo1e3p2}
|\mathcal{M}_n'|=2nM_{n-1}+R_n, \quad n \geq 0.
\end{equation}

Since there are $R_n$ members of $\mathcal{M}_n'$ that contain no low $h$'s, to show \eqref{Theo1e3p2}, we must argue that there are $2nM_{n-1}$ members of $\mathcal{M}_{n}'$ that contain at least one low $h$.  Clearly, we may assume $n \geq 1$ in \eqref{Theo1e3p2}.  Let $\mathcal{J}_n$ denote the set of Motzkin paths of length $n$ wherein there is at least one $h$ step (at any level) such that exactly one of the $h$ steps is colored either blue or green.  Upon choosing the color and relative position of the colored $h$, we have $|\mathcal{J}_n|=2nM_{n-1}$.  Let $\mathcal{K}_n$ denote the subset of $\mathcal{M}_n'$ whose members contain at least one low $h$.  To complete the proof of \eqref{Theo1e3p2}, it suffices to define a bijection between $\mathcal{J}_n$ and $\mathcal{K}_n$.
\begin{figure}[htp]
	\hfil\scalebox{1.31}
{	\begin{picture}(360,50)
{
\linethickness{0.0025mm}
\multiput(0,0)(10,0){36}{\line(0,1){50}}
\multiput(0,0)(0,10){6}{\line(1,0){350}}
\linethickness{0.55mm}
\put(0,0){\line(1,1){10}}
\put(10,10){\line(1,-1){10}}
\put(20,0){\line(1,0){10}}
{\color{red}\put(30,0){\line(1,1){10}}}
\put(40,10){\line(1,1){10}}
\put(50,20){\line(1,0){10}}
\put(60,20){\line(1,-1){10}}
{\color{red}\put(70,10){\line(1,1){10}}}
\put(80,20){\line(1,1){10}}
\put(90,30){\line(1,-1){10}}
{\color{blue}\put(100,20){\line(1,0){10}}}
\put(110,20){\line(1,1){20}}
\put(130,40){\line(1,-1){10}}
\put(140,30){\line(1,0){20}}
\put(160,30){\line(1,1){10}}
\put(170,40){\line(1,-1){20}}
{\color{red}\put(190,20){\line(1,-1){10}}}
\put(200,10){\line(1,1){10}}
\put(210,20){\line(1,0){20}}
\put(230,20){\line(1,-1){10}}
\put(240,10){\line(1,0){10}}
\put(250,10){\line(1,1){10}}
\put(260,20){\line(1,-1){10}}
\put(270,10){\line(1,0){10}}
{\color{red}\put(280,10){\line(1,-1){10}}}
\put(290,0){\line(1,0){10}}
\put(300,0){\line(1,1){10}}
\put(310,10){\line(1,0){10}}
\put(320,10){\line(1,-1){10}}
\put(330,0){\line(1,0){10}}
}
\end{picture}
}\caption{Decomposition of colored Motzkin path $\lambda \in \mathcal{J}_{34}$}\label{fig1}
\end{figure}

In order to do so, we consider the level $\ell$, where $\ell \geq 0$, of the colored $h$ within $\lambda \in \mathcal{J}_n$.  Then $\lambda$ can be decomposed as
\begin{equation}\label{Thero1e3p3}
\lambda= \begin{cases}
\rho_0u\cdots\rho_{\ell-1}u\rho_\ell\underline{h}\rho_\ell'd\cdots\rho_1'd\rho_0', &amp; \text{if $\ell\geq 1$;}\\
\rho_0\underline{h}\rho_0', &amp; \text{if $\ell=0$,}
\end{cases}
\end{equation}
where $\rho_0,\ldots,\rho_\ell,\rho_0',\ldots,\rho_\ell'$ are all (possibly empty) Motzkin paths and the colored $h$ is underlined. Pictured above in Figure \ref{fig1} is the decomposition of $\lambda \in \mathcal{J}_n$ where $n=34$ and $\ell=2$, in which the $\rho_i$ and $\rho_i'$ sections for $0 \leq i \leq 2$ are separated by red $u$ and by red $d$ steps, respectively, and the colored $h$ is blue as indicated.  We transform $\lambda$ as given in \eqref{Thero1e3p3} to a member of $\mathcal{K}_n$ as follows.  First replace each $u$ directly preceding a $\rho_i$ section with an $h$ of the same color as that of the underlined $h$ in $\lambda$ and do the same for each $d$ directly following some $\rho_j'$.  For each $\rho_i$ and $\rho_j'$ where $0 \leq i,j \leq \ell$, we color all low $h$ steps contained therein with the color not used for the underlined $h$.  Finally, we keep the color of the underlined $h$ in $\lambda$ the same (deleting the underlining).  Let $\lambda'$ denote the resulting lattice path and one may verify $\lambda' \in \mathcal{K}_n$.  Further, it must be the case that at least one of the colors is applied to an odd number of $h$ steps in $\lambda'$ as an equal number of $u$ and $d$ in $\lambda$ were converted to $h$ with the same color as that of the underlined $h$.  Pictured in Figure \ref{fig2} is $\lambda' \in \mathcal{K}_{34}$ corresponding to the $\lambda$ illustrated above.
\begin{figure}[htp]
	\hfil\scalebox{1.31}
{	\begin{picture}(360,30)
{
\linethickness{0.0025mm}
\multiput(0,0)(10,0){36}{\line(0,1){30}}
\multiput(0,0)(0,10){4}{\line(1,0){350}}
\linethickness{0.55mm}
\put(0,0){\line(1,1){10}}
\put(10,10){\line(1,-1){10}}
{\color{green}\put(20,0){\line(1,0){10}}}
\hspace{-0.276cm}
{\color{blue}\put(30,0){\line(1,0){10}}}
\put(40,0){\line(1,1){10}}
\put(50,10){\line(1,0){10}}
\put(60,10){\line(1,-1){10}}
{\color{blue}\put(70,0){\line(1,0){10}}}
\put(80,0){\line(1,1){10}}
\put(90,10){\line(1,-1){10}}
{\color{blue}\put(100,0){\line(1,0){10}}}
\put(110,0){\line(1,1){20}}
\put(130,20){\line(1,-1){10}}
\put(140,10){\line(1,0){20}}
\put(160,10){\line(1,1){10}}
\put(170,20){\line(1,-1){20}}
{\color{blue}\put(190,0){\line(1,0){10}}}
\put(200,0){\line(1,1){10}}
\put(210,10){\line(1,0){20}}
\put(230,10){\line(1,-1){10}}
{\color{green}\put(240,0){\line(1,0){10}}}
\put(250,0){\line(1,1){10}}
\put(260,10){\line(1,-1){10}}
{\color{green}\put(270,0){\line(1,0){10}}}
\hspace{-0.276cm}
{\color{blue}\put(280,0){\line(1,0){10}}}
\hspace{-0.276cm}
{\color{green}\put(290,0){\line(1,0){10}}}
\put(300,0){\line(1,1){10}}
\put(310,10){\line(1,0){10}}
\put(320,10){\line(1,-1){10}}
{\color{green}\put(330,0){\line(1,0){10}}}
}
\end{picture}
}\caption{The corresponding $\lambda' \in \mathcal{K}_{34}$}\label{fig2}
\end{figure}

Let $\mathcal{K}_n^{(e,o)}$ denote the subset of $\mathcal{K}_n$ for which there are an even number of blue $h$ and an odd number of green $h$ steps, with the obvious analogous meanings for $\mathcal{K}_n^{(o,e)}$, $\mathcal{K}_n^{(e,e)}$, and $\mathcal{K}_n^{(o,o)}$. Let $\mathcal{J}_n^{(1)}$ and $\mathcal{J}_n^{(2)}$ denote the subsets of $\mathcal{J}_n$ in which the colored $h$ step is blue or green, respectively.  Then the mapping $\lambda \mapsto \lambda'$ is reversible when restricted to either $\mathcal{J}_n^{(1)}$ or $\mathcal{J}_n^{(2)}$ and hence yields a bijection between the sets $\mathcal{J}_n^{(1)}$ and $\mathcal{K}_n^{(o,e)}\cup\mathcal{K}_n^{(o,o)}$ as well as between $\mathcal{J}_n^{(2)}$ and $\mathcal{K}_n^{(e,o)}\cup\mathcal{K}_n^{(o,o)}$.  Thus, we get
\begin{equation}\label{Thero1e3p4}
|\mathcal{J}_n|=|\mathcal{J}_n^{(1)}|+|\mathcal{J}_n^{(2)}|=|\mathcal{K}_n^{(e,o)}|+|\mathcal{K}_n^{(o,e)}|+2|\mathcal{K}_n^{(o,o)}|.
\end{equation}
Now we have $|\mathcal{K}_n^{(e,e)}|=|\mathcal{K}_n^{(o,o)}|$, upon changing the color of the rightmost low $h$ step within a member of $\mathcal{K}_n^{(e,e)}$ or $\mathcal{K}_n^{(o,o)}$.  Note that since each member of $\mathcal{K}_n$ contains at least one low $h$, the preceding operation is well-defined and bijective.  Thus, $|\mathcal{K}_n^{(e,e)}|=|\mathcal{K}_n^{(o,o)}|$, together with \eqref{Thero1e3p4}, implies $|\mathcal{J}_n|=|\mathcal{K}_n|$, as desired, which completes the proof. \hfill \qed

\subsection{Proof of Eq.~\eqref{Theo1e3b}}

Let $\mathcal{D}_n$ be as in the proof of \eqref{Theo1e2} and it is seen that $D_-(M_1,\ldots,M_n)=|\mathcal{D}_n|$.  Let $d_n=2|\mathcal{D}_n|$ for $n \geq 1$ with $d_0=1$ so that $d_n$ enumerates the set of all marked Motzkin paths of length $n$ wherein some subset (possibly empty) of the returns to the $x$-axis (including the final return) is marked. We make use of the \emph{symbolic} enumeration method (see, e.g., \cite{FS}) and let $D=D(x):=\sum_{n\geq0}d_nx^n$. We then have $D=1+2xD+2x^2DM$, where $M=M(x)$, which follows from considering whether a nonempty lattice path $\sigma$ counted by $D$ can be expressed as $\sigma=h\sigma'$ or $\sigma=u\tau d\sigma''$ such that $\sigma',\sigma''$ are paths of the form enumerated by $d_n$ and $\tau$ is a Motzkin path. (Equivalently, we have the combinatorial recurrence $d_n=2d_{n-1}+2\sum_{i=0}^{n-2}M_id_{n-2-i}$ for $n \geq 2$, with $d_0=1$ and $d_1=2$.)  Solving for $D$ gives
\begin{equation*}
	D=\frac{1}{1-2x-2x^2M}=\frac{1}{\sqrt{1-2x-3x^2}-x}=\sum_{n\geq0}\seqnum{A111961}(n)x^n,
\end{equation*}
which implies \eqref{Theo1e3b}. \hfill \qed


\subsection{Proof of Eq.~\eqref{Theo1e4}}

Given $n \geq 2$ and $1 \leq k \leq n$, let $\mathcal{G}_{n,k}$ denote the set of $k$-tuples $(\lambda_1,\ldots,\lambda_k)$, where each $\lambda_i$ is a Motzkin path of length at least two and $\sum_{i=1}^k|\lambda_i|=n+k$.  Define the sign of $\lambda \in \mathcal{G}_{n,k}$ as $(-1)^{n-k}$ and let $\mathcal{G}_n=\cup_{k=1}^n\mathcal{G}_{n,k}$.  Then $D_+(M_2,\ldots,M_{n+1})$ gives the sum of the signs of all members of $\mathcal{G}_n$. To prove \eqref{Theo1e4}, we define a sign-changing involution on $\mathcal{G}_n$ in several steps as follows.  Throughout, we let $\lambda=(\lambda_1,\ldots,\lambda_k)$ denote a member of $\mathcal{G}_{n,k}$ for some $k \in [n]$.

First suppose that the last step of $\lambda_k$ is $h$, with $\lambda_k=\omega h$ for some nonempty Motzkin path $\omega$.  If $|\lambda_k|\geq 3$, then replace the final component $\lambda_k$ of $\lambda$ with the two components $\lambda_k=\omega$ and $\lambda_{k+1}=h^2$.  If $|\lambda_k|=2$, whence $\lambda_k=h^2$ and $n \geq 2$ implies $k \geq 2$, then delete the final component of $\lambda$ and append an $h$ to the path $\lambda_{k-1}$.  These two operations, taken together, define a sign-changing involution on the subset of $\mathcal{G}_n$ consisting of those members in which the final step of the final component path is an $h$, and thus their contribution towards the determinant $D_+(M_2,\ldots,M_{n+1})$ is zero.

Henceforth, assume that the final component $\lambda_k$ within $\lambda$ ends in $d$.  First suppose $\lambda_k$ has one of the following four forms, where $|\lambda_k|\geq 3$ and $k \geq 1$:
\begin{align*}
(\text{i})~&amp;\lambda_k=h\alpha, \text{ where } \alpha \text{ contains no low } h\text{'s},\\
(\text{ii})~&amp;\lambda_k=h^2\beta, \text{ where } \beta \text{ contains no low } h\text{'s},\\
(\text{iii})~&amp;\lambda_k=u\gamma d, \text{ where } \gamma \text{ is a Motzkin path that has at least one low } h, \\
(\text{iv})~&amp;\lambda_k \text{ has no low } h, \text{ but does have at least one internal return to the $x$-axis}.
\end{align*}
Note that in case (iii), the lattice path $\lambda_k$ has no internal returns to the $x$-axis, but contains an $h$ at level one.  We divide the case when $|\lambda_k|=2$, and hence $\lambda_k=ud$ with $k \geq 2$, into the following four subcases based on the penultimate component $\lambda_{k-1}$:
\begin{align*}
(\text{a})~&amp;\lambda_{k-1} \text{ does not contain a low } h,\\
(\text{b})~&amp;\lambda_{k-1}=h\delta, \text{ where } \delta \text{ does not contain a low } h,\\
(\text{c})~&amp;\lambda_{k-1}=h\delta, \text{ where } \delta \text{ contains a low } h,\\
(\text{d})~&amp;\lambda_{k-1} \text{ starts with } u \text{ and has a low } h.
\end{align*}

We now pair cases (i)--(iv) with (a)--(d), respectively, as follows. If (i) occurs, then delete the initial $h$ from $\lambda_k$ and replace $\lambda_k$ with the two components $\lambda_k=\alpha$ and $\lambda_{k+1}=ud$.  If (ii) holds, then replace $\lambda_k=h^2\beta$ with the components $\lambda_k=h\beta$ and $\lambda_{k+1}=ud$.  If (iii), then replace $\lambda_k=u\gamma d$ with $\lambda_k=h\gamma$ and $\lambda_{k+1}=ud$.  Finally, if (iv), then consider the decomposition $\lambda_k=\rho'\rho''$, where $\rho'$ and $\rho''$ are both nonempty, $\rho'$ contains no low $h$'s and $\rho''$ is primitive.  Further, let $\rho''=u\sigma d$, where $\sigma$ is possibly empty with no restrictions.  In this case, we replace the final component $\lambda_k$ with $\lambda_k=\rho'h\sigma$ and $\lambda_{k+1}=ud$. Moreover, it is understood in each case that all other components of $\lambda$ are to remain unchanged.   Then it is seen that each of the four mappings described above is reversible and changes the sign as the number of components increases by one in each case.  Note that in order to reverse the mapping for case (iv), one needs to consider the position of the leftmost low $h$ in the penultimate component within a member of $\mathcal{G}_n$ for which (d) above applies.

So the remaining cases for when $\lambda_k$ ends in $d$ are as follows:
\begin{align*}
\text{(I)}~&amp;\lambda_k \text{ contains a low } h, \text{ with the last low } h \text{ occurring in the third step or beyond},\\
\text{(II)}~&amp;\lambda_k \text{ is primitive and has no } h \text{ at level one, with } |\lambda_k|&gt;2 \text{ and } k \geq 2,\\
\text{(III)}~&amp;k=1 \text{ and } \lambda_1 \in \mathcal{M}_{n+1} \text{ is primitive and has no } h \text{ at level one}.
\end{align*}
We pair members of $\mathcal{G}_n$ for which (I) or (II) applies as follows.  If (I), then write $\lambda_k=\tau h \tau'$, where $|\tau|\geq 2$ and $\tau'$ contains no low $h$'s.  Note that the assumption that $\lambda_k$ ends in $d$ implies $\tau' \neq \emptyset$.  We then replace  $\lambda_k=\tau h \tau'$ with the two components $\lambda_k=\tau$ and $\lambda_{k+1}=u\tau'd$, keeping all other components of $\lambda$ the same.  Note that $\lambda_{k+1}$ is primitive and has no $h$ at level one since $\tau'$ does not contain a low $h$, whence (II) holds for the resulting member of $\mathcal{G}_n$.  Further, this operation is seen to be reversible and always changes the sign.

Thus, each member of $\mathcal{G}_n$ has been paired with another of opposite sign except for those where (III) above applies, each of which has sign $(-1)^{n-1}$.  Upon deleting the initial $u$ and the final $d$, members of $\mathcal{G}_n$ in (III) are synonymous with Riordan paths of length $n-1$.  This implies $D_+(M_2,\ldots,M_{n+1})=(-1)^{n-1}R_{n-1}$ for $n \geq 2$, as desired. \hfill \qed

\subsection{Proofs of Eqs.~\eqref{Theo3e1}--\eqref{Theo3e4}}

To show \eqref{Theo3e1}, let $\mathcal{A}_n$ be as in the proof of \eqref{Theo1e1} and note that $D_-(R_0,\ldots,R_{n-1})$ enumerates the subset $\mathcal{A}_n'$ of $\mathcal{A}_n$ consisting of those $\lambda=\lambda_1h\cdots \lambda_mh$ in which each $\lambda_i$ is a Riordan path.  Upon deleting the final $h$, one may identify members of $\mathcal{A}_n'$ with members of $\mathcal{M}_{n-1}$, which yields \eqref{Theo3e1}.  For \eqref{Theo3e2}, first note that $D_+(R_0,\ldots,R_{n-1})$ gives the sum of the signs of the members of $\mathcal{A}_n'$, where the sign is defined as $(-1)^{n-m}$.  Equivalently, we have that $(-1)^nD_+(R_0,\ldots,R_n)$ equals the sign-balance of the low $h$ statistic on $\mathcal{M}_n$, i.e.,
\begin{equation*}
	(-1)^nD_+(R_0,\ldots,R_n)=\sum_{\pi \in \mathcal{M}_n}(-1)^{\mu(\pi)}:=v_n, \qquad n \geq 1,
\end{equation*}
with $v_0=1$, where $\mu(\pi)$ denotes the number of low $h$'s in $\pi$.  Let $V=V(x):=\sum_{n\geq0}v_nx^n$.  Considering whether a nonempty Motzkin path starts with $h$ or $u$ gives $V=1-xV+x^2MV$, and hence
	\begin{equation*}
	V=\frac{1}{1+x-x^2M}=\frac{2}{1+3x+\sqrt{1-2x-3x^2}}.
	\end{equation*}
A comparison with the generating function formula for \seqnum{A344507} then implies \eqref{Theo3e2}.

For \eqref{Theo3e3}, first let $e_n=2D_-(R_1,\ldots,R_n)$ for $n \geq 1$, with $e_0=1$. Then $e_n$ enumerates members of $\mathcal{M}_n^*$ in which returns to the $x$-axis may be marked.  By dropping the restriction that a member of $\mathcal{M}_n$ cannot go below the $x$-axis, one obtains the class of lattice paths known as the \emph{Grand Motzkin paths}, denoted by $\mathcal{GM}_n$.  Then it is known that $\seqnum{A109190}(n)$ enumerates the subset of $\mathcal{GM}_n$ consisting of those members with no $h$ steps at level zero.  By reflecting in the $x$-axis each unit to the left of a marked return within a marked member of $\mathcal{M}_n^*$, it is seen that $e_n$ also enumerates the aforementioned subset of $\mathcal{GM}_n$. Hence, $e_n=\seqnum{A109190}(n)$ for all $n \geq 0$, which implies \eqref{Theo3e3}.  Finally, note that the proof above for the first part of \eqref{Theo1e2} applies when restricted to the subset of $\mathcal{D}_n$ in which the corresponding $\lambda$ are Riordan paths.  Since this subset contains the set of survivors of the involution, formula \eqref{Theo3e4} follows. \hfill \qed

\subsection{Proof of Eq.~\eqref{Theo3e5}}

Given $n \geq 3$ and $1 \leq k\leq n$, let $\mathcal{H}_{n,k}$ denote the set of $k$-tuples $\lambda=(\lambda_1,\ldots,\lambda_k)$ such that each $\lambda_i$ is a Riordan path of length at least three with $\sum_{i=1}^k|\lambda_i|=n+2k$.  Define the sign of $\lambda \in \mathcal{H}_{n,k}$ as $(-1)^{n-k}$ and let $\mathcal{H}_n=\cup_{k=1}^n\mathcal{H}_{n,k}$.  Then $D_+(R_3,\ldots,R_{n+2})$ is seen to give the sum of the signs of all members of $\mathcal{H}_n$.  We define a sign-changing involution on $\mathcal{H}_n$ in three steps as follows.  First let $\mathcal{H}_n^{(1)}\subseteq \mathcal{H}_n$ comprise those $\lambda=(\lambda_1,\ldots,\lambda_k)$ where $k$ can range over $[n]$ such that either
\begin{itemize}
\item[(i)] $\lambda_k=\alpha\beta$, or
\item[(ii)] $\lambda_k=u\beta d$,
\end{itemize}
where $\alpha$ is any Riordan path with $|\alpha| \geq 3$ and $\beta$ is primitive with $|\beta| \geq 2$ in both cases.  Note, in (ii), that the only return to the line $y=1$ within $\lambda_k$ occurs with the penultimate step.  We exchange cases (i) and (ii) by replacing $\lambda_k$ in (i) with the two components $\lambda_k=\alpha$ and $\lambda_{k+1}=u\beta d$, and vice versa if (ii) holds with $k&gt;1$.  This yields an involution of $\mathcal{H}_{n}^{(1)}$ which always reverses the sign that is not defined on the subset $\widetilde{\mathcal{H}}_{n}^{(1)}$ comprising those members for which $k=1$ and $\lambda_1=u\beta d$, where $\beta$ is as described.  Note that $|\widetilde{\mathcal{H}}_{n}^{(1)}|=M_{n-2}$ since $\beta$ is primitive and hence of length at least three (as $k=1$), with each member of $\widetilde{\mathcal{H}}_{n}^{(1)}$ having sign $(-1)^{n-1}$.

Next, let $\mathcal{H}_n^{(2)}$ consist of those $\lambda=(\lambda_1,\ldots,\lambda_k)$ in $\mathcal{H}_n$ where $k$ can vary such that either (i) $\lambda_k=u\alpha d$, where $\alpha$ is a Motzkin path that has at least one internal return to the $x$-axis and does not end in $h$, or (ii) $\lambda_k=ud\beta$, where $\beta$ is primitive.  Note that $\lambda_k$ a Riordan path implies $|\beta| \geq 2$ in (ii).  Further, in (i), we let $\alpha=\alpha'\alpha''$, where $\alpha''$ is primitive.  Then, by the assumptions on $\alpha$, we have $\alpha' \neq \emptyset$ and $|\alpha''| \geq 2$.  We now exchange cases (i) and (ii) as follows. If (i) holds, then replace $\lambda_k=u\alpha'\alpha''d$ with $\lambda_k=u\alpha'd$ and $\lambda_{k+1}=ud\alpha''$, keeping all other components of $\lambda$ the same.  If (ii) holds, along with the further assumptions that $k \geq 2$ and $\lambda_{k-1}$ be primitive, then we reverse the operation just described.

Thus, at this point, we have paired each member of $\mathcal{H}_n^{(2)}$ with another of opposite sign except for those satisfying condition (ii) with $k=1$ or with $k \geq 2$ such that $\lambda_{k-1}$ is not primitive.  If the latter holds, then write $\lambda_{k-1}=\sigma\sigma'$, where $\sigma'$ is primitive (and hence $\sigma \neq \emptyset$). If $|\sigma|\geq 3$, then replace $\lambda_{k-1}=\sigma\sigma'$, $\lambda_k=ud\beta$ with $\lambda_{k-1}=\sigma$, $\lambda_k=ud\sigma'$ and $\lambda_{k+1}=ud\beta$, where $\beta$ is primitive as before.  If $|\sigma|=2$ and $k \geq 3$, then replace $\lambda_{k-2}=\tau$, $\sigma_{k-1}=ud\tau'$ and $\sigma_k=ud\beta$ with $\lambda_{k-2}=\tau\tau'$ and $\lambda_{k-1}=ud\beta$, where $\tau'$ is primitive.  In either case, we keep all other components of $\lambda$ the same.  This mapping, taken together with the one defined in the preceding paragraph, yields a sign-changing involution on all members of $\mathcal{H}_n^{(2)}$ except for those satisfying condition (ii) with $k=1$ or with $k=2$ such that $\lambda_1=ud\sigma'$, where $\sigma'$ is primitive.

Let $\widetilde{\mathcal{H}}_n^{(2)}$ denote the subset of $\mathcal{H}_n^{(2)}$ for which the involution is not defined.  Note that there are $M_{n-2}$ possibilities for members of $\widetilde{\mathcal{H}}_n^{(2)}$ where $k=1$, each of sign $(-1)^{n-1}$, and $\sum_{i=0}^{n-4}M_iM_{n-4-i}=M_{n-2}-M_{n-3}$ possibilities for members in which $k=2$, each of sign $(-1)^{n-2}$, by the Motzkin number defining recurrence where $i$ in the summation denotes $|\sigma'|-2$.  Thus, the sum of the signs of the members of $\widetilde{\mathcal{H}}_n^{(2)}$ is given by 	
\begin{equation*}
(-1)^{n-1}M_{n-2}+(-1)^{n-2}(M_{n-2}-M_{n-3})=(-1)^{n-1}M_{n-3}.
\end{equation*}
Note that it is a straightforward matter at this point to pair members of $\widetilde{\mathcal{H}}_n^{(2)}$ of opposite sign, if one desires, by considering the standard decomposition of a Motzkin path according to its first return to the $x$-axis.

Now let $\mathcal{H}_n^{(3)}=\mathcal{H}_n-\mathcal{H}_n^{(1)}-\mathcal{H}_n^{(2)}$ and note that $\mathcal{H}_n^{(3)}$ consists of those members $\lambda \in \mathcal{H}_n$ for which the final component $\lambda_k$ is primitive with the last two steps $hd$.  If $|\lambda_k|=3$, i.e., $\lambda_k=uhd$, then $n \geq 3$ implies $k \geq 2$ and we consider whether or not $\lambda_{k-1}$ is primitive.  If it is, then delete $\lambda_k$ and insert an $h$ directly preceding the terminal $d$ step in $\lambda_{k-1}$.  Note that the resulting lattice path is still primitive with length at least four.  If $|\lambda_k|\geq 4$, then remove the penultimate $h$ step from $\lambda_k$ and add the component $\lambda_{k+1}=uhd$.  These two operations together yield an involution of $\mathcal{H}_n^{(3)}$ that is not defined if $\lambda_k=uhd$, with $\lambda_{k-1}$ not primitive.  In this case, we make use of a mapping similar to that employed in the second part of the involution defined above on $\mathcal{H}_n^{(2)}$ in which either the antepenultimate and penultimate components of $\lambda$ were combined or the penultimate component was broken into two as described.  Thus, each $\lambda$ in $\mathcal{H}_n^{(3)}$ is paired with another of opposite sign except for those in which $k=2$  with $\lambda_1=ud\alpha$ and $\lambda_2=uhd$, where $\alpha$ is primitive, the subset of which we denote by $\widetilde{\mathcal{H}}_n^{(3)}$.  Note that $|\widetilde{\mathcal{H}}_n^{(3)}|=M_{n-3}$, with each member of $\widetilde{\mathcal{H}}_n^{(3)}$ having sign $(-1)^{n-2}$.

We have now defined sign-changing involutions on $\mathcal{H}_n^{(i)}$ for $1 \leq i \leq 3$ with respective sets of survivors $\widetilde{\mathcal{H}}_n^{(i)}$.  Hence, the sum of the signs of all members of $\mathcal{H}_n=\cup_{i=1}^3\mathcal{H}_n^{(i)}$ is the same as the sum of the signs of members of $\cup_{i=1}^3\widetilde{\mathcal{H}}_n^{(i)}$.  The contributions from $\widetilde{\mathcal{H}}_n^{(2)}$ and $\widetilde{\mathcal{H}}_n^{(3)}$ to this sum cancel and thus we get $(-1)^{n-1}M_{n-2}$.  Note that it is a straightforward matter to pair the remaining unpaired members of  $\widetilde{\mathcal{H}}_n^{(2)}$ (i.e., those accounted for by $(-1)^{n-1}M_{n-3}$) with the members of $\widetilde{\mathcal{H}}_n^{(3)}$, if desired, as both sets are readily seen to be in one-to-one correspondence with $\mathcal{M}_{n-3}$.  Since $D_+(R_3,\ldots,R_{n+2})$ equals the sum of the signs of all members of $\mathcal{H}_n$, the proof of \eqref{Theo3e5} is complete.  \hfill \qed


\subsection{Proofs of Eqs.~\eqref{Theo4e1} and \eqref{Theo4e2}}

Given a composition $\sigma$ of $n$ with parts $\sigma_1,\ldots,\sigma_m$, we overlay each $\sigma_i$ with a member $\lambda_i \in \mathcal{L}_{\sigma_i}$ followed by an $h$ step.  Then let $\lambda=\lambda_1h\cdots \lambda_mh$ denote the corresponding member of $\mathcal{L}_{n+1}$ wherein we mark each appended $h$.  Let $\mathcal{Q}_n$ denote the set of all $\lambda \in \mathcal{L}_{n+1}$ so marked.  We then have $D_-(L_1,\ldots,L_n)=|\mathcal{Q}_n|$ for all $n \geq 1$.  By a \emph{base} $h$ within a Motzkin left factor, we mean an $h$ step (including possibly a terminal $h$ step) for which there exists no step anywhere to its right that terminates at a strictly lower level.  Upon deleting the final $h$, we may regard the $\lambda \in \mathcal{Q}_n$ as marked members of $\mathcal{L}_n$ in which some subset (possibly empty) of the base $h$'s is marked.

Let $\mathcal{P}_n$ denote the set of tricolored Motzkin paths of length $n$ in which low $h$'s are colored either black, white or red.  Then it is known that $|\mathcal{P}_n|$ is given by $\seqnum{A059738}(n)$ for all $n \geq 0$.  Thus, to complete the proof of \eqref{Theo4e1}, it suffices to define a bijection between $\mathcal{P}_n$ and $\mathcal{Q}_{n+1}$.  To do so, consider replacing each red low $h$ within $\rho \in \mathcal{P}_n$ by $u$ and regard each white low $h$ as being marked.  Let $\rho'$ denote the resulting marked Motzkin left factor.  One may verify that only base $h$'s can be marked in $\rho'$ and hence $\rho' \in \mathcal{Q}_{n+1}$.  Let $t$ denote the final height of a member of $\mathcal{Q}_{n+1}$.  Then the mapping $\rho \mapsto \rho'$ may be reversed by considering the rightmost $u$ step starting from the line $y=i$ for each $0 \leq i \leq t-1$, which completes the proof of \eqref{Theo4e1}.

To show \eqref{Theo4e2}, define the sign of $\lambda \in \mathcal{Q}_{n}$ as $(-1)^{n-\ell}$, where $\ell$ is the number of marked $h$ steps in $\lambda$.  Then $D_+(L_1,\ldots,L_{n})$ equals the sum of the signs of all members of $\mathcal{Q}_n$.  Define an involution on $\mathcal{Q}_n$ by identifying the leftmost non-terminal base $h$ and either marking it or removing the marking from it.  This operation reverses the sign and fails to be defined on the subset $\mathcal{Q}_n^*$ of $\mathcal{Q}_n$ whose members do not contain a base $h$ outside of the terminal base $h$.  Then members of $\mathcal{Q}_n^*$ each have sign $(-1)^{n-1}$ and, by the inverse of the mapping $\rho \mapsto \rho'$ defined above, are equivalent to members of $\mathcal{P}_{n-1}$ in which each low $h$ is red.  As there are clearly $M_{n-1}$ such members of $\mathcal{P}_{n-1}$, formula \eqref{Theo4e2} follows. \hfill \qed


\subsection{Proofs of Eqs.~\eqref{Theo4e3} and \eqref{Theo4e4}}

By a \emph{base step} within a Motzkin left factor, we mean a \emph{non-terminal} step for which there exists no step anywhere to its right that terminates at a strictly lower height.  Let $\mathcal{U}_n$ denote the set of marked members of $\mathcal{L}_{n+1}$ in which some subset (possibly empty) of the base steps is marked.  By reasoning similar to that used in the proof of \eqref{Theo4e1}, we have $D_-(L_2,\ldots,L_{n+1})=|\mathcal{U}_n|$ for $n \geq 1$.  Let $u_n=|\mathcal{U}_n|$ and one may verify $u_1=2$ and $u_2=9$, using the definitions. So assume $n \geq 3$ and let $\lambda \in \mathcal{U}_n$.  If $\lambda=u\lambda'$ or $\lambda \in h\lambda'$, where $\lambda' \in \mathcal{U}_{n-1}$, then the first step of $\lambda$ is a base step in either case, which implies $4u_{n-1}$ possibilities altogether.  Now assume $\lambda$ starts with $u$ and returns to the $x$-axis at some point.  Then $\lambda=u\tau d\lambda'$, where $\tau \in \mathcal{M}_i$ and $\lambda'\in \mathcal{U}_{n-2-i}$ for some $i \geq 0$.  If $\lambda'=\emptyset$, then $\lambda$ is primitive and there are no base steps in $\lambda$ since the final step terminates at height zero and all other steps terminate at a positive height.  Hence, there are $M_{n-2}$ possibilities in this case.  If $\lambda'\neq \emptyset$, then the $d$ following the section $\tau$ within $\lambda$ is a base step (with no others to its left).  Considering all $0\leq i\leq n-3$ in this case thus gives $2\sum_{i=0}^{n-3}M_iu_{n-2-i}$ possibilities.  Combining the prior cases then yields the recurrence stated for $u_n$ and completes the proof of \eqref{Theo4e3}.

For \eqref{Theo4e4}, define the sign of a member of $\mathcal{U}_n$ by $(-1)^{n-1-\ell}$, where $\ell$ denotes the number of base steps.  Then $D_+(L_2,\ldots,L_{n+1})$ equals the sum of the signs of the members of $\mathcal{U}_n$.  By either marking or unmarking the leftmost base step, each member of $\mathcal{U}_n$ is paired with another of opposite sign except for those which fail to contain a base step.  From the analysis used to deduce the recurrence for $u_n$, members of $\mathcal{U}_n$ that do not contain a base step are precisely the primitive Motzkin paths and hence they number $M_{n-2}$, each with sign $(-1)^{n-1}$, which implies \eqref{Theo4e4}.  \hfill \qed

\begin{remark} Sequences \seqnum{A111961} and \seqnum{A344507} have apparently only arisen before in algebraic settings and thus the structures used in conjunction with them in the proofs of \eqref{Theo1e3b} and \eqref{Theo3e2} provide the first known combinatorial interpretations of these sequences.  In particular, it was seen that $\seqnum{A111961}(n)$ enumerates Motzkin paths of length $n$ in which some subset of the steps terminating on the $x$-axis (either $d$ or $h$) is marked whereas $\seqnum{A344507}(n)$ corresponds to the sign-balance of the low $h$ statistic on $\mathcal{M}_n$. Further, the proofs of \eqref{Theo3e3} and \eqref{Theo4e1} provide new combinatorial interpretations for the sequences \seqnum{A109190} and \seqnum{A059738}, respectively.
\end{remark}


\begin{thebibliography}{99}

\bibitem{aigner}
M. Aigner,   Motzkin numbers,  \textit{European J. Combin.} \textbf{19} (1998), 663--675.

\bibitem{AS}
L. Alonso and R. Schott, \emph{Random Generation of Trees: Random Generators in Computer Science}, Kluwer Academic Publishers, 1995.

\bibitem{baril}
J.-L. Baril, S. Kirgizov, and A. Petrossian,   Motzkin paths with a restricted first return decomposition,  \textit{Integers} \textbf{19} (2019), \#A46.

\bibitem{barnabei}
M. Barnabei, F. Bonetti, N. Castronuovo, and M. Silimbani, Motzkin and Catalan tunnel polynomials, \textit{J. Integer Sequences} \textbf{21} (2018), \,\href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html}{Article 18.8.8}.

\bibitem{Bern}
F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, \textit{Discrete Math.} \textbf{204} (1999), 73--112.

\bibitem{Cal}
D. Callan, Bijections for Dyck paths with all peak heights of the same parity, arxiv preprint arXiv:1702.06150 [math.CO], 2017. Available at \url{https://arxiv.org/abs/1702.06150}.


\bibitem{cameron}
N. T. Cameron and A. C. M. Yip, Hankel determinants of sums of consecutive Motzkin
numbers,  \textit{Linear Algebra  Appl.} \textbf{434} (2011), 712--722.

\bibitem{chang}
X.-K. Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas,  \textit{Electron. J. Combin.} \textbf{19} (2016), \#P1.8.

\bibitem{chen}
W. Y. C. Chen, S. H. F. Yan, and L. L. M. Yang,   Identities from weighted Motzkin paths,  \textit{Adv. in Appl. Math.} \textbf{41} (2008), 329--334.

\bibitem{fang}
W. Fang, A partial order on Motzkin paths, \textit{Discrete Math.} \textbf{343} (2020), 111802.

\bibitem{FS}
P. Flajolet and R. Sedgewick, \emph{Analytic Combinatorics}, Cambridge University Press, 2009.

\bibitem{florez}
R. Fl\'orez, L. Junes, and J. L. Ram\'irez, Further results on paths in an $n$-dimensional cubic lattice, \textit{J. Integer Sequences} \textbf{21} (2018),  \,\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Ferrari/ferrari.html}{Article 18.1.2}.

\bibitem{gan}
L. Gan, S. Ouvry, and A. P. Polychronakos,
Combinatorics of generalized Dyck and Motzkin paths, \textit{Phys. Rev. E.} \textbf{106} (2022), 044123.

\bibitem{GSh-Indian}
T. Goy and M. Shattuck, Determinant formulas of some Toeplitz--Hessenberg matrices with Catalan entries, \textit{Proc. Indian Acad. Sci. Math. Sci.} \textbf{129} (2019), 46.

\bibitem{GSh-NNTDM}
T. Goy and M. Shattuck, Determinants of  Toeplitz--Hessenberg matrices with generalized Fibonacci entries, \textit{Notes Number Theory  Discrete Math.} \textbf{25} (2019), 83--95.

\bibitem{GSh-Trans}
T. Goy and M. Shattuck, Determinant identities for Toeplitz--Hessenberg matrices with tribonacci numbers entries, \textit{Trans. Comb.} \textbf{9} (2020), 89--109.

\bibitem{GSh-JIS}
T. Goy and M. Shattuck, Some Toeplitz--Hessenberg determinant identities for the tetranacci numbers, \textit{J. Integer Sequences} \textbf{23} (2020), \,\href{https://cs.uwaterloo.ca/journals/JIS/VOL23/Shattuck/shattuck20.html}{Article 20.6.8}.

\bibitem{KP}
T. Komatsu and J. L. Ram\'irez, Some determinants involving incomplete Fubini numbers, \textit{An. \c{S}t. Univ. Ovidius Constan\c{t}a Ser. Mat.} \textbf{26} (2018), 143--170.

\bibitem{MS}
T. Mansour and M. Shattuck, A statistic on $n$-color compositions and related sequences, \textit{Proc. Indian Acad. Sci. Math. Sci.} \textbf{124} (2014), 127--140.

\bibitem{MM1}
M. Merca, A note on the determinant of a Toeplitz--Hessenberg matrix, \textit{Spec. Matrices} \textbf{1} (2013), 10--16.

\bibitem{Muir}
T. Muir, \textit{The Theory of Determinants in the Historical Order of Development}, Vol.~3, Dover Publications, 1960.

\bibitem{oste}
R. Oste and J. Van  der Jeugt, Motzkin paths, Motzkin polynomials and recurrence relations, \textit{Electron. J. Combin.} \textbf{22} (2015), \#P2.8.

\bibitem{sapounakis} A. Sapounakis and P. Tsikouras, On $k$-colored Motzkin words, \textit{J. Integer Sequences} \textbf{7} (2004), \,\href{https://cs.uwaterloo.ca/journals/JIS/VOL7/Tsikouras/tsikouras43.html}{Article 04.2.5}.

\bibitem{shapiro}
L. W. Shapiro and C. J. Wang, A bijection between 3-Motzkin paths and
Schr\"oder paths with no peak at odd height, \textit{J. Integer Sequences} \textbf{12} (2009), \,\href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Shapiro/shapiro7.html}{Article 09.3.2}.

\bibitem{Sl} N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Available at \url{https://oeis.org}, 2022.

\bibitem{Tir}
J. O. Tirrell, \textit{Orthogonal polynomials, lattice paths, and skew Young tableaux}, Ph.D. Thesis, Brandeis Univ., 2016. Available at \url{https://people.brandeis.edu/~gessel/homepage/students/JordanTirrellThesis.pdf}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 05A19; Secondary 11C20, 15B05.


\noindent \emph{Keywords:} Motzkin number, Motzkin path,  Riordan number, Catalan number, Hessenberg--Toeplitz matrix, Trudi's formula, generating function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000108},
\seqnum{A001006},
\seqnum{A005043},
\seqnum{A005773},
\seqnum{A059738},
\seqnum{A109190},
\seqnum{A111961}, and
\seqnum{A344507}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 5 2022;
revised version received March 12 2023.
Published in {\it Journal of Integer Sequences}, March 14 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in





\end{document}



</pre></body></html>