<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{color,picture,atbegshi}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{cite}

\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}

\usepackage{bm}

\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}}}

\newcommand{\A}{{\mathcal A}}
\newcommand{\D}{{\mathcal D}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\F}{{\bm F}}
\newcommand{\V}{{\bm V}}
\newcommand{\G}{{\bm G}}
\newcommand{\Dg}{{\bm D}}
\newcommand{\dt}{{\bm d}}


\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}
\newtheorem{openproblem}[theorem]{Open Problem}



\begin{center}
\vskip 1cm{\Large\bf  Counting Subwords in Non-Decreasing Dyck Paths\\
\vskip 1cm}
Rigoberto Fl\'orez\\
Department of Mathematical Sciences \\
The Citadel\\
Charleston, SC 29409\\
USA\\
\href{mailto:rigo.florez@citadel.edu }{\tt rigo.florez@citadel.edu }\\
\ \\
Leandro Junes\\
Department of Mathematics\\
PennWest California\\
California, PA 15419\\
USA\\
\href{mailto:junes@pennwest.edu}{\tt junes@pennwest.edu}\\
\ \\
Luisa M. Montoya   and Jos\'e L. Ram\'{\i}rez\\
Departamento de Matem\'aticas\\
 Universidad Nacional de Colombia\\
Bogot\'a \\
Colombia\\
\href{mailto:jlmontoyaco@unal.edu.co}{\tt lmontoyaco@unal.edu.co}\\
\href{mailto:jlramirezr@unal.edu.co}{\tt jlramirezr@unal.edu.co}
\end{center}

\vskip .2 in

\begin{abstract}
A Dyck path is \emph{non-decreasing} if the $y$-coordinates of its valleys, which are local minima along the path, form a non-decreasing sequence. To count the number of subpaths (or subwords) within non-decreasing Dyck paths, we use generating functions and recursive relations.  These techniques enable us to count subpaths of various lengths, such as two, three, four, and five, while considering both the length and the number of subwords. Using constructive recursive proofs, we establish a combinatorial interpretation of the counting process, expressing the results as linear combinations of Fibonacci and Lucas numbers. In several cases, we provide new interpretations of sequences from the On-Line Encyclopedia of Integer Sequences (OEIS).
\end{abstract}

\section{Introduction}
A \emph{Dyck path} of semilength $n$ is a lattice path in the first quadrant of the  $xy$-plane that begins at the origin $(0,0)$ and ends at $(2n,0)$, consisting of North-East steps $U = (1, 1)$ and South-East steps $D = (1, -1)$. In a Dyck path $P$, a  \emph{valley} is a subpath of the form $DU$, while a \emph{peak} is a subpath of the form $UD$. Informally, valleys correspond to local minima, and peaks correspond to local maxima. To encode a Dyck path of semilength $n$, we use a word $w=w_1w_2\cdots w_{2n}$ from the alphabet $\{U, D\}$, referred to  as a \emph{Dyck word}. The occurrence of a \emph{subword} $v$ in a Dyck word $w$ means that there exist subwords $u_1$ and $u_2$ from $\{U, D\}^*$ such that $w=u_1vu_2$. For instance, the valleys and peaks can be identified as the subwords $DU$ and $UD$, respectively. In enumerative combinatorics, a  classic problem involves counting the occurrences of a given subword within a combinatorial structure. For example, Deutsch \cite{Deutschenumeration} studied the distribution of subwords of length 2, namely  $UU$, $UD$, $DU$, and $DD$, in the set of Dyck words. The study of subwords of length 3, specifically  $UUU$, $UUD$, $UDU$, $UDD$, $DUU$, $DUD$, $DDU$, and $DDD$, has been explored by various researchers,  including Deutsch \cite{Deutschenumeration}, Mansour \cite{Mansour}, Merlini et al.\ \cite{Merl}, Sapounakis et al.\ \cite{Sapounakis}, and Sun \cite{Sun}.

Barcucci et al.\ \cite{barcucci} introduced the notion of a \emph{non-decreasing} Dyck path, defining it as a Dyck path $P$ where the $y$-coordinates of its valleys form a non-decreasing sequence. Other recent results on this topic can be found in  \cite{CzabarkaFlorezJunes, CzabarkaFlorezJunesJose, DeutschP, ElizaldeFlorezRamirez, FlorezJoseJunesasymmetric, FlorezJoseJunes, FlorezJoseSymmDyck, FlorezJoseTDyck, FlorezJose, MontoyaConde, Prod}. This paper focuses on enumerating subwords of various lengths, including $2$, $3$, $4$, as well as certain general cases. We present our results using generating functions and recursive relations, expressing the formulas as linear combinations of Fibonacci and Lucas numbers. We recall that the Fibonacci sequence is defined by the recurrence relation  
$F_n=F_{n-1}+F_{n-2}$ for $n\ge 2$, with initial values $F_0=0$ and $F_1=1$. Similarly, the Lucas sequence is given by  $L_n=L_{n-1}+L_{n-2}$  for $n\ge 2$, with initial values  $L_0=2$ and $L_1=1$.

Let $\D_n$ denote the set of all non-decreasing Dyck words of length $2n$, and let $\D=\bigcup_{k\geq 1} \D_k$ represent the union of these sets. Barcucci et al.\ \cite{barcucci} proved that $|\D_n|=F_{2n-1}$.

When considering a subword $v\in \{U, D\}^*$, we use $|w|_v$ to denote the number of occurrences of the subword $v$ in $w$, including overlapping instances. To analyze this, we introduce the bivariate generating function $\F_{v}(x,y)$ defined as follows:
$$\F_{v}(x,y)=\sum_{n\geq 1}x^{n}\sum_{w\in \D_n}y^{|w|_v}.$$

Let $\dt_{v}(n)$ denote the total number of occurrences of the subword $v$ in the Dyck words of $\D_n$. The generating function for the sequence $\dt_{v}(n)$ can be obtained by differentiating $\F_{v}(x,y)$ with respect to $y$ and then setting $y=1$ we have 
$$\Dg_{v}(x):=\left.\frac{\partial \F_{v}(x,y) }{\partial y}\right|_{y=1}.$$

A \emph{pyramid} of semi-length $h\geq 1$ in a Dyck word is a subword of the form $U^hD^h$. A pyramid is considered \emph{maximal} and is denoted by $\Delta_h$ if it cannot be extended to a larger pyramid $U^{h+1}D^{h+1}$. That is, if a symbol appears immediately before or after $\Delta_h$, it must be $D$ or $U$, respectively. The empty pyramid is represented by $\Delta_0$. 

Based on the definition of a non-decreasing Dyck word $w$, it can be decomposed using the \emph{first return decomposition}. This decomposition yields three cases: $w=UD$, the minimal word, $w=\Delta v$, or $w=UvD$, where $\Delta \ne \Delta_0$ is a pyramid and $v\in\D$. This decomposition is shown in Figure \ref{Ldecom1}. Here, $|w|$ denotes the length of the word $w$. The first return decomposition leads to the following equation for the generating function $D(x)=\sum_{w\in\D}x^{|w|/2}$:
\begin{equation}\label{eq:D}
D(x)=x+\frac{x}{1-x}D(x) + xD(x).
\end{equation}
By solving this equation, we obtain the generating function for non-decreasing Dyck words of length $2n$:
$$D(x)=\frac{x(1-x)}{1-3x+x^2}=\sum_{n=1}^{\infty} F_{2n-1}x^n.$$

\begin{figure} [h]
\begin{center}
\includegraphics[scale=.9]{decom1.eps}
\end{center}
\caption{Factorization of non-decreasing Dyck paths.} \label{Ldecom1}
\end{figure}

