Rational Dyck Paths

Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo

Pinzani

Dipartimento di Matematica e Informatica “Ulisse Dini” Università di Firenze Viale G. B. Morgagni 65 50134 Firenze Italy

           elena.barcucci@unifi.it
           antonio.bernini@unifi.it
           stefano.bilotta@unifi.it
            renzo.pinzani@unifi.it

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 ℚ-bonacci numbers.

1 Introduction

Baril et al. [4] introduced a new class of binary strings, called Fibonacci q-decreasing words, and enumerated by the Fibonacci generalized numbers. Barcucci et al. [2, 3] defined a new class of Dyck paths (q-Dyck paths, for short) with the same enumeration. More recently, two consecutive 1-peaks two consecutive 0-valleys 0 1 2

Figure 1: A path P ∈ D_{5} with two consecutive 1-peaks and two consecutive 0-valleys.

Kirgizov introduced a class of words (the ℚ-bonacci words [8]) larger than the one studied by Baril et al. [4] and enumerated by the ℚ-bonacci numbers. Following a similar approach, the present authors defined [1] a class of Dyck paths (Q-bonacci paths, for short) larger than the one introduced by Barcucci et al. [2, 3] and enumerated by the ℚ-bonacci numbers.

In this paper, we define a new class of Dyck paths, 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 [7]. Moreover, since rational Dyck paths contain a subset of paths counted by the ℚ-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.

2 Definition

A Dyck path P is a lattice path in ℤ^{2} from (0, 0) to (2n, 0) with steps in S = {(1, 1), (1, −1)} 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 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 D consisting of Dyck paths with semilength n (i.e., the length divided by 2). The empty path, with semilength 0, is denoted by ε. Clearly, we have D = ⋃_{n≥0} D_{n}.

A 1-peak of P is a substring UD of P where D attains ordinate 1, and a 0–valley is a substring DU of P where D touches the x-axis. In Figure 1 an example is illustrated.

If L_{1} and L_{2} are two subsets of D, then the concatenation L_{1} · L_{2} is the set of all paths of the form P Q where P ∈ L_{1} and Q ∈ L_{2}.

3 Construction and generating function

A path P ∈ D (P ≠ ε) can be factorized by highlighting the blocks of maximal length of consecutive 1-peaks and consecutive 0-valleys as follows:

P = U(UD)^{p_{1}}(DU)^{v_{1}}(UD)^{p_{2}}(DU)^{v_{2}} ⋯ (UD)^{p_{k}}(DU)^{v_{k}}D .  (1)

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 1peaks 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)^{2}D, where k = 2, p_{1} = 2, v_{1} = 3, p_{2} = 1, v_{2} = 2.

Clearly, in (1), 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)^{1}D it is k = 2, p_{1} = 0, v_{1} = 2, p_{2} = 1, v_{2} = 1, while in P = UUDUDD = U(UD)^{2}D, we have k = 1, p_{1} = 2, v_{1} = 0. Finally, the path P = UDUDUUDUDD = U(DU)^{2}(UD)^{2}D 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 ∈ ℚ^{+}), where the integers r and s are coprime.

Definition 1. Let R_{n}^{r/s} be the set of Dyck paths P ∈ D of semilength n where

\frac{p_{i}}{v_{i}} ≤ \frac{r}{s} or, equivalently, v_{i} ≥ ⌈p_{i} · \frac{s}{r}⌉

for i = 1, 2, …, k.

Moreover, let R^{r/s} be the class defined as follows:

R^{r/s} = ⋃_{n≥0} R_{n}^{r/s}.

We refer to R^{r/s} as the class of rational Dyck paths.

In other words, if a rational Dyck paths P contains p consecutive 1-peaks, then they must be immediately followed by at least ⌈p · \frac{s}{r}⌉ consecutive 0-valleys. Moreover, in its factorization (1), we cannot have v_{k} = 0.

Example 2. If q = 3/4 and

P_{1} = UUDDUDUUDUDDUDUD = U(UD)(DU)^{2}(UD)^{2}(DU)^{2}D,

