\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{tikz}

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

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

\usepackage[usenames]{color}
\usepackage{fullpage}
\usepackage{float}
\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}}}

\DeclareMathOperator{\pr}{\text{pr}}

\begin{document}

\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}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}


\begin{center}
\vskip 1cm{\LARGE\bf Rational Dyck Paths\\
}

\vskip 1cm
{\Large
{Elena Barcucci, Antonio Bernini,
 Stefano Bilotta, and Renzo Pinzani}\\
Dipartimento di Matematica e Informatica ``Ulisse Dini''\\
Universit\`a di Firenze\\
Viale G. B. Morgagni 65 \\
50134 Firenze\\
Italy\\
\href{mailto:elena.barcucci@unifi.it}{\tt elena.barcucci@unifi.it} \\
\href{mailto:antonio.bernini@unifi.it}{\tt antonio.bernini@unifi.it} \\
\href{mailto:stefano.bilotta@unifi.it}{\tt stefano.bilotta@unifi.it} \\
\href{mailto:renzo.pinzani@unifi.it}{\tt renzo.pinzani@unifi.it} \\
}
\end{center}

\vskip .2 in
\begin{abstract}
Given a positive rational $q$, we consider Dyck paths of height at most two, subject to constraints on the number of consecutive peaks and consecutive valleys depending on $q$. We introduce a general class of Dyck paths, named rational Dyck paths, and provide the associated generating function based on their semilength, along with a construction for this class. Moreover, we characterize certain subsets of rational Dyck paths that are enumerated by the $\mathbb Q$-bonacci numbers.
\end{abstract}


\section{Introduction}
Baril et al.\ \cite{BKV} introduced a new class of binary strings, called Fibonacci $q$-decreasing words, and enumerated by the Fibonacci generalized numbers. Barcucci et al.\ \cite{BBP1,BBP2} defined a new class of Dyck paths ({\it $q$-Dyck paths}, for short) with the same enumeration.
More recently, Kirgizov introduced a class of words (the $\mathbb Q$-bonacci words \cite{Ki}) larger than the one studied by Baril et al.\  \cite{BKV} and enumerated by the $\mathbb Q$-bonacci numbers. Following a similar approach, the present authors defined \cite{BBBP} a class of Dyck paths ({\it $Q$-bonacci paths}, for short) larger than the one introduced by Barcucci et al.\ \cite{BBP1,BBP2} and enumerated by the $\mathbb Q$-bonacci numbers.

In this paper, we define a new class of Dyck paths, {\it rational Dyck paths}. We provide their construction and generating function (which turns out to be rational). We also present a very simple bijection between them and compositions of integers with parts in a set \cite{HM}.
Moreover, since rational Dyck paths contain a subset of paths counted by the $\mathbb Q$-bonacci numbers, we give a bijection between this subset and a corresponding subset of paths in the set of $Q$-bonacci paths.
Finally, we show that no bijection can exist between the remaining rational Dyck paths and the remaining $Q$-bonacci paths.

\section{Definition}
A Dyck path $P$ is a lattice path in $\mathbb {Z} ^{2}$ from 
$(0,0)$ to $(2n,0)$ with steps in $S=\lbrace (1,1),(1,-1)\rbrace$ that never passes below the $x$-axis. The step $(1,1)$ is abbreviated by the letter $U$ and the step $(1,-1)$ by $D$, so that $P$ can be represented by a string over the alphabet $\{U,D\}.$

The height of $P$ is the maximum ordinate reached by its $U$ steps. In this paper we consider the set $\mathcal D$ of Dyck paths with height at most $2$.

The length of $P$ is the number of its steps. We let $D_n$ denote  the subset of $\mathcal D$ consisting of Dyck paths with semilength $n$ (i.e., the length divided by $2$). The empty path, with semilength $0$, is denoted by $\varepsilon$.
Clearly, we have $\mathcal D=\displaystyle \bigcup_{n\geq 0} D_n$.

A \emph{1-peak} of $P$ is a substring $UD$ of $P$ where $D$ attains ordinate $1$, and a \emph{0--valley} is a substring $DU$ of $P$ where $D$ touches the $x$-axis. In Figure \ref{picchi} an example is illustrated. 

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.9]
\draw [help lines] (8,0) grid +(10,2);
\draw [line width=.3] (8,0)--(9,1);
\draw [line width=.6](9,1)-- (10,2)--(11,1)--(12,2)--(13,1);
\draw [line width=1.3](13,1)--(14,0)--(15,1)--(16,0)--(17,1);
\draw [line width=.3](17,1)--(18,0);
\draw (9,1) node [scale=0.2, circle, draw,fill=black]{};
\draw (10,2) node [scale=0.2, circle, draw,fill=black]{};
\draw (11,1) node [scale=0.2, circle, draw,fill=black]{};
\draw (12,2) node [scale=0.2, circle, draw,fill=black]{};
\draw (13,1) node [scale=0.3, circle, draw,fill=black]{};
\draw (14,0) node [scale=0.3, circle, draw,fill=black]{};
\draw (15,1) node [scale=0.3, circle, draw,fill=black]{};
\draw (16,0) node [scale=0.3, circle, draw,fill=black]{};
\draw (17,1) node [scale=0.3, circle, draw,fill=black]{};
\draw (11,3) node [scale=.7]{two consecutive};
\draw (11,2.4) node [scale=.7]{$1$-peaks};
\draw (15.2,-.4) node [scale=.7]{two consecutive};
\draw (15.2,-1) node [scale=.7]{$0$-valleys};
\draw (7.5,0) node [scale=.55]{0};
\draw (7.5,1) node [scale=.55]{1};
\draw (7.5,2) node [scale=.55]{2};
 \end{tikzpicture}
 \end{center}
 \caption{A path $P\in D_5$ with two consecutive $1$-peaks and two consecutive $0$-valleys.}
 \label{picchi}
\end{figure}
If $L_1$ and $L_2$ are two subsets of $\mathcal D$, then the concatenation $L_1\cdot L_2$ is the set of all paths of the form $PQ$ where $P\in L_1$ and $Q\in L_2$.

\section{Construction and generating function}\label{Section3}

A path $P \in \mathcal{D}$ ($P \neq \varepsilon$) can be factorized by highlighting the blocks of maximal length of consecutive $1$-peaks and consecutive 0-valleys as follows:
\begin{equation}
\label{factorization} P = U(UD)^{p_1}(DU)^{v_1}(UD)^{p_2}(DU)^{v_2} \cdots (UD)^{p_k}(DU)^{v_k}D\ .
\end{equation}
For clarity, the expression $(UD)^{p_j}$ (resp., $(DU)^{v_j}$) refers to the concatenation of $p_j$ (resp., $v_j$) copies of $(UD)$ (resp., $(DU)$).
Moreover, the quantities $p_j$ and $v_j$ represent the number of $1$-peaks and $0$-valleys, respectively, occurring in the $j$-th block of maximal length that contains $1$-peaks or $0$-valleys. For example, the path $P=UUDUDDUDUDUUDDUDUD$ can be factorized as $P=U(UD)^2(DU)^3(UD)^1(DU)^2D$, where $k=2,p_1=2,v_1=3,p_2=1,v_2=2$.

Clearly, in (\ref{factorization}),  it may hold that $p_1 = 0$ or $v_k = 0$ (or both). For example, in the path $P=UDUDUUDDUD=U(DU)^2(UD)^1(DU)^1D$ it is $k=2, p_1=0,v_1=2,p_2=1,v_2=1$, while in $P=UUDUDD=U(UD)^2D$, we have $k=1, p_1=2,v_1=0$. Finally, the path $P=UDUDUUDUDD=U(DU)^2(UD)^2D$ has $k=2, p_1=0,v_1=2, p_2=2,v_2=0$.
It may also happen that $k=0$. In this case, the path $P$ is $UD$.

Let $q = r/s$ be a positive rational number ($q \in \mathbb{Q}^+$), where the integers $r$ and $s$ are coprime.

\begin{definition}\label{Def1}
Let $ R_n^{r/s}$ be the set of Dyck paths $P\in\mathcal D$ of semilength $n$ where
$$
\frac{p_i}{v_i}\leq \frac{r}{s}
\text{ or, equivalently, $v_i\geq \left\lceil p_i\cdot\frac{s}{r}\right\rceil$}
$$
for $i=1,2,\ldots,k.$

Moreover, let $\mathcal R^{r/s}$ be the class defined as follows:
$$
\mathcal R^{r/s}=\bigcup_{n\geq 0}R_n^{r/s}.
$$
We refer to $\mathcal R^{r/s}$ as the class of \emph{rational Dyck paths}.
\end{definition}

In other words, if a rational Dyck paths $P$ contains $p$ consecutive $1$-peaks, then they must be immediately followed by at least
$\left\lceil p\cdot\frac{s}{r}\right\rceil$ consecutive $0$-valleys.
Moreover, in its factorization (\ref{factorization}), we cannot have $v_k=0$.

\begin{example}
If $q=3/4$ and
$$
P_1=UUDDUDUUDUDDUDUD=U(UD)(DU)^2(UD)^2(DU)^2D,
$$
then $k=2, p_1=1, v_1=2, p_2=2, v_2=2$. According to Definition \ref{Def1}, we must have $v_2\geq3$. Therefore $P_1\notin \mathcal R^{3/4}$.

The path
$$
P_2=UUDDUDUUDUDUDUDD=U(UD)(DU)^2(UD)^4D
$$
is not allowed $(P_2\notin \mathcal R^{3/4})$ since in this case $v_2=0$ (there are no valleys after the last block of $1$-peaks).

The path
$$
P_3=UUDDUDUUDUDDUDUDUDUD=U(UD)(DU)^2(UD)^2(DU)^4D
$$
is allowed.
\end{example}
A path $P$, different from the empty path $\varepsilon$ $\bigl(P\in \{\mathcal R^{r/s}\setminus \varepsilon\}\bigr)$, can be recursively constructed as follows:
\begin{itemize}
\item $P=UD\cdot P', \text{ where } P'\in\mathcal R^{r/s} \text{ (possibly $P'=\varepsilon$)}$, either
\item $P=U(UD)^p(DU)^{\lceil ps/r \rceil-1}D\cdot P', \text{ where } P'\in\{\mathcal R^{r/s}\setminus\varepsilon\}, \text{ and } p\geq 1$ .
\end{itemize}

Note that in the second case we must have $P'\not=\varepsilon.$ For otherwise in the path $P$ the $p$ consecutive $1$-peaks of the prefix $U(UD)^p(DU)^{\lceil ps/r \rceil-1}D$ would not be followed by the correct number of consecutive $0$-valleys. This number has to be $\lceil ps/r \rceil$, according to Definition \ref{Def1}. Observing that $\lceil ps/r \rceil-1$ consecutive $0$-valleys occur in the prefix itself, the missing one is given by the last $D$ step of the prefix, followed by the first $U$ step of $P'$.


Therefore, the construction of rational Dyck paths can be expressed by
\begin{equation}\label{costruzione}
\mathcal R^{r/s}=\varepsilon\ \cup\ UD\cdot\mathcal R^{r/s}\ 
\bigcup_{p\geq 1} U(UD)^p(DU)^{\lceil ps/r \rceil-1}D\cdot\{\mathcal 
R^{r/s}\setminus\varepsilon\}.
\end{equation}
We let $\delta ^{r/s}(x)=\displaystyle\sum_{P\in\mathcal 
R^{r/s}}x^{|P|}$ denote the generating function of $\mathcal R^{r/s}$, 
according to the semilength of the paths, where $|P|$ denotes the 
semilength of $P$. From (\ref{costruzione}), it is possible to deduce 
the functional equation for the generating function $\delta 
^{r/s}(x)$, which is
\begin{equation}\label{eq_funzionale}
\delta ^{r/s}(x)=1 + x\delta ^{r/s}(x) + 
\sum_{p\geq 1} x^{p+\lceil ps/r \rceil}\bigl(\delta ^{r/s}(x)-1\bigr).
\end{equation}
In Eq.~(\ref{eq_funzionale}), the sum $\sum_{p\geq 1} x^{p+\lceil ps/r \rceil}$
can be manipulated so that the functional equation simplifies to
\begin{align}\label{funzione_generatrice}
\delta ^{r/s}(x)&=1 + x\delta^{r/s}(x) + 
\bigl(\delta^{r/s}(x)-1\bigr)
\sum_{k= 1}^{r} x^{k+\lceil ks/r \rceil}
\sum_{j\geq 0}x^{(r+s)j}\nonumber\\
&=1+ x\delta^{r/s}(x) + 
\bigl(\delta^{r/s}(x)-1\bigr)\cdot\frac{\displaystyle\sum_{k= 1}^{r} x^{k+\lceil ks/r \rceil}}{1-x^{r+s}}\ .
\end{align}
Thus, the generating function is
\begin{align}\label{GEN_FUN}
\delta^{r/s}(x)&=\frac{1-x^{r+s}-\displaystyle\sum_{k= 1}^{r} x^{k+\lceil ks/r \rceil}}{(1-x)(1-x^{r+s})-\displaystyle\sum_{k= 1}^{r} x^{k+\lceil ks/r \rceil}}\nonumber\\
&=\frac{1-\displaystyle\sum_{k= 1}^{r-1} x^{k+\lceil ks/r \rceil}-2x^{r+s}}{1-x-\displaystyle\sum_{k= 1}^{r-1} x^{k+\lceil ks/r \rceil}-2x^{r+s}+x^{r+s+1}}.
\end{align}
From (\ref{costruzione}) and letting $\emptyset$ denote the empty set, it is not difficult to realize that the generation of the sets
$R_n^{r/s}$ is given by
\begin{equation}
R_n^{r/s}=
\begin{cases}
\varepsilon,  & \text{if $n=0$};\\
UD\cdot R_{n-1}^{r/s}\displaystyle\bigcup_{p\geq1} \{Y_{n,p}\}, & \text{if $n\geq1$},\\
\end{cases} 
\end{equation}
where
\begin{equation*}
Y_{n,p}=
\begin{cases}
U(UD)^{p}(DU)^{\lceil{p s/r}\rceil-1}D\cdot R_{n-p-\lceil{p s/r}\rceil},  & \text{if $n-p-\lceil{p s/r}\rceil\geq1$};\\
\emptyset,  & \text{otherwise.}\\
\end{cases}
\end{equation*}
Hence, denoting by $w_n^{r/s}$ the cardinality of
$R_n^{r/s}$,  the recurrence relation for $w_n^{r/s}$ is
\begin{equation}
w_n^{r/s}=
\begin{cases}
1,  & \text{if $n=0$};\\
w_{n-1}^{r/s}+ \displaystyle\sum_{p\geq 1}u_{n,p}, & \text{if $n\geq1$},\\
\end{cases} 
\end{equation}
where
\begin{equation*}
u_{n,p}=
\begin{cases}
w_{n-p-\lceil{p s/r}\rceil},  & \text{if $n-p-\lceil{p s/r}\rceil\geq1$};\\
0,  & \text{otherwise.}\\
\end{cases}
\end{equation*}

\section{Links with other structures}\label{LINK}
If $r=s=1$, then the generating function (\ref{GEN_FUN}) becomes
$$
\delta (x)=\frac{1-2x^2}{1-x-2x^2+x^3}
$$
which corresponds to the sequence $1,1,1,2,3,6,10,19,33,\ldots$. This is a shifted version of the sequence \seqnum{A028495} in The On-line Encyclopedia of Integer Sequences \cite{S}. It enumerates the compositions of $n$ with parts in $A=\{1,2,4,6,\ldots\}$, according to their length. See Heubach et al.\ \cite{HM} and Baril et al.\  \cite{BRV} for more information.

On closer inspection, our sets $R_{n+1}^{r/s}$ are in bijection with the sets of compositions $C_n^{A_{r/s}}$ of $n$ with parts in the set
$$A_{r/s}=\{1\}\cup\{p+\lceil ps/r\rceil \mid p\geq 1\}.$$
The bijection is achieved by mapping the part $1$ to $UD$, and the part $p+\lceil ps/r\rceil$ to $U(UD)^{p}(DU)^{\lceil{p s/r}\rceil-1}D$. Finally, we add the factor $UD$ at the end of the resulting Dyck path.
For example, if $q=3/4$, then $A_{3/4}=\{{1,3,5,7,10,12,14,\ldots}\}$ and the correspondence between $C_n^{A_{3/4}}$ and $R_{n+1}^{3/4}$ can be seen in Table \ref{Table1}.

\begin{table}[ht]
\centering
\begin{tabular}{ | l | c | c |}
       \hline 
          & $C_n^{A_{3/4}}$ & $R_{n+1}^{3/4}$ \\ \hline
    $n=0$ & $\varepsilon$ & $UD$ \\ \hline
    $n=1$ & $1$ & $UDUD$ \\ \hline
    $n=2$ & $11$ & $UDUDUD$ \\ \hline
    $n=3$ & $111,\ 3$ & $UDUDUDUD$, $UUDDUDUD$ \\ \hline
 		  & $1111$ & $UDUDUDUDUD$\\	   
    $n=4$ & $13$ & $UDUUDDUDUD$ \\ 
          & $31$ & $UUDDUDUDUD$ \\ 
    \hline
    	  & $11111$ & $UDUDUDUDUDUD$ \\    
    	  & $113$   & $UDUDUUDDUDUD$ \\	   
    $n=5$ & $131$   & $UDUUDDUDUDUD$ \\ 
          & $311$   & $UUDDUDUDUDUD$ \\ 
    	  & $5$     & $UUDUDDUDUDUD$ \\
    \hline
  $\cdots$& $\cdots$& $\cdots$\\   
    \hline    
\end{tabular}
\caption{$C_n^{A_{3/4}}$ and $R_{n+1}^{3/4}$}
\label{Table1}
\end{table}
In a recent paper by Kirgizov \cite{Ki} the concept of $q$-decreasing words, originally introduced for $q\in \mathbb N^+$  \cite{BKV}, has been generalized to the case where $q\in\mathbb Q^+$.
If $q\in \mathbb N^+$, the $q$-decreasing words are enumerated \cite{BKV} by the well-known $q$-generalized Fibonacci numbers \cite{F,M}, whereas if $q\in \mathbb Q^+$, they are enumerated by the so-called $\mathbb Q$-bonacci numbers \cite{Ki}.

For certain values $q=r/s$, the $n$-length $q$-decreasing words are enumerated by sequences that, when properly filled with 1's at the beginning, coincide with sequences enumerating restricted compositions of $n$ with a finite number of parts, depending on $r/s$.
For example, the sequences \seqnum{A060961} and \seqnum{A117760} in The On-line Encyclopedia of Integer Sequences \cite{S}, corresponding to the values $q=2/3$ and $q=3/4$, enumerate the $q$-decreasing words and the compositions of $n$ with parts in $\{1,3,5\}$ and $\{1,3,5,7\}$, respectively.

More precisely, the involved compositions are the ones where the summands of $n$ belong to the finite set 
$$
\widetilde{A}_{r/s}=\{1\}\cup\{p+\lceil ps/r\rceil \mid 1\leq p\leq r\}.
$$

This particular context, where restricted compositions, Dyck paths, and $q$-decreasing words appear to be connected in an intriguing way, prompted us to investigate the set $\mathcal R^{r/s}$  in order to  
\begin{itemize}
\item find a subset of Dyck paths in bijection with $C_n^{\widetilde{A}_{r/s}}$;
\item find a subset of Dyck paths with the same enumeration of the $q$-decreasing words according to the semilength, for $q\in\mathbb Q^+$.
\end{itemize}

\subsection{Dyck paths and restricted compositions}\label{COMP}
Referring again to the factorization (\ref{factorization}) 
\begin{equation*}
	P=U(UD)^{p_1}(DU)^{v_1}(UD)^{p_2}(DU)^{v_2}\cdots(UD)^{p_k}(DU)^{v_k}D
\end{equation*}
for Dyck paths $P\in\mathcal D$, we impose a constraint on the number 
of consecutive $1$-peaks within each block. 

\begin{definition}\label{Def3}
	Let $\widetilde R_n^{r/s}$ be the set of Dyck paths $P\in\mathcal D$ of semilength $n$ where
	\begin{itemize}
		\item $p_i\leq r$ for $i=1,2,\ldots,k$;
		\item for $i=1,2,\ldots,k$, the following condition must hold: 
		$$
		\frac{p_i}{v_i}\leq \frac{r}{s}
		\text{ or equivalently $v_i\geq \left\lceil p_i\cdot\frac{s}{r}\right\rceil.$}
		$$
	\end{itemize}
	Moreover, let $\widetilde R^{r/s}$ be the class defined as follows:
	$$
	\widetilde{\mathcal R}^{r/s}=\bigcup_{n\geq 0}\widetilde R_n^{r/s}.
	$$ 
\end{definition}
All the steps presented for $\mathcal R^{r/s}$ in Section \ref{Section3} can be easily adapted to Definition \ref{Def3}. More precisely:
\begin{itemize}
	\item the construction of $\widetilde{\mathcal R}^{r/s}$ can be described by
	\begin{equation*}
		\widetilde{\mathcal R}^{r/s}=\varepsilon\ \cup\ UD\cdot
		\widetilde{\mathcal R}^{r/s}\ 
		\bigcup_{p=1}^r U(UD)^p(DU)^{\lceil ps/r \rceil-1}D\cdot
		\{\widetilde{\mathcal R}^{r/s}\setminus\varepsilon\};
	\end{equation*}
	\item the corresponding functional equation for the generating function $\widetilde{\delta}^{r/s}(x)$ of $\widetilde{\mathcal R}^{r/s}$ is
	\begin{equation*}
		\widetilde{\delta}^{r/s}(x)=1 + x\widetilde{\delta}^{r/s}(x) + 
		\sum_{p=1}^{r} x^{p+\lceil ps/r \rceil}\bigl(\widetilde{\delta}^{r/s}(x)-1\bigr);
	\end{equation*}
	\item the generating function is
	\begin{equation}\label{gen_fun_tilde}
		\widetilde{\delta}^{r/s}(x)=\frac{1-\displaystyle\sum_{p=1}^{r} x^{p+\lceil ps/r \rceil}}{1-x-\displaystyle\sum_{p= 1}^{r} x^{p+\lceil ps/r \rceil}};
	\end{equation}
	\item the generation of the sets $\widetilde R_n^{r/s}$ is given by
	\begin{equation*}
		\widetilde R_n^{r/s}=
		\begin{cases}
			\varepsilon,  & \text{if $n=0$};\\
			UD\cdot\widetilde R_{n-1}^{r/s}\displaystyle\bigcup_{p=1}^r \{\widetilde{Y}_{n,p}\}, & \text{if $n\geq1$},\\
		\end{cases} 
	\end{equation*}
	where
	\begin{equation*}
		\widetilde{Y}_{n,p}=
		\begin{cases}
			U(UD)^{p}(DU)^{\lceil{p s/r}\rceil-1}D\cdot\widetilde R_{n-p-\lceil{p s/r}\rceil},  & \text{if $n-p-\lceil{p s/r}\rceil\geq1$};\\
			\emptyset,  & \text{otherwise.}\\
		\end{cases}
	\end{equation*}
	Hence, denoting by $\widetilde{w}_n^{r/s}$ the cardinality of
	$\widetilde R_n^{r/s}$,  the recurrence relation for $\widetilde{w}_n^{r/s}$ is
	\begin{equation}\label{rec_rel_tilde}
		\widetilde{w}_n^{r/s}=
		\begin{cases}
			1,  & \text{if $n=0$};\\
			\widetilde{w}_{n-1}^{r/s}+ \displaystyle\sum_{p=1}^r\widetilde{u}_{n,p}, & \text{if $n\geq1$},\\
		\end{cases} 
	\end{equation}
	where
	\begin{equation*}
		\widetilde{u}_{n,p}=
		\begin{cases}
			\widetilde{w}^{r/s}_{n-p-\lceil{p s/r}\rceil},  & \text{if $n-p-\lceil{p s/r}\rceil\geq1$};\\
			0,  & \text{otherwise}.\\
		\end{cases}
	\end{equation*}
\end{itemize}
The bijection between the sets $C_n^{\widetilde{A}_{r/s}}$
and $\widetilde R_{n+1}^{r/s}$ is the same as the one between the sets $C_n^{A_{r/s}}$ and $R_{n+1}^{r/s}$, defined at the beginning of Section \ref{LINK}. Here, we note that the set $\widetilde{A}_{r/s}$, which contains the parts for the composition of $n$, is finite. This corresponds to the fact that the paths $P\in\widetilde R_n^{r/s}$ cannot have more than $r$ consecutive $1$-peaks. Moreover, due to the bijection, we observe that $\widetilde{w}_n^{r/s}$ represents the number of composition of $n-1$ for $n\geq 1$, with parts in $\widetilde{A}^{r/s}$. This is the reason why the sequence defined by (\ref{rec_rel_tilde}) does not exactly match
the sequence enumerating the compositions of $n$ with parts in $\widetilde{A}^{r/s}$. Specifically, the sequence $(\widetilde{w}_n^{r/s})_{n\geq 0}$ is obtained by the one enumerating the compositions by inserting a $1$ at the beginning. Indeed, the generating function
$$
\frac{1}{1-\displaystyle\sum_{\ell\in\widetilde{A}^{r/s}}x^{\ell}}
$$
for the compositions of $n$ with parts in $\widetilde{A}^{r/s}$ \cite{HM} is obtained as $\widetilde{\delta}^{r/s}(x)-1$.


\subsection{Dyck paths and \texorpdfstring{$q$}{q}-decreasing words}
Here, we consider the family of Dyck paths that have the same enumeration  (according to their semilength) of $q$-decreasing words, as generalized by Kirgizov \cite{Ki}.

Recalling the factorization (\ref{factorization}) 
\begin{equation*}
P=U(UD)^{p_1}(DU)^{v_1}(UD)^{p_2}(DU)^{v_2}\cdots(UD)^{p_k}(DU)^{v_k}D
\end{equation*}
for Dyck paths $P\in\mathcal D$, we maintain the restriction on the number of consecutive $1$-peaks and relax the assumption on $v_k$. 



\begin{definition}\label{decreasing}
Let ${\text Q}_n^{r/s}$ be the set of Dyck paths $P\in\mathcal D$ of semilength $n$ where

\begin{itemize}
\item $p_i\leq r$ for $i=1,2,\ldots,k$;
\item for $i=1,2,\ldots,k-1$, the following condition must hold:
$$
\frac{p_i}{v_i}\leq \frac{r}{s}
\text{\qquad  or equivalently $v_i\geq \left\lceil p_i\cdot\frac{s}{r}\right\rceil;$}
$$
\item for $i=k$
\begin{itemize}
\item if $p_k=r$, then $v_k\geq 0$;
\item if $p_k<r$, then
 either $v_k=0$ or $v_k\geq \left\lceil p_k\cdot\frac{s}{r}\right\rceil.$
\end{itemize}
\end{itemize}
Moreover, let $\mathcal Q^{r/s}$ be the class defined as follows:
$$
\mathcal Q^{r/s}=\bigcup_{n\geq 0}Q_n^{r/s}.
$$
We refer to $Q_n^{r/s}$ as the class of \emph{$Q$-bonacci paths}.
\end{definition}
In other  words, in a path $P\in Q_n^{r/s}$,	 a block $B$ of $p$ consecutive $1$-peaks must be followed by at least $\lceil p\cdot\frac{s}{r}\rceil$ consecutive $0$-valleys. The only case in which $B$ can be followed by less than $\lceil p\cdot\frac{s}{r}\rceil$ consecutive $0$-valleys is when $B$ is the last block and $B=(UD)^r$. Moreover, the $p$ consecutive $1$-peaks in each $B$ cannot exceed $r$.

\begin{example}
If $q=4/5$ and
$$
P_1=UUDDUDUUDUDDUDUD=U(UD)(DU)^2(UD)^2(DU)^2D,
$$
then $k=2, p_1=1, v_1=2, p_2=2, v_2=2$. According to Definition \ref{decreasing}, it should be $v_2\geq3$. Therefore $P_1\notin \mathcal Q^{4/5}$.

The path
$$
P_2=UUDDUDUUDUDUDUDDUDUD=U(UD)(DU)^2(UD)^4(DU)^2D
$$
is allowed $(P_2\in \mathcal Q^{4/5})$ since in this case $p_2=4=r$, so that the only requirement is $v_2\geq 0$.

The path
$$
P_3=UUDDUDUUDUDUDD=U(UD)(DU)^2(UD)^3D
$$
is allowed since $p_2=3<r$ and $v_2=0$.
\end{example}
These Dyck paths were introduced by Barcucci et al.\ \cite{BBBP}, who presented them with a different but equivalent approach. After defining them, and following a similar argument to that used in Section \ref{Section3}, we recall only the key points in order to arrive at the enumerating sequences.

\begin{itemize}
	\item The construction of $\mathcal Q^{r/s}$ can be summarized by
	\begin{align*}
		\mathcal Q^{r/s}=&\varepsilon\ \cup\ UD\cdot
		\mathcal Q^{r/s}\ 
		\bigcup_{\ell=1}^{r+s-1} U \pr_{\ell} \bigl((UD)^r(DU)^{s-1}\bigr)D\\
		&\bigcup_{p=1}^r U(UD)^p(DU)^{\lceil ps/r \rceil-1}D\cdot
		\{\mathcal Q^{r/s}\setminus\varepsilon\},
	\end{align*}
	where, if $A$ is a path, then $\pr_{\ell}(A)$ denotes the prefix of semilength $\ell$ of $A$.
	
	Specifically, a path $P\in\mathcal Q^{r/s}$, as in the case where $P\in \widetilde{\mathcal R}^{r/s}$ (Section \ref{COMP}),  starts with the factor $UD$, or one of the factors $U(UD)^p(DU)^{\lceil ps/r \rceil-1}D$ with $p=1,2,\ldots,r$, concatenated with a suitable path in $\mathcal Q^{r/s}$. In this case ($P\in\mathcal Q^{r/s}$), the path $P$ can also be a prefix of $(UD)^p(DU)^{\lceil ps/r \rceil-1}$, preceded by a step $U$ and followed by a step $D$.     
	\item The functional equation for the generating function $\chi^{r/s}(x)$ of $\mathcal Q^{r/s}$ is
	\begin{equation*}
		\chi^{r/s}(x)=1 + x\chi^{r/s}(x) +
		\sum_{j=2}^{r+s}x^j\  
		+\sum_{p=1}^{r} x^{p+\lceil ps/r \rceil}\bigl(\chi^{r/s}(x)-1\bigr),
	\end{equation*}
where the last sum tracks the paths given by the prefixes of 
$(UD)^r(DU)^{s-1}$, preceded by $U$ and followed by $D$.	
	\item The generating function is
	\begin{equation*}
		\chi^{r/s}(x)=\frac
		{1+\displaystyle\sum_{j=2}^{r+s}x^j-\sum_{p=1}^{r}x^{p+\lceil ps/r \rceil}}
		{1-x-\displaystyle\sum_{p=1}^{r}x^{p+\lceil ps/r \rceil}}\ .
	\end{equation*}
	\item The generation of the sets
	$Q_n^{r/s}$ is given by
	
	\begin{equation*}
		Q_n^{r/s}=
		\begin{cases}
			\varepsilon,  & \text{if $n=0$};\\
			UD,&\text{if $n=1$};\\
			UD\cdot Q_{n-1}^{r/s}
			\cup U \pr_{n-1}\bigl((UD)^r(DU)^{s-1}\bigr)D		
			\displaystyle\bigcup_{p=1}^r \{S_{n,p}\}, & \text{if $n\geq2$},\\
		\end{cases} 
	\end{equation*}
	where
	\begin{equation*}
		S_{n,p}=
		\begin{cases}
			U(UD)^{p}(DU)^{\lceil{p s/r}\rceil-1}D\cdot Q_{n-p-\lceil{p s/r}\rceil},  & \text{if $n-p-\lceil{p s/r}\rceil\geq1$};\\
			\emptyset,  & \text{otherwise.}\\
		\end{cases}
	\end{equation*}
	Hence, denoting by $v_n^{r/s}$ the cardinality of
	$Q_n^{r/s}$,  the recurrence relation for $v_n^{r/s}$ is
	\begin{equation}%\label{rec_rel_tilde}
		v_n^{r/s}=
		\begin{cases}
			1,  & \text{if $n=0$};\\
			v_{n-1}^{r/s}+ \displaystyle\sum_{p=1}^rt_{n,p}, & \text{if $n\geq1$},\\
		\end{cases} 
	\end{equation}
	where
	\begin{equation*}
		t_{n,p}=
		\begin{cases}
			v^{r/s}_{n-p-\lceil{p s/r}\rceil},  & \text{if $n-p-\lceil{p s/r}\rceil\geq1$};\\
			0,  & \text{otherwise.}\\
		\end{cases}
	\end{equation*}
\end{itemize} 
Denoting by $W_{r/s}(x)$ the generating function for the
$q$-decreasing words as defined in \cite{Ki}, it is routine to check that
$$
\chi^{r/s}(x)=1+xW_{r/s}(x)\ ,
$$
so that the sequences $\bigl(v_n^{r/s}\bigr)_{n\geq 0}$ are obtained
by inserting a $1$ at the beginning of the sequences enumerating the $q$-decreasing words. Hence, all the sequences obtained in \cite{Ki} have a different combinatorial interpretation in terms of $Q$-bonacci paths.



\subsection{The classes \texorpdfstring{$\mathcal Q^{r/s}$}{Qrs} and \texorpdfstring{$\widetilde{\mathcal R}^{r/s}$}{Drs}
}
In this section, we prove that, for certain cases, some subsets of $\mathcal Q^{r/s}$ and $\widetilde{\mathcal R}^{r/s}$ are in bijection. More precisely, we state the following proposition.

\begin{proposition}
	If $s=tr+1$ with $t \in \mathbb{N}$, then there exists a bijection $\phi: Q_n^{r/s} \rightarrow \widetilde{R}_{n+t+1}^{r/s}$, for $n \geq 0$.
\end{proposition}   

\begin{proof}	
	Let $P$ be a path such that $P\in Q_n^{r/s}$. The general idea to obtain the corresponding path $\phi(P)$ in $\widetilde R_{n+t+1}^{r/s}$ is to add the suffix $(UD)^{t+1}$ (so that $\phi(P)$ ends with at least $t+1$ consecutive $0$-valleys and its semilength is exactly $n+t+1$) and, eventually, replace a suitable number of the  rightmost $p_k$ consecutive $1$-peaks of $P$ with $0$-valleys.
	
	Referring to factorization (\ref{factorization}), if $p_k = j$, let $\nu_j$ be the quantity $\nu_j=\left\lceil j\cdot\frac{s}{r}\right\rceil$, so that $v_k \geq \nu_j$, according to Definition \ref{Def3}.
		It is easy to check that 
	\begin{equation}\label{nu}
		\nu_j=jt+1,
	\end{equation}
	being $1 \leq j \leq r$.
	
	We consider the following cases:
	\begin{itemize}
		\item If $P \in \widetilde{R}_{n}^{r/s} (\subseteq Q_n^{r/s})$, then it is easily seen that $\phi(P)=P (UD)^{t+1} \in \widetilde{R}_{n+t+1}^{r/s}$;
		\item If $P=\alpha U (UD)^j D \in Q_n^{r/s}$, where $\alpha \in \widetilde{R}_{n-j-1}^{r/s}$, then the path $\phi(P)$ can be expressed by $\phi(P)=\alpha U (UD)^{j-h} (DU)^h D (UD)^{t+1}$ with $h$ is the minimum integer such that $h+t+1 \geq \nu_{j-h}= t(j-h)+1$, taking into account formula (\ref{nu}). Hence $h =\left\lceil \frac{jt+1}{t+1} -1\right\rceil $. 
		
		Suppose there exists $P' \in \widetilde{R}_n^{r/s}$ such that 
		$\phi(P)=\phi(P')$. Then we can write $P'=\alpha U (UD)^{j-h} 
		(DU)^h D$. According to formula (\ref{nu}), we have $h \geq 
		(j-h)t+1$, which implies $h \geq \left\lceil 
		\frac{jt+1}{t+1}\right\rceil$. This leads to the inequality 
		$ h > \left\lceil \frac{jt+1}{t+1} -1\right\rceil$, against 
		the preceding value of $h$.
		
		\item If $P=\alpha U (UD)^r (DU)^j D$, with $1 \leq j \leq s-1$, then we distinguish two cases: 
		\begin{itemize}
			\item if $j \geq s-t-1$, then $\phi(P)=P (UD)^{t+1} \in \widetilde{R}_{n+t+1}^{r/s}$;
			\item if $1 \leq j < s-t-1$, then $\phi(P)=\alpha U (UD)^{r-h} (DU)^{j+h} D (UD)^{t+1}$, with $h$ is the minimum integer such that $j+h+t+1 \geq \nu_{r-h}= (r-h)t+1$ thanks to (\ref{nu}), hence $h =\left\lceil \frac{rt-j+1}{t+1} -1\right\rceil $.    
		\end{itemize}
		By using similar arguments described in the previous bullet, one can show that there does not exists $P' \in \widetilde{R}_n^{r/s}$ such that $\phi(P)=\phi(P')$.  
	\end{itemize}	
	
	The inverse map $\phi^{-1}$ can be obtained by similar considerations. Given $P \in \widetilde{R}_{n+t+1}^{r/s}$ of the form $P=\alpha U (UD)^j (DU)^h D$, with $h \geq \nu_j \geq t+1 $ and $\alpha \in \widetilde{R}_{n+t-j-h}^{r/s}$, we consider the following cases:
	
	\begin{itemize}
		\item if $h-(t+1) \geq \nu_j$, then $\phi^{-1}(P)=\alpha U (UD)^j (DU)^{h-t-1} D$, which belongs to $\widetilde{R}_{n}^{r/s} (\subseteq Q_n^{r/s})$;
		\item if $h-(t+1) < \nu_j$ and $j+h-t-1 \leq r$, then $\phi^{-1}(P)=\alpha U (UD)^{j+h-t-1}D$, which belongs to $Q_n^{r/s}$;
		\item if $h-(t+1) < \nu_j$ and $j+h-t-1 > r$, then $\phi^{-1}(P)=\alpha U (UD)^r (DU)^{j+h-t-1-r} D$, which belongs to $Q_n^{r/s}$.
	\end{itemize}    
	It is routine to show that $\phi(\phi^{-1}(P))=P$. The map $\phi$ is the required bijection. Note that, the hypothesis $s=tr+1$ is not used in the definition of $\phi^{-1}$.
\end{proof}
If $s \neq tr + 1$, then $tr+1 < s < (t+1)r$. In this case, we have $t\leq \nu_{j+1} - \nu_j \leq t+1$ and of course, there exists $j$ such that $\nu_{j+1} + \nu_j=t+1$. Let $j_0$ be the smallest integer such that $\nu_{r-j_0} -\nu_{r-(j_0+1)}=t+1$. We have $\nu_{r-j_0} = s-tj_0$ and $\nu_{r-(j_0+1)}=s-t(j_0+1)-1$. We now show that there exist two paths, $P,P'\in \mathcal Q_n^{r/s}$, such that $\phi(P)=\phi(P')$. Let $P,P'$ be the paths
$$
P=\alpha U (UD)^r (DU)^{s-(t+1)(j_0+1)-1}D \in  Q_n^{r/s} \setminus \widetilde{R}_{n}^{r/s}
$$
and
$$
P'=\alpha U (UD)^{r-(j_0+1)} (DU)^{s-t(j_0+1)-1}D \in \widetilde{R}_{n}^{r/s}.
$$
By applying the map $\phi$, we obtain $\phi(P)=\phi(P')=\alpha U (UD)^{r-(j_0+1)} (DU)^{s-t(j_0+1)+t}D$. Hence, the map $\phi$ is not injective, but it is surjective. Therefore, the sets $\widetilde{R}_{n+t+1}^{r/s}$ and $Q_n^{r/s}$ have different cardinalities, and the following proposition is proved.

\begin{proposition}
	The sets $\widetilde{R}_{n+t+1}^{r/s}$ and $Q_n^{r/s}$ are in bijection if and only if $s=tr+1$.
\end{proposition}
We point out that in the class of $Q$-bonacci paths, there are rational Dyck paths. These are exactly the paths in the class $\widetilde{\mathcal R}^{r/s}$. In other words

$$
\mathcal R^{r/s}\cap\mathcal Q^{r/s} =\widetilde{\mathcal R}^{r/s}\ .
$$

\section{Further work}
In our opinion, there are several open questions that deserve to be addressed. One of the most intriguing is the fact that $Q$-bonacci paths in \cite{BBBP} and $\mathbb{Q}$-bonacci words in \cite{Ki} are both enumerated by $\mathbb Q$-bonacci numbers. Nevertheless, an explicit bijection between the mentioned classes has not yet been defined. 

A second one could deal with the definition of a Gray code for rational Dyck paths or/and $Q$-bonacci paths. 

\section{Acknowledgment}

This work has been partially supported by the 
``INdAM---GNCS 2024 Project", codice CUP---E53C23001670001
``Strutture discrete in informatica: permutazioni, parking functions, linguaggi formali, ipergrafi" and by the 
``INdAM---GNCS 2025 Project", codice CUP---E53C24001950001
``Strutture combinatorie discrete nella matematica e nell'informatica".


\begin{thebibliography}{99}

\bibitem{BBBP} E.\ Barcucci, A.\ Bernini, S.\ Bilotta, and R.\ Pinzani, Dyck paths enumerated by the $\mathbb Q$-bonacci numbers,
in S. Brlek and L. Ferrari, eds.,
{\it Proc. GASCom 2024}, Electron. Proc. Theor. Comput. Sci. (EPTCS),
Vol. 403, 2024, pp. 49--53.

\bibitem{BBP1} E.\ Barcucci, A.\ Bernini, and R.\ Pinzani,
From the {F}ibonacci to {P}ell numbers and beyond via {D}yck paths,
{\it Pure Math. Appl.}
{\bf 30}
(2022),	17--22.

\bibitem{BBP2} E.\ Barcucci, A.\ Bernini, and R.\ Pinzani,
Sequences from Fibonacci to Catalan: A combinatorial interpretation via Dyck paths,
{\it RAIRO Theor. Inform. Appl.} {\bf 58}
(2024),	\#8.


\bibitem{BKV} J.-L.\ Baril, S.\ Kirgizov, and V.\ Vajnovszki,
Gray codes for Fibonacci $q$-decreasing words,
{\it Theoret. Comput. Sci.} {\bf 297} (2022), 120--132.

\bibitem{BRV} J.-L.\ Baril, J.\ L.\ Ram\'irez, and F.\ A.\ Velandia, Bijections between directed-column convex polyominoes and
restricted compositions, {\it Theoret. Comput. Sci.} {\bf 1003} (2024), 114626.

\bibitem{F} M.\ Feinberg, Fibonacci-Tribonacci, {\it Fibonacci Quart.} {\bf 1} (1963), 71--74.


\bibitem{HM} S.\ Heubach and T.\ Mansour, Compositions of $n$ with parts in a set, {\it Congr. Numer.} {\bf 168} (2004), 127--143.

\bibitem{Ki} S.\ Kirgizov, $\mathbb{Q}$-bonacci words and numbers, {\it Fibonacci Quart.} {\bf 60} (2022), 187--195.

\bibitem {M} E.\ P.\ Miles, Jr., Generalized Fibonacci numbers and associated matrices. {\it Amer. Math. Monthly} {\bf 67} (1960), 745--752.

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


\end{thebibliography}
\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: }  Dyck path, composition, $\mathbb Q$-bonacci number.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A028495}, \seqnum{A060961}, and \seqnum{A117760}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 11 2024;
revised version received  April 15 2025.
Published in {\it Journal of Integer Sequences}, April 15 2025.

\bigskip
\hrule
\bigskip

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


\end{document}