\section{Words of length two}
In this section, we focus on counting the number of subwords of length two in $\D_n$. Czabarka et al. \cite{CzabarkaFlorezJunesJose} obtained the generating function for the subwords $UD$ and $DU$. Therefore, we present their theorems without providing their proofs. However, we introduce new generating functions and recursive relations specifically for the number of subwords of the form $UU$ and $DD$. 

 \begin{theorem} \label{SubPathsUD}  The number of subwords of the form $UD$ in $\D_n$ is counted by
$$\F_{UD}(x,y)=\frac{(1 - x) x y}{1 - 2 x + x^2 - x y} \quad \text{and} \quad \Dg_{UD}(x)=\dfrac{x(1-x)^3}{(1-3x+x^2)^2}.$$
Furthermore, for $n\geq 1$, we have  
$$\dt_{UD}(n)=\frac{1}{10}((5n-7) F_{2n}-(n-5)L_{2n}).$$
\end{theorem}

 \begin{proof}
To derive an expression for $\F_{UD}(x,y)$, we refine Equation~\eqref{eq:D} by introducing a variable $y$ to track the number of occurrences of the subword $UD$ in the word. By applying the same decomposition, we get
\[
\F_{UD}(x,y)=xy+\frac{xy}{1-x}\F_{UD}(x,y)+x\F_{UD}(x,y).
\]
Solving this functional equation yields the expressions for $\F_{UD}(x,y)$.
Since $\dt_{UD}(n)$ corresponds to the number of peaks in $\D_n$, the recursive relation follows from \cite[Theorem 2]{CzabarkaFlorezJunesJose}. The combinatorial formula of $\dt_{UD}(n)$ follows from some Fibonacci identities.
\end{proof}

 \begin{theorem} \label{SubPathsDU}    
 The number of subwords of the form $DU$ in $\D_n$ is counted by
$$\F_{DU}(x,y)=\frac{(1 - x) x}{1 - 2 x + x^2 - x y} \quad \text{and} \quad \Dg_{DU}(x)=\dfrac{(1-x)x^2}{(1-3x+x^2)^2}.$$
Furthermore, for $n\geq 1$, we have   
$$\dt_{DU}(n)=\frac{1}{10}((5n-2) F_{2n}-nL_{2n}).$$
\end{theorem}

Since the $\dt_{DU}(n)$ corresponds to the number of valleys in $\D_n$, the proof of the previous theorem follows from \cite[Theorems 14]{CzabarkaFlorezJunesJose}. 

 \begin{theorem} \label{SubPathsUUyDD} 
 Let $w\in\{UU, DD\}$. The number of subwords of the form $w$ in $\D_n$ is given by
$$\F_{w}(x,y)=\frac{x (1-x y)}{1-x-2xy+x^2y^2} \quad \text{and} \quad \Dg_{w}(x)=\frac{x^2 \left(1-x+x^2\right)}{\left(1-3 x+x^2\right)^2}.$$
Moreover, for $n\geq 1$, we have 
\begin{align}\label{eqUU}
\dt_{w}(n)=\frac{1}{10}((7-10n) F_{2n}+(6n-5)L_{2n}).
\end{align}
\end{theorem}

\begin{proof} We prove the case for subwords of the form  $UU$; the case  $DD$  is similar and is therefore omitted.
From the first return decomposition (as shown in Figure \ref{Ldecom1}), any non-empty non-decreasing Dyck path $w$ can be uniquely decomposed as either $UD$, $\Delta_1v$, $\Delta_h v$, or $ UvD$, where $v\in \D$ and $h \geq 2$. Utilizing the symbolic method, see for example Flajolet and  Sedgewick \cite{flajolet}, we get the functional equation:
\begin{equation*}
\F_{UU}(x,y)=\underbrace{x}_{(1)} + \underbrace{\left(x + \frac{x^2y}{1-xy}\right)\F_{UU}(x,y)}_{(2)} + \underbrace{xy\F_{UU}(x,y)}_{(3)}.
\end{equation*}
Here, the labels $(1)$, $(2)$, and $(3)$ in the functional equation correspond to the labels in Figure \ref{Ldecom1}. By solving this functional equation, we obtain the desired generating function for $\F_{UU}(x,y)$.

Next, we provide a combinatorial proof of \eqref{eqUU}. From the previous argument, we can express $\dt_{UU}(n)$ (for $n&gt;0$) in terms of Fibonacci and Lucas numbers. Specifically, considering the first return decomposition in Figure \ref{Ldecom1}, any path $w\in \D_n$ can be written as $\Delta_k z$ or $UvD$, where $v \in \D_{n-1}$, $z\in \D_{n-k}$, and $1\leq k &lt;n$.

Firstly, we note that the number of subwords of the form $UU$ in $\Delta_k$ is $k-1$. This implies that the number of subwords of the form $UU$ in a path of the form $\Delta_k z$ is $(k-1)F_{2(n-k)-1} + \dt_{UU}(n-k)$, for a fixed $1\leq k &lt;n$, (since $|\D_{n-k}|=F_{2(n-k)-1}$). Secondly, we observe that the number of subwords $UU$ in the decomposition $UvD$ is equal to the number of subwords $UU$ in $v$ plus one. Thus, for $k=1, \dots, n-1$, we obtain the recurrence relation:
\begin{align*}
\dt_{UU}(n)&amp;=\dt_{UU}(n-1) + \sum_{k=2}^{n-1}\left((k-1)F_{2(n-k)-1} + \dt_{UU}(n-k)\right)  + \dt_{UU}(n-1) + F_{2(n-1)-1} \\
&amp;=2\dt_{UU}(n-1)  + \sum_{k=1}^{n-1}(n-k-1)F_{2k-1}  + \sum_{k=1}^{n-1}\dt_{UU}(k) + F_{2n-3}\\
&amp;=2\dt_{UU}(n-1)  + F_{2n-3}  + \sum_{k=1}^{n-1}\dt_{UU}(k) + F_{2n-3}\\
&amp;=2\dt_{UU}(n-1)  + 2F_{2n-3}  + \sum_{k=1}^{n-1}\dt_{UU}(k).
\end{align*}
Simplifying the equation, we get
$$\dt_{UU}(n+1)-\dt_{UU}(n)= 2 \dt_{UU}(n)-\dt_{UU}(n-1)+2 (F_{2n-1}-F_{2n-3}).$$ 
Therefore,
$
\dt_{UU}(n)=3\dt_{UU}(n-1)-\dt_{UU}(n-2)+2 F_{2n-4},  
$
where $\dt_{UU}(1)=0$ and $\dt_{UU}(2)=1$.

It is possible to verify that $((7-10n) F_{2n}+(6n-5)L_{2n})/{10}$ satisfies the previous recurrence relation. 
\end{proof}

The sequences $\dt_{UD}(n)$, $\dt_{DU}(n)$, and  $\dt_{UU}(n)= \dt_{DD}(n)$, provide a new combinatorial interpretation for \seqnum{A038731}, \seqnum{A001870}, \seqnum{A054444}, respectively. 

\section{String of length three}

In this section, we focus on counting the number of subwords of length three in $\D_n$. Since there are eight distinct subword types to analyze, we present eight theorems, each addressing a specific type. The proofs for these theorems follow a similar approach based on the first return decomposition illustrated in Figure \ref{Ldecom1}. To ensure a comprehensive understanding, we provide a detailed proof for one representative theorem and outline the main ideas for the remaining proofs.

The proofs of many theorems in this section can naturally be extended to more general cases. For example, the results for  $U^3$, $D^3$, $UD^2$, and $U^2D$ extend to subwords of the form $U^k$, $D^k$, $UD^k$, and $U^kD$, respectively. However, due to the scope of this paper, we do not develop such generalizations here; interested readers may verify them independently. 
 
To provide an overview of the results in this section, Table \ref{table1} summarizes the first few values of the sequence $\dt_{w}(n)$, along with the corresponding generating functions and references to related sequences in the OEIS (On-Line Encyclopedia of Integer Sequences \cite{sloane}). This table serves as a convenient reference for the results presented throughout the section.  