then k = 2, p_{1} = 1, v_{1} = 2, p_{2} = 2, v_{2} = 2. According to Definition 1, we must have v_{2} ≥ 3. Therefore P_{1} ∉ R^{3/4}.

The path

P_{2} = UUDDUDUUDUDUDUDD = U(UD)(DU)^{2}(UD)^{4}D

is not allowed (P_{2} ∉ 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)^{4}D

is allowed.

A path P, different from the empty path ε (P ∈ {R^{r/s}\ε}), can be recursively constructed as follows:

• P = UD · P′, where P′ ∈ R^{r/s} (possibly P′ = ε), either

• P = U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · P′, where P′ ∈ {R^{r/s} \ ε}, and p ≥ 1 .

Note that in the second case we must have P′ ≠ ε. For otherwise in the path P the p consecutive 1-peaks of the prefix U(UD)^{p}(DU)^{⌈ps/r⌉−1}D would not be followed by the correct number of consecutive 0-valleys. This number has to be ⌈ps/r⌉, according to Definition 1. Observing that ⌈ps/r⌉ − 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

R^{r/s} = ε ∪ UD · R^{r/s} ⋃_{p≥1} U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · {R^{r/s} \ ε}.  (2)

We let δ^{r/s}(x) = ∑_{P ∈R^{r/s}} x^{|P |} denote the generating function of R^{r/s}, according to the semilength

of the paths, where |P | denotes the semilength of P. From (2), it is possible to deduce the functional equation for the generating function δ^{r/s}(x), which is

δ^{r/s}(x) = 1 + xδ^{r/s}(x) + ∑_{p≥1} x^{p+⌈ps/r⌉}(δ^{r/s}(x) − 1).  (3)

In Eq. (3), the sum ∑_{p≥1} x^{p+⌈ps/r⌉} can be manipulated so that the functional equation simplifies to

δ^{r/s}(x) = 1 + xδ^{r/s}(x) + (δ^{r/s}(x) − 1) ∑_{k=1}^{r} x^{k+⌈ks/r⌉} ∑_{j≥0} x^{(r+s)j}

= 1 + xδ^{r/s}(x) + (δ^{r/s}(x) − 1) · \frac{∑_{k=1}^{r} x^{k+⌈ks/r⌉}}{1 − x^{r+s}} .  (4)

Thus, the generating function is

δ^{r/s}(x) = \frac{1 − x^{r+s} − ∑_{k=1}^{r} x^{k+⌈ks/r⌉}}{(1 − x)(1 − x^{r+s}) − ∑_{k=1}^{r} x^{k+⌈ks/r⌉}}

= \frac{1 − ∑_{k=1}^{r−1} x^{k+⌈ks/r⌉} − 2x^{r+s}}{1 − x − ∑_{k=1}^{r−1} x^{k+⌈ks/r⌉} − 2x^{r+s} + x^{r+s+1}} .  (5)

From (2) and letting ∅ denote the empty set, it is not difficult to realize that the generation of the sets R_{n}^{r/s} is given by

R_{n}^{r/s} = \begin{cases}ε, & if n = 0; \\ UD · R_{n−1}^{r/s} ⋃_{p≥1}\{Y_{n,p}\}, & if n ≥ 1, \end{cases}  (6)

where

Y_{n,p} = \begin{cases}U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · R_{n−p−⌈ps/r⌉}, & if n − p − ⌈ps/r⌉ ≥ 1; \\ ∅, & otherwise. \end{cases}

Hence, denoting by w_{n}^{r/s} the cardinality of R_{n}^{r/s}, the recurrence relation for w_{n}^{r/s} is

w_{n}^{r/s} = \begin{cases}1, & if n = 0; \\ w_{n−1}^{r/s} + ∑_{p≥1} u_{n,p}, & if n ≥ 1, \end{cases}  (7)

where

u_{n,p} = \begin{cases}w_{n−p−⌈ps/r⌉}, & if n − p − ⌈ps/r⌉ ≥ 1; \\ 0, & otherwise. \end{cases}