\footnotesize
\begin{table}[htp]
\begin{tabular}{|c|l|c|c|} \hline
Subword $w$ &amp; $\dt_{w}(n)$ for $2\leq n \leq 10$ &amp; $\Dg_{w}(x)$ &amp; OEIS \\ \hline 
$UUU\sim DUU$ &amp; 0, 1, 6, 25, 90, 300, 954, 2939, 8850 &amp; $\frac{x^3}{(1 - 3 x + x^2)^2}$ &amp; \seqnum{A001871}  \\[5pt]  \hline
$UDU\sim UUD$ &amp;  1, 4, 14, 46, 145, 444, 1331, 3926, 11434 &amp; $\frac{x^2(1-x)^2}{(1 - 3 x + x^2)^2}$ &amp; \seqnum{A030267}  \\[5pt]  \hline
$UDD$ &amp;  1, 4, 14, 45, 138, 411, 1200, 3454, 9836 &amp;  $\frac{(1 - x) (1 - 3 x + 2 x^2 - x^3) x^2}{(1 - 2 x)(1 - 3 x + x^2)^2}$&amp;\seqnum{A377670}  \\[5pt]  \hline
$DUD$ &amp;  1, 4, 13, 40, 120, 354, 1031, 2972, 8495 &amp;$\frac{x^2(1-2x)}{(1 - 3 x + x^2)^2}$ &amp; \seqnum{A238846}  \\[5pt]  \hline
$DDU$ &amp; 0, 1, 5, 19, 65, 210, 654, 1985, 5911 &amp;  $\frac{(1-x)x^3}{(1 - 3 x + x^2)^2}$ &amp; \seqnum{A001870}  \\[5pt]  \hline
$DDD$ &amp; $0, 1, 6, 26, 97, 333, 1085, 3411, 10448$  &amp; $\frac{x^3 (1 - 2 x + x^2 - x^3)}{(1 - 2 x) (1 - 3 x + x^2)^2}$ &amp;\seqnum{A377679} \\[5pt]  \hline
\end{tabular}
\caption{Non-decreasing  words and subwords of length three.}\label{table1}
\end{table}
\normalsize 

 \begin{theorem} \label{SubPathsUUU}  The number of subwords of the form $UUU$ in $\D_n$ is counted by
$$\F_{UUU}(x,y)=\frac{(1 - xy)x}{1 - x (2 + y) + x^2 y} \quad \text{and} \quad \Dg_{UUU}(x)=\dfrac{x^3}{(1 - 3 x + x^2)^2}.$$
Furthermore, for $n\geq 1$, we have   
$$\dt_{UUU}(n)=\frac{1}{10}(-(5n+4) F_{2n}+ 3nL_{2n}).$$
\end{theorem}
\begin{proof}
From the first return decomposition, see Figure \ref{Ldecom1}, any non-empty non-decreasing Dyck word $w$ can be uniquely decomposed into one of the following three cases:
\begin{enumerate}[\text{Case} 1.]
\item \label{Case1UDThm4} $UD$. This case corresponds to the generating function  $x$.

\item \label{Case2Thm4} $\Delta_k v$, where $k \geq 1$ and $v\in \D$. Notice that for $k\geq 3$ the pyramid $\Delta_k$ contains $k-2$ subpaths of the form $UUU$.  Therefore, in this case the corresponding generating function is 
$$\left(x+x^2+x^3y+x^4y^2+\cdots\right)\F_{UUU}(x,y)=\left(x+x^2+\frac{x^3y}{1-xy}\right)\F_{UUU}(x,y).$$
 
\item \label{CaseUvDThm4}  $UvD$, with $v\in \D$. Any path in this case can be written as $U^iD^jwD^{i-j}$, with $w\in \D\cup\{\epsilon\}$ and $i\geq 2$, $j=1, 2, \dots, i$. See Figure \ref{figUUU} for a geometric representation of the case $i=4$.
\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.8]{CaseUUU.eps}
\end{center}
\caption{Factorization of non-decreasing Dyck paths in Case \ref{CaseUvDThm4}.} \label{figUUU}
\end{figure}
Therefore, the corresponding generating function for this case is 
$$
x^2(1+\F_{UUU}(x,y))+x^3y(1+2\F_{UUU}(x,y)) + x^4y^2(1+3\F_{UUU}(x,y))+\cdots.$$
Simplifying we obtain 
$$\frac{x^2}{1-xy}+\frac{x^2}{(1-xy)^2}\F_{UUU}(x,y).
$$
\end{enumerate}
Summing the expression in cases \ref{Case1UDThm4}, \ref{Case2Thm4}, and \ref{CaseUvDThm4}, we obtain the following functional equation: 
\begin{equation*}
\F_{UUU}(x,y)=x + \left(x+x^2+\frac{x^3y}{1-xy}\right)\F_{UUU}(x,y) + \frac{x^2}{1-xy}+\frac{x^2}{(1-xy)^2}\F_{UUU}(x,y).
\end{equation*}
By solving this functional equation, we obtain the desired result.

Next, we provide a  combinatorial proof for the sequence $\dt_{U^3}(n)$. 
We observe that the number of subwords of the form $U^3$ in the pyramid $\Delta_k$ is $k-2$,  as explained in the decomposition described in cases  \ref{Case1UDThm4}, \ref{Case2Thm4}, and   \ref{CaseUvDThm4}.

For a path of the form $\Delta_k v$, the total number of subwords of the form $U^3$ is $\dt_{U^3}(n-k)$, for $k=1,2$. For a fixed $k\ge 3$, the total number of subwords $U^3$ in a path of the form  $\Delta_k v$ is $(k-2)F_{2(n-k)-1} + \dt_{U^3}(n-k)$, since $|\D_{n-k}|=F_{2(n-k)-1}$. 

 Furthermore, the number of subwords $U^3$ in a path of the form $UvD$ is equal to the number of  subwords  $U^3$ in $v$. Additionally, we add $1$ if the path  $v$  is not of the form $\Delta_1Q$ with $Q \in \D_{n-2}$. Therefore, for $k=1, \dots, n-1$, we obtain the recurrence relation:
 
\begin{eqnarray*}
\dt_{U^3}(n) &amp;=&amp; \left(\sum_{k=3}^{n-1} (k-2)F_{2k-1} +\sum_{i=1}^{n-1}\dt_{U^3}(i)\right)+ \left( \dt_{U^3}(n-1)+F_{2n-3}\right) -  F_{2(n-1)-3} \\
		   &amp;=&amp; \sum_{i=1}^{n-2} (n-2-i) F_{2i-1} +\sum_{i=1}^{n-1}\dt_{U^3}(i)+\dt_{U^3}(n-1)+F_{2n-3}-F_{2n-5} \\ 
		   &amp;=&amp; F_{2(n-3)}-1 +F_{2n-3} - F_{2(n-1)-3}+\sum_{i=1}^{n-1}\dt_{U^3}(i)+\dt_{U^3}(n-1). 
\end{eqnarray*}
Subtracting $\dt_{U^3}(n+1)$ from $\dt_{U^3}(n)$ we obtain 
$$\dt_{U^3}(n)=3 \dt_{U^3}(n-1)-\dt_{U^3}(n-2)+F_{2 (n-2)},$$
where $\dt_{U^3}(1)=\dt_{U^3}(2)=0$ and $\dt_{U^3}(3)=1$.
It is possible to verify that 
$$\frac{3nL_{2n}-(5n+4) F_{2n}}{10}$$ 
satisfies the previous recurrence relation. 
\end{proof}

The coefficient array $[x^ny^m]\F_{UUU}(x,y)$ corresponds to the matrix sequence \seqnum{A153342}. Our combinatorial interpretation is new. 

From the proof of Theorem \ref{SubPathsUUU}, we observe that once the functional equation is established, completing the remaining details becomes straightforward. Therefore, for the other theorems in this section, we will present only the functional equations and leave the detailed proofs to the reader.

As mentioned earlier, all functional equations in this section are derived based on the first return decomposition illustrated in Figure \ref{Ldecom1}. The labels within each functional equation correspond directly to the labels provided in Figure  \ref{Ldecom1}.

 \begin{theorem} \label{SubPathsUDU}  The number of subwords of the form $UDU$ in $\D_n$ is counted by
$$\F_{UDU}(x,y)=\frac{(1 - x)x}{1 - x (2 + y) + x^2 y} \quad \text{and} \quad \Dg_{UDU}(x)=\dfrac{x^2(1-x)^2}{(1 - 3 x + x^2)^2}.$$
Furthermore, for $n\geq 1$, we have
$$\dt_{UDU}(n)=\frac{1}{10}((-5n+11) F_{2n}+ (3n-5)L_{2n}).$$
\end{theorem}

\begin{proof}
From decomposition given in Figure \ref{Ldecom1} we have 
$$\F_{UDU}(x,y)= \underbrace{x}_{(1)}  +  \underbrace{xy\F_{UDU}(x,y) + \frac{x^2}{1-x}\F_{UDU}(x,y)}_{(2)} + \underbrace{x\F_{UDU}(x,y)}_{(3)}.$$
Solving this functional equation we obtain the desired  generating function. 
\end{proof} 

The coefficient array $[x^ny^m]\F_{UDU}(x,y)$ coincides with the matrix  \seqnum{A105306}.
    
\begin{theorem} \label{SubPathsUDD}  The number of subwords of the form $UDD$ in $\D_n$ is counted by
\begin{eqnarray*}
\F_{UDD}(x,y)&amp;=&amp;\frac{(1 - x) (1 - 2 x) (1 - x (1 - y)) x}{(1 - 3 x + x^2 (2 - y)) (1 - 2 x + x^2 (1 - y))} \quad \text{and} \\
\Dg_{UDD}(x)&amp;=&amp;\dfrac{(1 - x) (1 - 3 x + 2 x^2 - x^3) x^2}{(1 - 2 x)(1 - 3 x + x^2)^2}.
\end{eqnarray*}
Furthermore, for $n\geq 2$, we have  
$$\dt_{UDD}(n)=\frac{1}{5}((5n-9) F_{2n}+ (-2n+5)L_{2n} - 5 \cdot 2^{n-2}).$$
\end{theorem}

\begin{proof} For $i_j\ge0$ and $n\geq 0$, the paths of the form $U(\Delta_{i_1} \Delta_{i_2} \cdots \Delta_{i_n}\textcolor{red}{UD})\textcolor{red}{D}$, can be obtained from case (3) of the decomposition shown in Figure \ref{Ldecom1}. Recall that when $i_j=0$, $\Delta_{i_j}$ corresponds to an empty pyramid. In these paths, the subword $UDD$ appears at the end of the path (highlighted in red). The generating function for this type of paths is given by
$$x(xy+xy\Delta(x,y) + xy\Delta(x,y)^2+\cdots)= x\left(\frac{xy}{1-\Delta(x,y)}\right),$$
where $\Delta(x,y)$ is the generating function of the non-empty pyramids  according to the number of $UDD$'s. So, 
$$\Delta(x,y)=x + x^2y + x^3y + \cdots = \frac{x-x^2+x^2y}{1-x}.$$
Therefore, we have that $\F_{UDD}(x,y)$ is equal to 
$$ \underbrace{x}_{(1)}  +  \underbrace{ \left(x + \frac{x^2y}{1-x}\right)\F_{UDD}(x,y)}_{(2)}\\ + \underbrace{x\left(\F_{UDD}(x,y)- \frac{x}{1-\Delta(x,y)} +  \frac{xy}{1-\Delta(x,y)}\right)}_{(3)}.
$$
Solving this functional equation we obtain the desired result. 
\end{proof} 

The coefficient array  $[x^ny^m]\F_{UDD}(x,y)$ coincides with the matrix  \seqnum{A105306}.

 \begin{theorem} \label{SubPathsDUU}  The number of subwords of the form $DUU$ in $\D_n$ is counted by
$$\F_{DUU}(x,y)=\frac{x - x^2 + x^3 (1 - y)}{1 - 3 x + x^2 (3 - 2 y) - x^3 (1 - y)} \quad \text{and} \quad \Dg_{DUU}(x)=\dfrac{x^3}{(1 - 3 x + x^2)^2}.$$
Furthermore, for $n\geq 3$, we have
$$\dt_{DUU}(n)=\frac{1}{10}(-(5n+4) F_{2n}+ 3nL_{2n}).$$
\end{theorem}

\begin{proof} From case (2) in the decomposition given in Figure \ref{Ldecom1}, we deduce that the paths of the form $U\Delta Dv$, where $\Delta$ may be empty, determine the subpath $DUU$ if $v$ starts with $UU$.  This gives rise to the following functional equation:
$$\F_{DUU}(x,y)= \underbrace{x}_{(1)}  +  \underbrace{\frac{x}{1-x}\left(\F_{DUU}(x,y) -\G_{DUU}(x,y) + y\G_{DUU}(x,y)\right)}_{(2)} + \underbrace{x\F_{DUU}(x,y)}_{(3)},$$
where $\G_{DUU}(x,y)$ is the generating function for the non-decreasing Dyck path starting with $UU$ according to the number of $DUU$'s.  This kind of Dyck paths admit the decomposition given in Figure \ref{Ldecom2 }.  Therefore, we have the functional equation:  
\begin{multline*}
\G_{DUU}(x,y)= \underbrace{x^2}_{(1)} +   \underbrace{\frac{x^2}{1-x}\left(\F_{DUU}(x,y) - \G_{DUU}(x,y) + y\G_{DUU}(x,y)\right)}_{(2)}   \\
+  \underbrace{\frac{x^2}{1-x}\left(\F_{DUU}(x,y) - \G_{DUU}(x,y) + y\G_{DUU}(x,y)\right)}_{(3\text{-a})} +  \underbrace{x^2 \F_{DUU}(x,y)}_{(3\text{-b})}.
\end{multline*}
Solving the system of  functional equations we obtain the desired result. 
\end{proof} 

\begin{figure} [ht!]
\begin{center}
\includegraphics[scale=0.9]{decom2.eps}
\end{center}
\caption{Factorization of non-decreasing Dyck paths starting with $UU$.} \label{Ldecom2 }
\end{figure}

The coefficient array $[x^ny^m]\F_{DUU}(x,y)$ coincides with the matrix  \seqnum{A105306}.

\begin{theorem} \label{SubPathsDUD}  The number of subwords of the form $DUD$ in $\D_n$ is counted by 
$$\F_{DUD}(x,y)=\frac{x (1 - x - x^2 (1 - y))}{1 - x^2 (1 - 2 y) + x^3 (1 - y) - x (2 + y)} \quad \text{and} \quad \Dg_{DUD}(x)=\dfrac{x^2-2x^3}{(1 - 3 x + x^2)^2}.$$
Furthermore, for $n\geq 3$, we have  
$$\dt_{DUD}(n)=\frac{1}{5}((5n+1) F_{2n} - 2nL_{2n}).$$
\end{theorem}

\begin{proof}
In case (2) of the decomposition given in Figure  \ref{Ldecom1}, paths  of the form $U\Delta \textcolor{red}{DUD}v$, where $\Delta$ may be empty,  determine the subpath $DUD$. Therefore,  we have  the functional equation:   
$$\F_{DUD}(x,y)= \underbrace{x}_{(1)}  +  \underbrace{\frac{x}{1-x}\left(\F_{DUD}(x,y) - \G_{DUD}(x,y) + y\G_{DUD}(x,y)\right)}_{(2)} + \underbrace{x\F_{DUD}(x,y)}_{(3)},$$
where  $\G_{DUD}(x,y)= x + x(\F_{DUD}(x,y)-\G_{DUD}(x,y)+y\G_{DUD}(x,y))$. Solving this system of equations yields the desired result. 
\end{proof}