4 Links with other structures

If r = s = 1, then the generating function (5) becomes

δ(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, . . .. This is a shifted version of the sequence \underline{A028495} in The On-line Encyclopedia of Integer Sequences [10]. It enumerates the compositions of n with parts in A = {1, 2, 4, 6, …}, according to their length. See Heubach et al. [7] and Baril et al. [5] 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} ∪ {p + ⌈ps/r⌉ | p ≥ 1}.

The bijection is achieved by mapping the part 1 to UD, and the part p + ⌈ps/r⌉ to U(UD)^{p}(DU)^{⌈ps/r⌉−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, …} and the correspondence between C_{n}^{A_{3/4}} and R_{n+1}^{3/4} can be seen in Table 1.

C_{n}^{A_{3/4}}  R_{n+1}^{3/4}
n = 0  ε  UD
n = 1  1  UDUD
n = 2 11  UDUDUD
n = 3 111, 3 UDUDUDUD, UUDDUDUD
1111  UDUDUDUDUD
n = 4 13  UDUUDDUDUD
31  UUDDUDUDUD
11111  UDUDUDUDUDUD
113  UDUDUUDDUDUD
n = 5 131  UDUUDDUDUDUD
311  UUDDUDUDUDUD
5  UUDUDDUDUDUD
⋯  ⋯  ⋯
Table 1: C_{n}^{A_{3/4}} and R_{n+1}^{3/4}

In a recent paper by Kirgizov [8] the concept of q-decreasing words, originally introduced for q ∈ ℕ^{+} [4], has been generalized to the case where q ∈ ℚ^{+}. If q ∈ ℕ^{+}, the q-decreasing words are enumerated [4] by the well-known q-generalized Fibonacci numbers [6, 9], whereas if q ∈ ℚ^{+}, they are enumerated by the so-called ℚ-bonacci numbers [8].

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 \underline{A060961} and \underline{A117760} in The On-line Encyclopedia of Integer Sequences [10], 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