The coefficient array $[x^ny^m]\F_{DUD}(x,y)$ does not appear in the OEIS.

\begin{theorem} \label{SubPathsDDU}  The number of subwords of the form $DDU$ in $\D_n$ is counted by
$$\F_{DDU}(x,y)=\frac{(1-x)x}{1 - 3 x + x^2 (2 - y))} \quad \text{and} \quad \Dg_{DDU}(x)=\dfrac{(1-x)x^3}{(1 - 3 x + x^2)^2}.$$
Furthermore, for $n\geq 3$, we have   
$$\dt_{DDU}(n)=\frac{1}{10}((10n  - 13) F_{2n} + (-4n + 5) L_{2n}).$$
\end{theorem}
\begin{proof}
The decomposition presented in Figure \ref{Ldecom1} yields the following functional equation: 
$$\F_{DDU}(x,y)= \underbrace{x}_{(1)}  +  \underbrace{\left(x + \frac{x^2y}{1-x}\right)\F_{DDU}(x,y)}_{(2)} + \underbrace{x\F_{DDU}(x,y)}_{(3)}.$$
Solving this equation we obtain the desired result. 
\end{proof}

The coefficient array $[x^ny^m]\F_{DDU}(x,y)$ coincides with the matrix  \seqnum{A121466}.

\begin{theorem} \label{SubPathsDDD}  The number of subwords of the form $DDD$ in $\D_n$ is counted by 
\begin{eqnarray*}
\F_{DDD}(x,y)&amp;=&amp;\frac{x (1 - x y) (1 - 2 x y - x^2 (1 - y^2))}{(1 - x (1 + y) - x^2 (1 - y)) (1 - x (1 + 2 y) - x^2 (1 - y - y^2))} \quad \text{and} \\
\Dg_{DDD}(x)&amp;=&amp;\dfrac{x^3 (1 - 2 x + x^2 - x^3)}{(1 - 2 x) (1 - 3 x + x^2)^2}.
\end{eqnarray*}
Furthermore, for $n\geq 3$, we have   
$$\dt_{DDD}(n)=\frac{1}{4}((-8n  + 10) F_{2n} + (4n -6) L_{2n} + 2^n).$$
\end{theorem}

\begin{proof}
In  case (3) of the decomposition presented in Figure \ref{Ldecom1}, we consider the paths of the form $UvD$, where $v\in \D$. We classify $v$ according to the number of ending  $D's$. Note that if the last return of $v$ contains  exactly $k$ $D$'s, where $k\geq 2$, these paths generate $k-1$ subpaths of the form $DDD$. 

For example, if the last return of $v$ is represented by $DDD$, the path $UvD$ can be decomposed as $U(P_1UP_2UP_3UDDD)D$, where each $P_i$ ($i=1, 2, 3$) is a non-decreasing Dyck path (possibly empty) with only valleys at the floor level, see Figure \ref{Ldecom3}.

\begin{figure} [H]
\begin{center}
\includegraphics[scale=0.8]{decom3.eps}
\end{center}
\caption{Factorization of non-decreasing Dyck paths of the form $U(P_1UP_2UP_3UDDD)D$.} \label{Ldecom3}
\end{figure}
In general, this kind of paths have this generating function:
$$x(x\V_{DDD}(x,y)+x^2y\V_{DDD}(x,y)^2+ x^3y^2\V_{DDD}(x,y)^3+\cdots)= x\left(\frac{x\V_{DDD}(x,y)}{1-xy\V_{DDD}(x,y)}\right),$$
where  $\V_{DDD}(x,y)$ 
is the generating function of the  non-decreasing Dyck paths  (possible empty) with only valleys at floor level, according to the number of $DDD$'s.  So, 
$$\V_{DDD}(x,y)=1+\left( x + x^2 + \frac{x^3y}{1-xy}\right)\V_{DDD}(x,y).$$
Therefore,  we have  this functional equation:   
$$\F_{DDD}(x,y)= \underbrace{x}_{(1)}  +  \underbrace{\left(x + x^2 + \frac{x^3y}{1-xy}\right)\F_{DDD}(x,y)}_{(2)} + \underbrace{x\left(\frac{x\V_{DDD}(x,y)}{1-xy\V_{DDD}(x,y)}\right)}_{(3)}.$$
Solving this system of equations we obtain the desired result. 
\end{proof}

 \begin{theorem} \label{SubPathsUUD}  
The number of subwords of the form $UUD$ in $\D_n$ is counted by 
$$\F_{UUD}(x,y)=\frac{(1 - x) x (1 - x (1 - y))}{1 - 3 x + x^2 (3 - 2 y) - x^3 (1 - y)} \quad \text{and} \quad \Dg_{UUD}(x)=\frac{(1 - x)^2 x^2}{(1 - 3 x + x^2)^2}.$$
Furthermore, for $n\geq 3$, we have   
\begin{align}\label{eqUUD}
\dt_{UUD}(n)=\frac{1}{10}((-5n+11) F_{2n}+(3n-5)L_{2n}).
\end{align}

\end{theorem}
\begin{proof}
The decomposition presented in Figure \ref{Ldecom1} yields the following functional equation:   
\begin{multline*}
\F_{UUD}(x,y)= \underbrace{x}_{(1)}  +  \underbrace{\left(x + \frac{x^2y}{1-x}\right)\F_{UUD}(x,y)}_{(2)} \\+ \underbrace{x\left(\F_{UUD}(x,y)- (x+x\F_{UUD}(x,y)) +  y(x+x\F_{UUD}(x,y)) \right)}_{(3)}.
\end{multline*}
Solving this functional equation we obtain the desired result. 
\end{proof}

The coefficient array $[x^ny^m]\F_{UUD}(x,y)$ coincides with the matrix  \seqnum{A304429}.

\section{String of length four}

In this section, we focus on counting the number of subwords of length four in  $\D_n$. Given that there are $16$ distinct subword types, we have compiled the results in Table \ref{table2}, rather than presenting each result as a separate theorem. We provide a detailed proof for one representative theorem and omit the remaining proofs, as they follow a similar structure or have been addressed in earlier sections.

 \begin{theorem} \label{SubPathsUUUD}  The number of subwords of the form $U^3D$ in $\D_n$ is counted by 
$$\F_{U^3D}(x,y)=\frac{(1-x) \left(x+x^3 (y-1)\right)}{1 - 3 x + x^2 + (3-3y) x^3 - 2(1-y) x^4} 
\quad \text{and} \quad 
\Dg_{U^3D}(x)=\frac{(x-1)^2 x^3 (x+1)}{(1+x(x-3))^2}.
$$
Furthermore, for $n\geq 3$, we have   
$$\dt_{U^3D}(n)=n F_{2 n-5}-L_{2 n-6}.$$
\end{theorem}

\begin{proof} For simplicity, and when there is no ambiguity, we use $\F$ to denote $\F_{U^3D}(x,y)$ throughout this proof. From the first return decomposition any non-empty  non-decreasing Dyck word  $w$  may be uniquely decomposed in one of these   
three cases. 

\begin{enumerate}[\text{Case} 1.]
\item  \label{CaseUDThm12} $UD$.  This case corresponds to the generating function  $x$.

\item \label{Case1Thm12}  $\Delta_k v$, where $v\in \D$ and  $k \geq 1$.  In this case the corresponding generating function is 
$$\left(x+x^2+\frac{x^3y}{1-x}\right)\F.$$
 
\item \label{CaseUvDThm12}  $UvD$, with $v\in \D$. Any path in this case can be written as 
$U^iD^jwD^{i-j}$, with $w\in \D\cup\{\epsilon\}$, for all $i\geq 2$ and  $j=1, 2, \dots, i$. 
This gives rise to the following generating function:  
$$x\left(\F-(x^2+x^2\F+x^2\F)+ y(x^2+x^2\F+x^2\F)\right).$$
\end{enumerate}
Summing and simplifying the generating functions from cases \ref{CaseUDThm12},  \ref{Case1Thm12} and \ref{CaseUvDThm12} we obtain the functional equation: 
\begin{equation*}
\F=\underbrace{x}_{(1)}+\underbrace{x\left(x+x^2+\frac{x^3y}{1-x}\right)\F}_{(2)}+\underbrace{x\left(\F-(x^2+x^2\F+x^2\F)+ y(x^2+x^2\F+x^2\F)\right)}_{(3)}.
\end{equation*}
Solving this functional equation for $\F$ we obtain the desired generating function.

Next, we present a constructive and combinatorial proof of the sequence  $\dt_{U^3D}(n)$. We observe that the number of subwords of the form $U^3D$ in $\Delta_k$ is $1$ if $k&gt;2$. 

A path $\D_n$ can be uniquely decomposed as $\Delta_kv$ or $UzD$ where $v \in \D_{n-i}$ and $z \in \D_{n-1}$.  It is evident that the number of subwords of the form $U^3D$ in a path of the form $\Delta_k v$ is $\dt_{U^3D}(n-k)$ for $k=1,2$. For a fixed $k\ge 3$ the total number of subwords $U^3D$ in a path of the form  
$\Delta_k v$ is $F_{2(n-k)-1} + \dt_{U^3D}(n-k)$.  

We observe that the number of subwords $U^3D$ in a path in the decomposition $UzD$ is equal to the number of  subwords   $U^3D$ in $v$. Additionally, we add $1$ in cases where the path $z$ takes one of the forms
$\Delta_2Q \in \D_{n-1}$ or $U\Delta_1QD \in \D_{n-1}$, where $Q \in \D_{n-3}$.

Therefore, for $k=1, \dots, n-1$, we obtain the recurrence relation:
$$\dt_{U^3D}(n)=\sum _{k=1}^{n-1} \dt_{U^3D}(k)+\dt_{U^3D}(n-1)+\sum _{k=1}^{n-3} F_{2 k-1}+2 F_{2 n-7}.$$
By simplifying similarly as in the proof of Theorem \ref{SubPathsUUU},  we obtain the recurrence relation: 
$$\dt_{U^3D}(n)=3 \dt_{U^3D}(n-1)-\dt_{U^3D}(n-2)+L_{2n-7},$$ where 
$\dt_{U^3D}(1)=\dt_{U^3D}(2)=0$, $\dt_{U^3D}(3)=1$, and $\dt_{U^3D}(4)=5$. 
It is possible to verify that $n F_{2 n-5}-L_{2 n-6}$ satisfies the previous recurrence relation. 
\end{proof}

From Table \ref{table2}, we observe that the subwords $UDUU$, $DUDU$, and $DDDU$ correspond to the same sequence \seqnum{A001870}, while the subwords  $UUDU$, $UDDU$ correspond to the same sequence  \seqnum{A030267}. 

\begin{table}[ht!]
\begin{tabular}{|c|c|c|c|} \hline
Subword $w$ &amp; $\Dg_{w}(x)$ &amp;Sequence&amp; OEIS \\ \hline 
$UUUU$ &amp; $\frac{x^4 \left(-x^2+x+1\right)}{\left(x^2-3 x+1\right)^2}$   &amp; $\frac{2(n-3)L_{2n-5}-3F_{2n-6}}{5}$   &amp; \seqnum{A375995}  \\[5pt]  \hline
$UUUD$ &amp; $\frac{(x-1)^2 x^3 (x+1)}{\left(x^2-3 x+1\right)^2} $   &amp;$nF_{2n-5}-L_{2n-6}$  &amp;  \seqnum{A377857} \\[5pt]  \hline
$UUDU$ &amp; $\frac{(x-1)^2 x^3}{\left(x^2-3 x+1\right)^2}$   		&amp;$\frac{(n-1)L_{2n-4}-F_{2n-7}}{5}$&amp;\seqnum{A030267}   \\[5pt]  \hline
$UDUU$ &amp; $\frac{(1-x) x^3}{\left(x^2-3 x+1\right)^2}$    		&amp;$\frac{(n-1)L_{2n-3}-F_{2n-2}}{5}$  &amp;\seqnum{A001870 }  \\[5pt]  \hline
$DUUU$ &amp; $\frac{x^4 (x+1)}{\left(x^2-3 x+1\right)^2}$   		&amp;$nF_{2n-5}-L_{2n-4}$  &amp;\seqnum{A197649 }  \\[5pt]  \hline
$UUDD$ &amp; $\frac{(1-x)^3 x^2}{\left(x^2-3 x+1\right)^2}$   		&amp;$\frac{n L_{2n-3}+3F_{2n-5}}{5}$  &amp; \seqnum{A038731} \\[5pt]  \hline
$UDUD$ &amp; $\frac{x^2 \left(2 x^2-3 x+1\right)}{\left(x^2-3 x+1\right)^2}$   &amp;$\frac{n L_{2n-4}+2L_{2n-3}-F_{2n-3}}{5}$  &amp; \seqnum{A059502} \\[5pt]  \hline
$UDDU$ &amp; $\frac{(x-1)^2 x^3}{\left(x^2-3 x+1\right)^2}$    		&amp;$\frac{(n-1)L_{2n-4}-F_{2n-7}}{5}$  &amp;\seqnum{A030267 }  \\[5pt]  \hline
$DDUU$ &amp; $\frac{x^3}{\left(x^2-3 x+1\right)^2}$   			&amp;$\frac{(n-1) L_{2n-4}-2F_{2n-2}}{5}$  &amp; \seqnum{A001871}  \\[5pt]  \hline
$DUDU$ &amp; $\frac{(1-x) x^3}{\left(x^2-3 x+1\right)^2}$  		&amp;$\frac{(n-1)L_{2n-3}-F_{2n-2}}{5}$  &amp; \seqnum{A001870}  \\[5pt]  \hline
$UDDD$ &amp; $\frac{\left(-x^5+2 x^4-5 x^3+8 x^2-5 x+1\right) x^3}{\left(2 x^3-7 x^2+5 x-1\right)^2}$  &amp; $\frac{(n-3)L_{2n-5}+L_{2n-3}+F_{2n+2} -5(n+5)2^{n-4}}{5}$  &amp;  \seqnum{A378383}\\[5pt]  \hline
$DUDD$ &amp; $\frac{(x-1) x^3}{2 x^3-7 x^2+5 x-1}$  &amp;$F_{2n-2}-2^{n-2}$  &amp; \seqnum{A105693 } \\[5pt]  \hline
$DDUD$ &amp; $\frac{(1-2 x) x^2}{\left(x^2-3 x+1\right)^2}$   		&amp;$\frac{(n-2) L_{2n-5}+4F_{2n-4}}{5}$  &amp;\seqnum{A238846 }  \\[5pt]  \hline
$DDDU$ &amp; $\frac{(1-x) x^4}{\left(x^2-3 x+1\right)^2}$   &amp;$\frac{(n-2)L_{2n-5}-F_{2n-4}}{5}$  &amp;\seqnum{A001870 }  \\[5pt]  \hline
$DUUD$ &amp; $\frac{-x^3 \left(x^2+x-1\right)}{\left(x^2-3 x+1\right)^2}$  &amp;$\frac{2 n L_{2 n-5}-6 F_{2 n-6}-F_{2 n-7}}{5}$  &amp; \seqnum{A377866} \\[5pt]  \hline
$DDDD$ &amp; $\frac{x^4 \left(x^4+2 x^2-3 x+1\right)}{\left(2 x^3-7 x^2+5 x-1\right)^2}$  &amp; $\frac{3(n-2)L_{2n-4}-3F_{2n+1} +5(n+9)2^{n-4}}{5}$&amp; \seqnum{A377867} \\[5pt]  \hline
\end{tabular}
\caption{Subwords of length four in $\D_n$.}\label{table2}
\end{table}