Ã_{r/s} = {1} ∪ {p + ⌈ps/r⌉ | 1 ≤ p ≤ 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 R^{r/s} in order to

• find a subset of Dyck paths in bijection with CÃ_{r/s} ; n;

• find a subset of Dyck paths with the same enumeration of the q-decreasing words according to the semilength, for q ∈ ℚ^{+}.

4.1 Dyck paths and restricted compositions

Referring again to the factorization (1)

P = U(UD)^{p_{1}}(DU)^{v_{1}}(UD)^{p_{2}}(DU)^{v_{2}} ⋯ (UD)^{p_{k}}(DU)^{v_{k}}D

for Dyck paths P ∈ D, we impose a constraint on the number of consecutive 1-peaks within each block.

Definition 3. Let R̃_{n}^{r/s} be the set of Dyck paths P ∈ D of semilength n where

• p_{i} ≤ r for i = 1, 2, …, k;

• for i = 1, 2, …, k, the following condition must hold:

\frac{p_{i}}{v_{i}} ≤ \frac{r}{s} or equivalently v_{i} ≥ ⌈p_{i} · \frac{s}{r}⌉ .

Moreover, let R̃^{r/s} be the class defined as follows:

R̃^{r/s} = ⋃_{n≥0} R̃_{n}^{r/s}.

All the steps presented for R^{r/s} in Section 3 can be easily adapted to Definition 3. More precisely:

• the construction of R̃^{r/s} can be described by

R̃^{r/s} = ε ∪ UD · R̃^{r/s} ⋃_{p=1}^{r} U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · {R̃^{r/s} \ ε};

• the corresponding functional equation for the generating function δ̃^{r/s}(x) of R̃^{r/s} is

δ̃^{r/s}(x) = 1 + xδ̃^{r/s}(x) + ∑_{p=1}^{r} x^{p+⌈ps/r⌉}(δ̃^{r/s}(x) − 1);

• the generating function is

δ̃^{r/s}(x) = \frac{1 − ∑_{p=1}^{r} x^{p+⌈ps/r⌉}}{1 − x − ∑_{p=1}^{r} x^{p+⌈ps/r⌉}};  (8)

• the generation of the sets R̃_{n}^{r/s} is given by

R̃_{n}^{r/s} = \begin{cases}ε, & if n = 0; \\ UD · R̃_{n−1}^{r/s} ⋃_{p=1}^{r}\{Ỹ_{n,p}\}, & if n ≥ 1, \end{cases}

where

Ỹ_{n,p} = \begin{cases}U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · R̃_{n−p−⌈ps/r⌉}, & if n − p − ⌈ps/r⌉ ≥ 1; \\ ∅, & otherwise. \end{cases}

Hence, denoting by w̃_{n}^{r/s} the cardinality of R̃_{n}^{r/s}, the recurrence relation for w̃_{n}^{r/s} is

w̃_{n}^{r/s} = \begin{cases}1, & if n = 0; \\ w̃_{n−1}^{r/s} + ∑_{p=1}^{r} ũ_{n,p}, & if n ≥ 1, \end{cases}  (9)

where

ũ_{n,p} = \begin{cases}w̃_{n−p−⌈ps/r⌉}^{r/s}, & if n − p − ⌈ps/r⌉ ≥ 1; \\ 0, & otherwise. \end{cases}

The bijection between the sets CÃ_{r/s} ; n and 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 4. Here, we note that the set Ã_{r/s}, which contains the parts for the composition of n, is finite. This corresponds to the fact that the paths P ∈ R̃_{n}^{r/s} cannot have more than r consecutive 1-peaks. Moreover, due to the bijection, we observe that w̃_{n}^{r/s} represents the number of composition of n − 1 for n ≥ 1, with parts in Ã^{r/s}. This is the reason why the sequence defined by (9) does not exactly match the sequence enumerating the compositions of n with parts in Ã^{r/s}. Specifically, the sequence (w̃_{n}^{r/s})_{n≥0} is obtained by the one enumerating the compositions by inserting a 1 at the beginning. Indeed, the generating function

\frac{1}{1 − ∑_{ℓ∈Ã^{r/s}} x^{ℓ}}

for the compositions of n with parts in Ã^{r/s} [7] is obtained as δ̃^{r/s}(x) − 1.

4.2 Dyck paths and 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 [8].

Recalling the factorization (1)

P = U(UD)^{p_{1}}(DU)^{v_{1}}(UD)^{p_{2}}(DU)^{v_{2}} ⋯ (UD)^{p_{k}}(DU)^{v_{k}}D

for Dyck paths P ∈ D, we maintain the restriction on the number of consecutive 1-peaks and relax the assumption on v_{k}.

Definition 4. Let Q_{n}^{r/s} be the set of Dyck paths P ∈ D of semilength n where

• p_{i} ≤ r for i = 1, 2, …, k;

• for i = 1, 2, …, k − 1, the following condition must hold:

\frac{p_{i}}{v_{i}} ≤ \frac{r}{s} or equivalently v_{i} ≥ ⌈p_{i} · \frac{s}{r}⌉;

• for i = k

– if p_{k} = r, then v_{k} ≥ 0;

– if p_{k} < r, then either v_{k} = 0 or v_{k} ≥ ⌈p_{k} · \frac{s}{r}⌉ .

Moreover, let Q^{r/s} be the class defined as follows:

Q^{r/s} = ⋃_{n≥0} Q_{n}^{r/s}.

We refer to Q_{n}^{r/s} as the class of Q-bonacci paths.

In other words, in a path P ∈ Q_{n}^{r/s}, a block B of p consecutive 1-peaks must be followed by at least ⌈p · \frac{s}{r}⌉ consecutive 0-valleys. The only case in which B can be followed by less than ⌈p · \frac{s}{r}⌉ 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.

Example 5. If q = 4/5 and

P_{1} = UUDDUDUUDUDDUDUD = U(UD)(DU)^{2}(UD)^{2}(DU)^{2}D,

then k = 2, p_{1} = 1, v_{1} = 2, p_{2} = 2, v_{2} = 2. According to Definition 4, it should be v_{2} ≥ 3. Therefore P_{1} ∉ Q^{4/5}.

The path

P_{2} = UUDDUDUUDUDUDUDDUDUD = U(UD)(DU)^{2}(UD)^{4}(DU)^{2}D

is allowed (P_{2} ∈ Q^{4/5}) since in this case p_{2} = 4 = r, so that the only requirement is v_{2} ≥ 0. The path

P_{3} = UUDDUDUUDUDUDD = U(UD)(DU)^{2}(UD)^{3}D

is allowed since p_{2} = 3 < r and v_{2} = 0.

These Dyck paths were introduced by Barcucci et al. [1], who presented them with a different but equivalent approach. After defining them, and following a similar argument to that used in Section 3, we recall only the key points in order to arrive at the enumerating sequences.

• The construction of Q^{r/s} can be summarized by

Q^{r/s} =ε ∪ UD · Q^{r/s} ⋃_{ℓ=1}^{r+s−1} U pr_{ℓ}((UD)^{r}(DU)^{s−1})D

⋃_{p=1}^{r} U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · {Q^{r/s} \ ε},

where, if A is a path, then pr_{ℓ}(A) denotes the prefix of semilength ℓ of A.

Specifically, a path P ∈ Q^{r/s}, as in the case where P ∈ R̃^{r/s} (Section 4.1), starts with the factor UD, or one of the factors U(UD)^{p}(DU)^{⌈ps/r⌉−1}D with p = 1, 2, …, r, concatenated with a suitable path in Q^{r/s}. In this case (P ∈ Q^{r/s}), the path P can also be a prefix of (UD)^{p}(DU)^{⌈ps/r⌉−1}, preceded by a step U and followed by a step D.

• The functional equation for the generating function χ^{r/s}(x) of Q^{r/s} is

χ^{r/s}(x) = 1 + xχ^{r/s}(x) + ∑_{j=2}^{r+s} x^{j} + ∑_{p=1}^{r} x^{p+⌈ps/r⌉}(χ^{r/s}(x) − 1),

where the last sum tracks the paths given by the prefixes of (UD)^{r}(DU)^{s−1}, preceded by U and followed by D.

• The generating function is

χ^{r/s}(x) = \frac{1 + ∑_{j=2}^{r+s} x^{j} − ∑_{p=1}^{r} x^{p+⌈ps/r⌉}}{1 − x − ∑_{p=1}^{r} x^{p+⌈ps/r⌉}} .

• The generation of the sets Q_{n}^{r/s} is given by

Q_{n}^{r/s} = \begin{cases}ε, & if n = 0; \\ UD, & if n = 1; \\ UD · Q_{n−1}^{r/s} ∪ U pr_{n−1}((UD)^{r}(DU)^{s−1})D ⋃_{p=1}^{r}\{S_{n,p}\}, & if n ≥ 2, \end{cases}

where

S_{n,p} = \begin{cases}U(UD)^{p}(DU)^{⌈ps/r⌉−1}D · Q_{n−p−⌈ps/r⌉}, & if n − p − ⌈ps/r⌉ ≥ 1; \\ ∅, & otherwise. \end{cases}

Hence, denoting by v_{n}^{r/s} the cardinality of Q_{n}^{r/s}, the recurrence relation for v_{n}^{r/s} is

v_{n}^{r/s} = \begin{cases}1, & if n = 0; \\ v_{n−1}^{r/s} + ∑_{p=1}^{r} t_{n,p}, & if n ≥ 1, \end{cases}  (10)

where

t_{n,p} = \begin{cases}v_{n−p−⌈ps/r⌉}^{r/s}, & if n − p − ⌈ps/r⌉ ≥ 1; \\ 0, & otherwise. \end{cases}

Denoting by W_{r/s}(x) the generating function for the q-decreasing words as defined in [8], it is routine to check that

χ^{r/s}(x) = 1 + xW_{r/s}(x) ,

so that the sequences (v_{n}^{r/s})_{n≥0} are obtained by inserting a 1 at the beginning of the sequences enumerating the q-decreasing words. Hence, all the sequences obtained in [8] have a different combinatorial interpretation in terms of Q-bonacci paths.

4.3 The classes Q^{r/s} and R̃^{r/s}

In this section, we prove that, for certain cases, some subsets of Q^{r/s} and R̃^{r/s} are in bijection. More precisely, we state the following proposition.

Proposition 6. If s = tr + 1 with t ∈ ℕ, then there exists a bijection ϕ : Q_{n}^{r/s} → R̃_{n+t+1}^{r/s}, for n ≥ 0.

Proof. Let P be a path such that P ∈ Q_{n}^{r/s}. The general idea to obtain the corresponding path ϕ(P) in R̃_{n+t+1}^{r/s} is to add the suffix (UD)^{t+1} (so that ϕ(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 (1), if p_{k} = j, let ν_{j} be the quantity ν_{j} = ⌈j · \frac{s}{r}⌉, so that v_{k} ≥ ν_{j}, according to Definition 3. It is easy to check that

ν_{j} = jt + 1,  (11)

being 1 ≤ j ≤ r.

We consider the following cases:

• If P ∈ R̃_{n}^{r/s}(⊆ Q_{n}^{r/s}), then it is easily seen that ϕ(P) = P (UD)^{t+1} ∈ R̃_{n+t+1}^{r/s};

• If P = αU(UD)^{j}D ∈ Q_{n}^{r/s}, where α ∈ R̃_{n−j−1}^{r/s}, then the path ϕ(P) can be expressed by ϕ(P) = αU(UD)^{j−h}(DU)^{h}D(UD)^{t+1} with h is the minimum integer such that h+t+1 ≥ ν_{j−h} = t(j −h)+1, taking into account formula (11). Hence h = ⌈\frac{jt+1}{t+1} − 1⌉.

Suppose there exists P′ ∈ R̃_{n}^{r/s} such that ϕ(P) = ϕ(P′). Then we can write P′ = αU(UD)^{j−h}(DU)^{h}D. According to formula (11), we have h ≥ (j − h)t + 1, which implies h ≥ ⌈\frac{jt+1}{t+1}⌉. This leads to the inequality h > ⌈\frac{jt+1}{t+1} − 1⌉, against the preceding value of h.

• If P = αU(UD)^{r}(DU)^{j}D, with 1 ≤ j ≤ s − 1, then we distinguish two cases:

– if j ≥ s − t − 1, then ϕ(P) = P (UD)^{t+1} ∈ R̃_{n+t+1}^{r/s};

– if 1 ≤ j < s − t − 1, then ϕ(P) = αU(UD)^{r−h}(DU)^{j+h}D(UD)^{t+1}, with h is the minimum integer such that j + h + t + 1 ≥ ν_{r−h} = (r − h)t + 1 thanks to (11), hence h = ⌈\frac{rt−j+1}{t+1} − 1⌉.

By using similar arguments described in the previous bullet, one can show that there does not exists P′ ∈ R̃_{n}^{r/s} such that ϕ(P) = ϕ(P′).

The inverse map ϕ^{−1} can be obtained by similar considerations. Given P ∈ R̃_{n+t+1}^{r/s} of the form P = αU(UD)^{j}(DU)^{h}D, with h ≥ ν_{j} ≥ t + 1 and α ∈ R̃_{n+t−j−h}^{r/s}, we consider the following cases:

• if h−(t+1) ≥ ν_{j}, then ϕ^{−1}(P) = αU(UD)^{j}(DU)^{h−t−1}D, which belongs to R̃_{n}^{r/s}(⊆ Q_{n}^{r/s});

• if h − (t + 1) < ν_{j} and j + h − t − 1 ≤ r, then ϕ^{−1}(P) = αU(UD)^{j+h−t−1}D, which belongs to Q_{n}^{r/s};

• if h − (t + 1) < ν_{j} and j + h − t − 1 > r, then ϕ^{−1}(P) = αU(UD)^{r}(DU)^{j+h−t−1−r}D, which belongs to Q_{n}^{r/s}.

It is routine to show that ϕ(ϕ^{−1}(P)) = P. The map ϕ is the required bijection. Note that, the hypothesis s = tr + 1 is not used in the definition of ϕ^{−1}.

If s ≠ tr + 1, then tr + 1 < s < (t + 1)r. In this case, we have t ≤ ν_{j+1} − ν_{j} ≤ t + 1 and of course, there exists j such that ν_{j+1} + ν_{j} = t + 1. Let j_{0} be the smallest integer such that ν_{r−j_{0}} − ν_{r−(j_{0}+1)} = t + 1. We have ν_{r−j_{0}} = s − tj_{0} and ν_{r−(j_{0}+1)} = s − t(j_{0} + 1) − 1. We now show that there exist two paths, P, P′ ∈ Q_{n}^{r/s}, such that ϕ(P) = ϕ(P′). Let P, P′ be the paths

P = αU(UD)^{r}(DU)^{s−(t+1)(j_{0}+1)−1}D ∈ Q_{n}^{r/s} \ R̃_{n}^{r/s}

and

P′ = αU(UD)^{r−(j_{0}+1)}(DU)^{s−t(j_{0}+1)−1}D ∈ R̃_{n}^{r/s}.

By applying the map ϕ, we obtain ϕ(P) = ϕ(P′) = αU(UD)^{r−(j_{0}+1)}(DU)^{s−t(j_{0}+1)+t}D. Hence, the map ϕ is not injective, but it is surjective. Therefore, the sets R̃_{n+t+1}^{r/s} and Q_{n}^{r/s} have different cardinalities, and the following proposition is proved.

Proposition 7. The sets R̃_{n+t+1}^{r/s} and Q_{n}^{r/s} are in bijection if and only if s = tr + 1.

We point out that in the class of Q-bonacci paths, there are rational Dyck paths. These are exactly the paths in the class R̃^{r/s}. In other words

R^{r/s} ∩ Q^{r/s} = R̃^{r/s} .

5 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 [1] and ℚ-bonacci words in [8] are both enumerated by ℚ-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.

6 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”.

References

[1] E. Barcucci, A. Bernini, S. Bilotta, and R. Pinzani, Dyck paths enumerated by the ℚ-bonacci numbers, in S. Brlek and L. Ferrari, eds., Proc. GASCom 2024, Electron. Proc. Theor. Comput. Sci. (EPTCS), Vol. 403, 2024, pp. 49–53.

[2] E. Barcucci, A. Bernini, and R. Pinzani, From the Fibonacci to Pell numbers and beyond via Dyck paths, Pure Math. Appl. 30 (2022), 17–22.

[3] E. Barcucci, A. Bernini, and R. Pinzani, Sequences from Fibonacci to Catalan: A combinatorial interpretation via Dyck paths, RAIRO Theor. Inform. Appl. 58 (2024), #8.

[4] J.-L. Baril, S. Kirgizov, and V. Vajnovszki, Gray codes for Fibonacci q-decreasing words, Theoret. Comput. Sci. 297 (2022), 120–132.

[5] J.-L. Baril, J. L. Ramírez, and F. A. Velandia, Bijections between directed-column convex polyominoes and restricted compositions, Theoret. Comput. Sci. 1003 (2024), 114626.

[6] M. Feinberg, Fibonacci-Tribonacci, Fibonacci Quart. 1 (1963), 71–74.

[7] S. Heubach and T. Mansour, Compositions of n with parts in a set, Congr. Numer. 168 (2004), 127–143.

[8] S. Kirgizov, ℚ-bonacci words and numbers, Fibonacci Quart. 60 (2022), 187–195.

[9] E. P. Miles, Jr., Generalized Fibonacci numbers and associated matrices. Amer. Math. Monthly 67 (1960), 745–752.

[10] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 05A05, 05A15. Keywords: Dyck path, composition, ℚ-bonacci number.

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

Received September 11 2024; revised version received April 15 2025. Published in Journal of Integer Sequences, April 15 2025.

Return to Journal of Integer Sequences home page.