\section{Strings of length five and some generalizations}

In this section, we provide combinatorial expressions for counting the number of subwords of length five in $\D_n$ in terms of Fibonacci and Lucas numbers. Table \ref{table3} presents the 32 distinct subword types along with their corresponding formulas. The results were obtained using the computer software \emph{Mathematica}$^{\mbox{\scriptsize\textregistered}}$.  While we have proven some of these results, not all have been rigorously demonstrated. However, based on the proofs we have established, we strongly believe that the remaining results can be proven using the same techniques applied in previous sections.

For the subword $DUD^2U$, we have $\dt_{DUD^2U}(n)=0$, since it does not appear in non-decreasing Dyck paths. To simplify notation, we omit the argument $n$ in the functions presented in Table \ref{table3}.

\begin{table}[ht!] \centering 
\begin{tabular}{|l|l|} \hline
$\dt_{U^5} = \frac{(5n-24) F_{2 n-8}+(n-4) L_{2 n-7}}{5}$ &amp;  $\dt_{U^4D} = \frac{(n-2)\left(L_{2n-6} +2 L_{2 n-8}\right)- 9F_{2 n-9}}{5}$\\
$\dt_{U^3DU} = \frac{(n-2)L_{2n-6}-F_{2n-9}}{5}$      &amp;  $\dt_{U^3D^2}= \frac{(n-1)L_{2n-4}-F_{2n-7}}{5}$ \\
$\dt_{U^2DU^2} = \frac{(n-2)L_{2n-5}-F_{2n-4}}{5}$     &amp;  $\dt_{U^2DUD} = \frac{(n-1) L_{2n-6}+2L_{2n-5}-F_{2n-5}}{5}$      \\
 $\dt_{U^2D^2U} = \frac{(n-1)L_{2n-4}-F_{2n-7}}{5}$      &amp;  $\dt_{U^2D^3} = \frac{2F_{2n-5}+2L_{2n-4}+(n-1)L_{2n-5}}{5} -2^{n-3}$      \\
$\dt_{UDU^3} = (n-3)F_{2n-6}$      &amp;  $\dt_{UDU^2D} = \frac{(2n-3)L_{2n-6}+6F_{2n-6}-F_{2n-7}}{5}$      \\
 $\dt_{UDUDU} = \frac{(n-1)L_{2n-4}-F_{2n-7}}{5}$      &amp;  $\dt_{UDUD^2} = F_{2n-3}-2^{n-3}$      \\
 $\dt_{UD^2U^2} = \frac{(n-2)L_{2n-5}-F_{2n-4}}{5}$     &amp;  $\dt_{UD^2UD} = \frac{(n-1) L_{2n-6}+2L_{2n-5}-F_{2n-5}}{5}$      \\   
 $\dt_{UD^3U} = \frac{(n-2)L_{2n-6}-F_{2n-9}}{5}$      &amp;  $\dt_{DU^2DU} = \frac{(n-2)L_{2n-5}-F_{2n-4}}{5}$      \\
 $\dt_{DU^2D^2} = \frac{(n-2) L_{2n-5}+4F_{2n-4}}{5}$      &amp;  $\dt_{DUDU^2} = \frac{(n-1) L_{2n-4}-2F_{2n-2}}{5}$      \\
 $\dt_{DUDUD} = \frac{(n-2) L_{2n-5}+4F_{2n-4}}{5}$      &amp;  $\dt_{DUD^3}= F_{2n-2}-(n+3)2^{n-4}$      \\
 $\dt_{D^2U^3} = (n-1)F_{2n-7}-L_{2n-6}$      &amp;  $\dt_{D^2U^2D} = \frac{2 (n-1) L_{2 n-7}-6 F_{2 n-8}-F_{2 n-9}}{5}$      \\ 
$\dt_{D^2UDU} = \frac{(n-2)L_{2n-5}-F_{2n-4}}{5}$      &amp;  $\dt_{D^2UD^2} = F_{2n-4}-2^{n-3}$      \\
 $\dt_{D^3U^2} = \frac{(n-2) L_{2n-6}-2F_{2n-4}}{5}$      &amp;  $\dt_{D^3UD} = \frac{(n-3) L_{2n-7}+4F_{2n-6}}{5}$      \\
 $\dt_{D^4U} = \frac{(n-3)L_{2n-7}-F_{2n-6}}{5}$  &amp;  $\dt_{DU^4} = \frac{(-35n + 84)F_{2n-4} + (17 n-44)L_{2n-4}}{10}$\\
 $\dt_{DU^3D}=\frac{(15n-42)F_{2n-4}-(6n -17)L_{2n-4}}{5}$ &amp;\\
    \resizebox{3in}{!}{$\dt_{UD^4} = \frac{64 (10n-13) F_{2n-4} -64 (4 n - 23) L_{2n-4} -(5n^2 + 55n +180)2^n }{640}$} &amp; \\
    \resizebox{3.2in}{!}{$\dt_{D^5}=(n-5)L_{2n-4}-(n+2)F_{2n-4} -64 (4 n - 23) L_{2n-4} +(n^2 +  19 n + 108)2^{n-7}$} &amp; \\ \hline
 \end{tabular}
\caption{Number of subwords of length  five in $\D_n$.}\label{table3}
\end{table}

\subsection{Some general cases}\label{GeneralCase}

In this section, we analyze generalizations of certain subwords of $\D_n$. Since the proofs follow the same structure as those for shorter lengths, we present only the theorems without detailed proofs.
 
\begin{theorem} \label{SubPathsUtom}  If $ n&gt; m$, then the number of subwords of the form $U^m$ in $\D_n$ is counted by 
$$\dt_{U^m}(n)=3 \dt_{U^m}(n-1)- \dt_{U^m}(n-2)+F_{2(n-m)}+F_{2(n-2)} - \sum_{k=1}^{m-2} k F_{2(n-k-2)}.$$
If $n\le m$, then $\dt_{U^m}(n)=0$ and  $\dt_{U^n}(n)=1$.
\end{theorem}

\begin{theorem} \label{SubPathsDtom}  If $ n&gt; m$, then the number of subwords of the form $D^m$ in $\D_n$ is counted by  
$$\dt_{D^m}(n)=3 \dt_{D^m}(n-1)- \dt_{D^m}(n-2)+F_{2(n-m)}+F_{2(n-2)} - \sum_{k=1}^{m-2} (\dt_{D^k}(n-1)-\dt_{D^k}(n-2)).$$
If $n\le m$, then $\dt_{D^m}(n)=0$ and  $\dt_{D^n}(n)=1$.
\end{theorem}

\begin{theorem} \label{SubPathsUtomD}  If $ n\ge m$, then the number of subwords of the form $U^mD$ in $\D_n$ is counted by  
$$\dt_{U^mD}(n)=3 \dt_{U^mD}(n-1)- \dt_{U^mD}(n-2)+F_{2(n-m)-3}+mF_{2 (n-m-1)}.$$
If $n&lt;m$, then $\dt_{U^mD}(n)=0$,  $\dt_{U^nD}(n)=1$, and $\dt_{U^{m}D}(m+1)=m+2$.
\end{theorem}

\begin{theorem} \label{SubPathsUDtom} If $n\ge m$, then the number of subwords of the form $UD^m$ in $\D_n$ is counted by  
$$\dt_{UD^m}(n)=3 \dt_{UD^m}(n-1)- \dt_{UD^m}(n-2)+ F_{2 (n-m)-1} +l_{n-1,m-1}  -l_{n-2,m-1},$$
where $l_{n,k}$ is the total number of paths where the last peak is of height $k$. 
If $n&lt;m$, then $\dt_{UD^m}(n)=0$ and   $\dt_{UD^n}(n)=1$.
\end{theorem}

\subsection{Subword that share the same sequence}

In this section, we present Table \ref{words_Fibo_Lucas}, which summarizes the subwords that share the same counting sequence. However, depending on the subword, the sequence may be shifted. Of particular interest is the potential to find bijections between these subwords.

\begin{table} [H]
\begin{center}\scalebox{1}{
\begin{tabular}{|l|l|} \hline
Subwords   					           &amp; The OEIS \\ \hline \hline
$ UU; DD$                    						           &amp; \seqnum{A054444}\\ \hline
$ UUU; DUU; DDUU; DUDUU; DDDUU$                        	   &amp; \seqnum{A001871 }\\\hline
$ UUD; UDU; UUDU; UDDU; UUUDU; UUUDD; UUDDU;$  &amp; \seqnum{A030267 }\\
$UDUDU; UUUDU; UUUDD; UUDDU; UDUDU; UDDDU$   &amp; \\ \hline
$ UDD; UUDDD$                  				                   &amp; \seqnum{A377670}\\ \hline
$ DUD; DDUD; DUUDD; DUDUD; DDDUD$. 			  &amp; \seqnum{A238846}\\  \hline
$ DU; DDU; UDUU; DUDU; DDDU; UUDUU; UDDUU$      &amp; \seqnum{A001870 }\\
$ DUUDU; DDUDU; DDDDU$   				         &amp; \\  \hline
$ UD; UUDD$    								 &amp; \seqnum{A038731}\\  \hline
$ DUUU; DDUUU$     							 &amp; \seqnum{A197649}\\ \hline
$ UDUD; UDDUD; UUDUD$      					 &amp; \seqnum{A059502 }\\  \hline
$ DUUD; DDUUD$      							 &amp; \seqnum{A377866}\\  \hline
$ DUDD; DDUDD$   								 &amp; \seqnum{A105693 }\\   \hline
\end{tabular}}
\end{center}
\caption{Subwords that share the same sequence.} \label{words_Fibo_Lucas}
\end{table}

These subwords have their unique sequence:  $DDD$, $UUUU$, $UDDD$, $DDDD$, $UUUUU$, $UDUUU$, $UDUDD$, $UDDDD$, $DUUUU$, $DUUUD$, $DUDDD$, and $DDDDD$. 

\section{Acknowledgment}

The first author was partially supported by the Citadel Foundation, Charleston SC. The last two authors were partially supported by Universidad Nacional de Colombia, Project No.\ 57340. 

The authors would like to thank the anonymous referee for their valuable suggestions, which helped improve the readability of the paper.

\begin{thebibliography}{99}
\bibitem{barcucci} E.~Barcucci, A.~Del Lungo, A.~Fezzi, and R.~Pinzani, Nondecreasing Dyck paths and $q$-Fibonacci numbers,
\emph{Discrete Math.} \textbf{170} (1997), 211--217.

\bibitem{CzabarkaFlorezJunes} \'E.~Czabarka, R.~Fl\'orez, and L.~Junes, Some enumerations on non-decreasing Dyck paths,
\emph{Electron. J. Combin.} \textbf{22}  (2015), Paper \#P1.3.

\bibitem{CzabarkaFlorezJunesJose} \'E.~Czabarka, R.~Fl\'orez, L.~Junes, and J.~L.~Ram\'irez,
 Enumerations of peaks and valleys on non-decreasing Dyck Paths, \emph{Discrete Math.}  \textbf{341} (2018), 2789--2807.
 
\bibitem{Deutschenumeration} E.~Deutsch, Dyck path enumeration, \emph{Discrete Math.} \textbf{204} (1999), 167--202.

\bibitem{DeutschP}  E.~Deutsch and H.~Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, \emph{Theoret. Comput. Sci.} \textbf{307} (2003), 319--325. 

\bibitem{ElizaldeFlorezRamirez} S.~Elizalde, R.~Fl\'orez, and J.~L.~Ram\'irez, Enumerating symmetric peaks in nondecreasing Dyck paths. 
  \emph{Ars Math. Contemp}. \textbf{21} (2021), Paper \#P2.04.

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

\bibitem{FlorezJoseJunesasymmetric}
R.~Fl\'orez, L.~Junes,  and J.~L.~Ram\'irez, Counting asymmetric weighted  pyramids in non-decreasing Dyck paths, \emph{Australas. J. Combin.} \textbf{79} (2021), 123--140.

\bibitem{FlorezJoseJunes} R.~Fl\'orez, L.~Junes,  and J.~L.~Ram\'irez, Enumerating several aspects of non-decreasing Dyck paths,
\emph{Discrete Math.} \textbf{342} (2019), 3079--3097.

\bibitem{FlorezJoseSymmDyck} R.~Fl\'orez and J.~L.~Ram\'irez, Enumerating symmetric and asymmetric peaks in Dyck paths, \emph{Discrete  Math.} \textbf{343} (2020), 112118.

\bibitem{FlorezJoseTDyck} R.~Fl\'orez and J.~L.~Ram\'irez,  Enumerations of rational non-decreasing Dyck paths with integer slope, \emph{Graphs Combin.} \textbf{37} (2021),  2775--2801.

\bibitem{FlorezJose} R.~Fl\'orez and J.~L.~Ram\'irez, Some enumerations on non-decreasing Motzkin paths, \emph{Australas. J. Combin.}  \textbf{72} (2018), 138--154.

\bibitem{Mansour} T.~Mansour, Statistics on Dyck paths, \emph{J. Integer Sequences} \textbf{9} (2006),   \href{https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.pdf}{Article 06.1.5}.

\bibitem{Merl} D.~Merlini, R.~Sprugnoli, and M.~C.~Verri, Some statistics on Dyck paths, {\it J. Statist. Plann. Inference} \textbf{101} (2002), 211--227.

\bibitem{MontoyaConde} L.~M. Montoya-Conde, \emph{Conteo de subpalabras de Dyck restringindas}, master's thesis, Universidad Nacional de Colombia, (2025).

\bibitem{Prod} H.~Prodinger, Words, Dyck paths, trees, and bijections, in 
{\it Words, Semigroups, and Transductions},
World  Scientific Publishing, 2001, pp.~369--379.

\bibitem{sloane} N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences, \url{https://oeis.org/}.

\bibitem{Sapounakis} A. Sapounakis, I. Tasoulas, and  P. Tsikouras, Counting strings in Dyck paths, \emph{Discrete  Math.} \textbf{307} (2007), 2909--2924.

\bibitem{Sun} Y.~Sun,   The statistic ``number of udu's" in Dyck paths, \emph{Discrete  Math.} \textbf{287} (2004), 177--186.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 05A19.

\noindent \emph{Keywords:} generating function, non-decreasing Dyck path, subword, Fibonacci.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A001870},
\seqnum{A001871},
\seqnum{A002212},
\seqnum{A030267},
\seqnum{A033321},
\seqnum{A038731},
\seqnum{A039598},
\seqnum{A054444},
\seqnum{A059502},
\seqnum{A105306},
\seqnum{A105693},
\seqnum{A121463},
\seqnum{A121466},
\seqnum{A122737},
\seqnum{A153342},
\seqnum{A197649},
\seqnum{A238846},
\seqnum{A304429},
\seqnum{A375995},
\seqnum{A377670},
\seqnum{A377679},
\seqnum{A377857},
\seqnum{A377866},
\seqnum{A377867}, and
\seqnum{A378383}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 5 2024;
revised version received  February 12 2025.
Published in {\it Journal of Integer Sequences},
February 13 2025.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                



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