Critical valleys in binary paths

1. Introduction

Let \(\mathcal{P}_n\), where \(n\) is a positive integer, be the set of all binary paths \(P\) of length \(|P| = n\), i.e., lattice paths \(P = p_1 p_2 \cdots p_n\) where each step \(p_i\), \(i \in [n] = \{1,2,\ldots, n\}\), is either an upstep \(u = (1,1)\) or a downstep \(d = (1,-1)\) and connects two consecutive points of the path \(P\). The number of \(u\)’s (resp. \(d\)’s) in \(P\) is denoted by \(|P|_u\) (resp. \(|P|_d\)). An ascent (resp. descent) of \(P\) is a maximal sequence of consecutive \(u\)’s (resp. \(d\)’s) in \(P\). A peak (resp. valley) of the path is the last point of an ascent (resp. descent). Clearly, every peak (resp. valley) corresponds to either an occurrence of \(ud\) (resp. \(du\)), or an occurrence of \(u\) (resp. \(d\)) at the end of the path. A peak (resp. valley) of \(P\) that is the last point of the step \(p_i\) is odd iff \(i\) is odd. We set \(\mathcal{P} = \bigcup_{n \ge 0} \mathcal{P}_n\), where \(\mathcal{P}_0 = \{\varepsilon\}\) and \(\varepsilon\) is the empty path (the path with no steps).

It is convenient to regard the starting point of a path as the origin of a pair of axes. The height of a lattice point is its \(y\)-coordinate. Note that, under this convention, the coordinates of the last point of \(P\) are \((|P|_u + |P|_d, |P|_u – |P|_d)\). Under this geometric representation, a natural partial ordering is defined on \(\mathcal{P}_n\): for any \(P, Q \in \mathcal{P}_n\), we have \(P \le Q\) iff \(P\) lies (weakly) below \(Q\). We note that \(Q\) covers \(P\) whenever \(Q\) is obtained from \(P\) by turning exactly one of \(P\)’s valleys into a peak. It is well-known that the poset \((\mathcal{P}_n, \le)\), or simply \(\mathcal{P}_n\), is a finite, self-dual, distributive, graded lattice whose minimum and maximum elements are the paths \(d^n = \underbrace{d d \cdots d}_{n \ \rm{times}}\) and \(u^n = \underbrace{u u \cdots u}_{n \ \rm{times}}\), respectively.

An odd valley of \(P = p_1p_2\cdots p_n\in \mathcal{P}_n\) that is the last point of \(p_i\) is critical whenever \(|p_1 p_2 \cdots p_{i-1}|_u\) is even. Equivalently, a valley with coordinates \((x,y)\) is critical iff \(x \equiv 1 \pmod{4}\) and \(y \equiv 3 \pmod{4}\) or vice versa (see Figure 1). Indeed, if \(i=1\), then \((x,y) = (1,-1) \equiv (1,3) \pmod{4}\), whereas for \(i>1\), setting \(L = p_1 p_2 \cdots p_{i-1}\), this valley \((x,y)\) is critical iff \(x = |Lp_i| = i\) is odd (since it must be an odd valley) and \(|L|_u\) is even, so that setting \(|L|_u = 2m\), we have that \[x + y = |Lp_i|_u + |Lp_i|_d + |Lp_i|_u – |Lp_i|_d = 2|Lp_i|_u = 2|L|_u = 4m.\]

It follows that the valley is critical iff \(x,y\) are odd and not congruent modulo 4.

The notion of critical valleys was introduced in [9], where the authors studied the Hamiltonicity of the Hasse graph \(G(P)\) of the interval \([d^{n-2}ud, P]\) in the lattice \((\mathcal{P}_n, \leq)\) and gave a necessary and sufficient condition for \(G(P)\) to be Hamiltonian, stated below in Theorem 1.1. Note that, since \(G(dP)\) is isomorphic to \(G(P)\), it is enough to consider only paths starting with \(u\).

Theorem 1.1 (Tasoulas et al. [9]). Let \(P \in \mathcal{P}\) be a path starting with \(u\). Then \(G(P)\) is Hamiltonian iff \(P\) has at least two peaks and either

• i) \(P\) ends with \(u\), or

• ii) \(P\) ends with \(d\) and has odd length and no critical valleys, or

• iii) \(P\) ends with \(ud\) and has even length, even \(|P|_d\) and no critical valleys.

Note that the restrictions of case (ii) imply that \(|P|_d\) is even (otherwise the last step of \(P\) is a critical valley). We set \(\mathcal{H}\) to be the set of paths \(P \in \mathcal{P}\) starting with \(u\) such that \(G(P)\) is Hamiltonian. We also set \(\mathcal{O}\) to be the set of paths in \(\mathcal{P}\) of even length, starting with \(u\) and having odd \(|P|_u\) and no critical valleys. Using this notation, Theorem 1.1 is equivalent to \[P \in \mathcal{H} \Leftrightarrow P \text{ has at least two peaks and } P \in \{ uP'u: P' \in \mathcal{P}\} \cup \{ P'd: P' \in \mathcal{O}\} \cup \{P'ud: P' \in \mathcal{O}\}, \tag{1}\] where each set of this union corresponds to one of the disjoint cases (i), (ii), (iii) of Theorem 1.1. Thus, in order to enumerate the set \(\mathcal{H}\), it is enough to enumerate \(\mathcal{O}\) and then exclude paths with fewer than two peaks. In the following, we enumerate the set \(\mathcal{O}\) and its subset \(\mathcal{O}(d)\) of paths ending with \(d\), and we present a bijection \(\theta\) between \(\mathcal{O}\) and order-consecutive partitions and a bijection \(\phi\) between \(\mathcal{O}(d)\) and generalized compositions. We also enumerate the set \(\mathcal{P}_n\) with respect to critical valleys.

2. Enumeration results

In order to gain more insight into the structure of the paths in \(\mathcal{O}\) and the interaction between steps that gives rise to critical valleys, we transform every path \(P \in \mathcal{P}\) of even length into a word \(f(P) \in \{u,d,p,v\}^*\) by reading the steps of \(P\) in pairs from left to right and transforming each pair according to the rules \[uu \mapsto u, \qquad dd \mapsto d, \qquad ud \mapsto p, \qquad du \mapsto v.\]

For example, for the path \[P = u^3 d^2 ud ud^4 = uu \ ud \ du \ du \ dd \ dd,\] we have \(f(P) = u p v v d d\).

Since the paths \(P\) have even length, the mapping \(f\) is injective and we set \(\mathcal{Q} = f(\mathcal{O})\). The letters \(v\) (resp. \(p\)) of \(f(P)\) correspond to odd valleys (resp. odd peaks) of \(P\).

Moreover, we denote by \(\mathcal{Q}^{(0)}\) the set of paths in \(\mathcal{Q}\) with no occurrence of \(v\) and by \(\mathcal{W}\) the set of paths in \(\{u,d,p\}^*\) that are either empty or start with \(u\) or \(p\).

Lemma 2.1.

• i) \(\mathcal{Q}^{(0)} = \{ Q \in \mathcal{W}: |Q|_p \text{ is odd}\}\).

• ii) \(Q \in \mathcal{Q}^{(0)}\) iff \(Q = ad^{k} W\), where \(k \geq 0\), \(W \in \mathcal{W}\) and \(a = \begin{cases} u, & \text{if } |W|_p \text{ is odd}, \\ p, & \text{if } |W|_p \text{ is even}. \end{cases}\)

• iii) \(Q \in \mathcal{Q}^{(0)}\) iff \(Q = Wad^{k}\), where \(k \geq 0\), \(W \in \mathcal{W}\) and \(a = \begin{cases} u, & \text{if } |W|_p \text{ is odd}, \\ p, & \text{if } |W|_p \text{ is even}. \end{cases}\)

Proof. i) Let \(Q \in \{u,d,p\}^* \supset \mathcal{Q}^{(0)}\) and let \(P = f^{-1}(Q)\), so that \(|P|_u = 2|Q|_u + |Q|_p \equiv |Q|_p \pmod{2}\). By definition, \(Q \in \mathcal{Q}^{(0)}\) iff \(P\in \mathcal{O}\) and \(P\) has no odd valleys, i.e., iff \(P\) starts with \(u\), \(P\) has no odd valleys and \(|P|_u\) is odd. Thus, \(Q \in \mathcal{Q}^{(0)}\) iff \(Q \in \mathcal{W}\) and \(|Q|_p\) is odd.

ii) Every \(Q \in \mathcal{Q}^{(0)}\) starts with a letter \(a \in \{u, p\}\), followed by a maximal run of \(k \geq 0\) letters \(d\) and then a word \(W \in \mathcal{W}\). Since, according to (i), \(|Q|_p\) must be odd, it follows that the letter \(a\) is completely determined by the parity of \(|W|_p\).

iii) Every \(Q \in \mathcal{Q}^{(0)}\) has a rightmost occurrence of \(a \in \{u, p\}\) which is followed by a maximal run of \(k \geq 0\) letters \(d\). Since \(Q\) starts with \(u\) or \(p\), it follows that \(Q = Wad^k\). Moreover, since, according to (i), \(|Q|_p\) must be odd, it follows that the letter \(a\) is completely determined by the parity of \(|W|_p\). \(\square\)

Lemma 2.2. Let \(P\) be a binary path of even length with \(\rho > 0\) odd valleys and let \(W = f(P)\). Then,

• i) \(P\) has no critical valleys iff \(W\) is decomposed as \[W = d^{\lambda_0}W_0 vd^{\lambda_1} W_1 \cdots vd^{\lambda_\rho} W_\rho,\] where \(\lambda_0, \ldots, \lambda_\rho \in \mathbb{N}\), \(W_0, \ldots, W_{\rho-1} \in \mathcal{Q}^{(0)}\) and \(W_\rho \in \mathcal{W}\).

• ii) \(P \in \mathcal{O}\) iff \(W\) is decomposed as \[W = W_0 vd^{\lambda_1} W_1 \cdots vd^{\lambda_\rho} W_\rho,\] where \(\lambda_1, \ldots, \lambda_\rho \in \mathbb{N}\), \(W_0, \ldots, W_{\rho} \in \mathcal{Q}^{(0)}\).

Proof. i) \(P\) has \(\rho\) odd valleys, so that \(|W|_v = \rho\). Thus, \(W\) is decomposed with respect to the occurrences of \(v\) as \(W= d^{\lambda_0}W_0 vd^{\lambda_1} W_1 \cdots vd^{\lambda_\rho} W_\rho\), where \(\lambda_0, \ldots, \lambda_\rho \in \mathbb{N}\), \(W_0, \ldots W_{\rho} \in \mathcal{W}\). Moreover, \(P\) has no critical valleys iff every \(v\) in \(W\) appears in an even position of the subword of \(W\) formed by the letters in \(\{p,v\}\), which is true iff \(|W_j|_p\) is odd for \(0 \leq j < \rho\). Indeed, if \(j< \rho\) is the minimum index for which \(|W_j|_p\) is even, then the \((j+1)\)-st occurrence of \(v\), which immediately follows \(W_j\) would correspond to a critical valley. Hence, \(P\) has no critical valleys iff \(W_0, \ldots, W_{\rho-1} \in \mathcal{Q}^{(0)}\).

ii) Moreover, \(P \in \mathcal{O}\) iff it has no critical valleys (i.e., \(W\) is decomposed as in (i)), starts with \(u\) (i.e., \(\lambda_0 = 0\)) and \(|P|_u\) is odd. Since, according to (i), \(|W_j|_p\) is odd for \(0 \leq j < \rho\), we have that \[|P|_u \equiv |W|_p + |W|_v \equiv |W_{\rho}|_p + \sum\limits_{j=0}^{\rho-1} (|W_j|_p+1) \equiv |W_{\rho}|_p \pmod{2},\] so that \(W_{\rho} \in \mathcal{Q}^{(0)}\) and hence (ii) holds. \(\square\)

2.1. Enumeration of \(\mathcal{O}\)

We enumerate the set \(\mathcal{O}\) via its image \(\mathcal{Q} = f(\mathcal{O})\).

Proposition 2.3. The generating function \(Q(x) = \sum\limits_{Q \in \mathcal{Q}} x^{|Q|}\) of the set \(\mathcal{Q}\), where the variable \(x\) encodes the length, is given by \[Q(x) = \frac{(1-x)x}{1-4x+2x^2} = x + 3 x^2 + 10 x^3 + 34 x^4 + 116 x^5 + 396 x^6 + 1352 x^7 + 4616 x^8 + 15760 x^9 + \cdots \tag{2}\]

Proof. According to Lemma 2.1, a word in \(\mathcal{Q}^{(0)}\) can be any (ternary) word in \(\{u,d,p\}^*\) subject to the restriction that it must start with \(u\) or \(p\) and it must contain an odd number of \(p\)’s, thus it has the form \(aX\), where \(X\) is any word in \(\{u,d,p\}^*\) and \(a = p\) if \(|X|_p\) is even, or \(a=u\) if \(|X|_p\) is odd. It follows that the generating function (GF) \(Q_0(x) = \sum\limits_{Q \in \mathcal{Q}^{(0)}} x^{|Q|}\) of \(\mathcal{Q}^{(0)}\) with respect to the length, encoded by the variable \(x\), is equal to \[Q_0(x) = \sum\limits_{n \geq 1} 3^{n-1}x^n = \frac{x}{1-3x}. \tag{3}\]

Furthermore, according to Lemma 2.2ii), every word \(Q \in \mathcal{Q} \setminus \mathcal{Q}^{(0)}\) is decomposed (with respect to its leftmost \(v\)) as \[Q = Q_0 vd^{\lambda} Q', \qquad \text{where } Q_0 \in \mathcal{Q}^{(0)}, \quad Q' \in \mathcal{Q}, \quad \lambda \in \mathbb{N}. \tag{4}\]

It follows from (4) that the corresponding GF \(Q(x)\) of \(\mathcal{Q}\) satisfies \[Q(x) – Q_0(x) = Q_0(x) \frac{x}{1-x} Q(x),\] which, combined with (3), gives (2). \(\square\)

The coefficients \([x^n]Q(x)\) are sequence \(A007052(n-1)\) in OEIS [7], counting order-consecutive partition sequences (OCPS) of \([n]\) (see F. Hwang and C. Mallows [5]), Kepler walls with \(n\) bricks having one top brick in column \(0\) and all other bricks in columns \(-2\), \(-1\), \(0\), \(1\), \(2\), or \(3\) (see A. Duane and E. Egge, [3]), nested convex topologies of \([n]\) (see T. Clark and T. Richmond [2]), balls-into-boxes with \(n\) singleton boxes (see V. Strehl [8]), compositions of \(n\) where part \(k\) comes in \(F_{2k-1}\) colors (\(F_k\) is the \(k\)-th Fibonacci number) (see J. Gil and J. Tomasko [4]). In Section 3, we present a bijection \(\theta\) from \(\mathcal{Q}\) to the set of all OCPS.

2.2. Enumeration of \(\mathcal{O}(d)\)

In this section, we enumerate the set \(\mathcal{O}(d)\) of all paths in \(\mathcal{O}\) ending with \(d\), via its image \(\mathcal{R} = f(\mathcal{O}(d))\) (since the restriction of \(f\) to \(\mathcal{O}(d)\) is also injective). Note that \(\mathcal{R}\) consists of all words in \(\mathcal{Q}\) that end with \(d\) or \(p\).

Proposition 2.4. The generating function \(R(x) = \sum\limits_{R \in \mathcal{R}} x^{|R|}\) of the set \(\mathcal{R}\), where the variable \(x\) encodes the length, is given by \[\begin{aligned} R(x) =& \frac{x(1-x)^2}{1-4x+2x^2}\\ =&x + 2 x^2 + 7x^3+24 x^4+82 x^5+280 x^6+956 x^7\notag\\&+3264 x^8+11144 x^9+38048 x^{10}+ \cdots \end{aligned}\tag{5}\]

Proof. First, we consider the set \(\mathcal{R}^{(0)}\) of words in \(\mathcal{R}\) with no occurrence of \(v\). Clearly, a word in \(\mathcal{R}^{(0)}\) can be any (ternary) word in \(\{u,d,p\}^*\) subject to the restriction that it must start with \(u\) or \(p\), end with \(d\) or \(p\) and it must contain an odd number of \(p\)’s, thus it has the form \(p\) or \(aXb\), where \(X \in \{u,d,p\}^*\), \(b \in \{d,p\}\) and \(a = p\) if \(|Xb|_p\) is even, or \(a=u\) if \(|Xb|_p\) is odd. It follows that the GF of \(\mathcal{R}^{(0)}\) with respect to the length, encoded by the variable \(x\), is equal to \[R_0(x) = x + 2\sum\limits_{n \geq 2} 3^{n-2} x^{n} = x + \frac{2x^2}{1-3x} = \frac{x(1-x)}{1-3x}. \tag{6}\]

Furthermore, according to Lemma 2.2ii), every word \(R \in \mathcal{R} \setminus \mathcal{R}^{(0)}\) is decomposed as \[R = Q_0 vd^{\lambda} R', \qquad \text{where } Q_0 \in \mathcal{Q}^{(0)}, \quad R' \in \mathcal{R}, \quad \lambda \in \mathbb{N}. \tag{7}\] It follows from (7) that the corresponding GF \(R(x)\) of \(\mathcal{R}\) satisfies \[R(x) – R_0(x) = Q_0(x) \frac{x}{1-x} R(x),\] which, combined with (3) and (6), gives (5). \(\square\)

The coefficients \([x^{n+1}]R(x)\), \(n \in \mathbb{N}\), are sequence \(A003480(n)\) in [7], counting generalized compositions (GC) of \(n\), i.e., compositions where each part of size \(i\) is colored with one out of \(i+1\) colors (see M. Janjic [6]) and \(L\)-convex polyominoes with semiperimeter \(n+2\) (see G. Castiglione, A. Frosini, E. Munarini, A. Restivo and S. Rinaldi [1]). In Section 4, we present a bijection \(\phi\) from \(\mathcal{R}\) to the set of all GC.

2.3. Enumeration of \(\mathcal{H}\)

Proposition 2.5. The generating function \(H(t) = \sum\limits_{P \in \mathcal{H}} t^{|P|}\) of the set \(\mathcal{H}\), where the variable \(t\) encodes the length, is given by \[\begin{aligned} H(t) &= \frac{t^2}{1-2t} – \frac{t^2}{1-t} -\frac{t^3}{(1-t^2)^2} + tQ(t^2) + t^2Q(t^2)\\ & = t^3+4 t^4+8 t^5+18 t^6+38 t^7+73 t^8+157 t^9+289 t^{10}+622 t^{11}+1139 t^{12}+2437 t^{13} + \cdots \end{aligned}\tag{8}\]

Proof. Recall that \[P \in \mathcal{H} \Leftrightarrow P \text{ has at least two peaks and } P \in \{ uP'u: P' \in \mathcal{P}\} \cup \{ P'd: P' \in \mathcal{O}\} \cup \{P'ud: P' \in \mathcal{O}\}.\]

Clearly, the GF for the first set is \(t^2/(1-2t)\) (where \(t\) encodes the length of \(P\)). Moreover, according to our previous enumerations, and setting \(x=t^2\) in (2), since each letter of \(f(P)\) corresponds to two letters of \(P\), the GFs for the second and third set are \(tQ(t^2)\) and \(t^2 Q(t^2)\) respectively.

In order to enumerate \(\mathcal{H}\), it remains to subtract from the first set all paths of the form \(u^k\), \(k \geq 2\) (since \(uP'u\) has at least two peaks iff \(P'\) has at least one \(d\)), with GF \(t^2/(1-t)\), and from the second set all paths with exactly one peak, i.e., of the form \(u^kd^{\lambda} d\), where \(k, \lambda\) odd, with GF \(t^3/(1-t^2)^2\). For the third set, nothing is subtracted because \(P'\in \mathcal{O}\) starts with \(u\), has even \(|P'|\) and odd \(|P'|_u\), so it has at least one \(d\), so that \(P'ud\) has at least two peaks. It follows that the GF \(H(t)\) of \(\mathcal{H}\) is given by (8). \(\square\)

3. The bijection \(\theta\)

For any integers \(a,b\), with \(a \leq b\), we use the notation \([a,b] := \{z \in \mathbb{Z}: a \leq z \leq b\}\) for the interval of integers from \(a\) to \(b\). Recall that an order-consecutive partition sequence (OCPS) \(S\) of \([n]\) with \(m\) parts (also called blocks) is an ordered partition \(S = (S_1, S_2, \ldots, S_m)\) of \([n]\), such that, for all \(i \in [m]\), the set \(\bigcup_{j=1}^i S_j\) is an interval of integers. We denote by \(\mathcal{S}\) the set of all OCPS. Also recall that the canonical representation of \(S\) is the word \[\pi(S) = \pi_1 \pi_2 \cdots \pi_n, \text{ where } \pi_k = i \Leftrightarrow k \in S_i.\]

Example 3.1. The ten OCPS of \([3]\) are

Proposition 3.2. Let \(m, n \in \mathbb{N}^*\), with \(m \le n\), and let \(S=(S_1,\dots,S_m)\) be an \(m\)-part ordered partition of \([n]\) with canonical word \(\pi(S) = \pi_1 \pi_2 \cdots \pi_n\). Then \(S\) is an OCPS iff there exists a pair of sequences of non-negative integers \((\ell_i,r_i)_{i \in [m]}\), with \(\ell_1=0\), \(\sum\limits_{i=1}^m(\ell_i+r_i)=n\) and \(\ell_i+r_i>0\), for all \(i \in [m]\), such that \[\pi(S)= m^{\ell_m}(m-1)^{\ell_{m-1}}\cdots 2^{\ell_2}1^{r_1}2^{r_2}\cdots m^{r_m}.\]

Proof. Let \(T_i=\bigcup\limits_{j=1}^{i}S_j = \bigcup\limits_{j=1}^{i} \{k \in [n] : \pi_k = j \} = \{k \in [n]: \pi_k \leq i\}\). Then \(S\) is an OCPS iff each \(T_i\) is an interval, i.e., iff the letters of \(\pi(S)\) in \([i]\) form a factor in \(\pi(S)\). Moreover, since \(S_{i+1} = T_{i+1} \setminus T_i\), it follows that, for every \(i \in [m-1]\), all occurrences of \(i+1\) in \(\pi(S)\) appear as two factors attached to the left and/or right boundary of the existing word formed by the letters in \([i]\), whereas the factor of the letter \(1\) is \(1^{|S_1|}\), giving \[\pi(S) = m^{\ell_m}(m-1)^{\ell_{m-1}}\cdots 2^{\ell_2} 1^{\ell_1+ r_1}2^{r_2}\cdots m^{r_m},\] where \(\ell_1=0\) and \(r_1 = |S_1|\). Non-emptiness of each \(S_i\) gives \(\ell_i+r_i>0\), and all letters are accounted for, so \(\sum\limits_{i=1}^m(\ell_i+r_i)=n\).

Conversely, any word of this form has the property that for each \(i\), the positions of the letters in \([i]\) form an interval (the letters appear as a central block after removing higher labels), hence \(S\) is an OCPS. \(\square\)

According to Proposition 3.2, we can encode every OCPS \(S = (S_i)_{i \in [m]}\) by a pair of sequences of non-negative integers \((\ell, r) = (\ell_i, r_i)_{i \in [m]}\) such that \(\ell_1 = 0\), \(r_1 = |S_1|\) and \(\ell_i + r_i >0\), for all \(i \in [m]\). In the sequel, we identify the set \(\mathcal{S}\) with the set of these pairs of sequences.

Example 3.3.  

In order to define the mapping \(\theta: \mathcal{Q} \to \mathcal{S}\), we first observe, by combining Lemmas 2.1ii) and 2.2ii), that every word \(Q \in \mathcal{Q} \setminus \mathcal{Q}^{(0)}\) with \(\rho > 0\) occurrences of \(v\) is decomposed as \[Q = a_0 d^{k_0}W_0 vd^{\lambda_1} a_1 d^{k_1}W_1 \cdots vd^{\lambda_\rho} a_\rho d^{k_\rho}W_\rho, \tag{9}\] where \(a_j = \begin{cases} u, & \text{if } |W_j|_p \text{ is odd}, \\ p, & \text{if } |W_j|_p \text{ is even}, \end{cases}\, 0 \leq j \leq \rho,\) \(k_0, \ldots, k_\rho, \lambda_1, \ldots, \lambda_\rho \in \mathbb{N}\) and \(W_0, \ldots, W_{\rho} \in \mathcal{W}\). Moreover, if \(Q \in \mathcal{Q}^{(0)}\), i.e., \(\rho = 0\), then the decomposition of (9) still holds with \(Q = a_0 d^{k_0}W_0\).

Then, we define the mapping \(\theta\) as follows: Given \(Q \in \mathcal{Q}\), then, in order to obtain the OCPS \(\theta(Q)\), we change the first letter of \(Q\) into \(p\) and then we read the letters from left to right and we transform each occurrence of \(pd^k\), \(ud^k\) and \(vd^\lambda ad^k\), where \(a \in \{u, p\}\) and \(k, \lambda\geq 0\) are maximal, according to the rules \[pd^k \mapsto \begin{bmatrix} 0 \\ k + 1 \end{bmatrix}, \qquad ud^k \mapsto \begin{bmatrix} k + 1 \\ 0 \end{bmatrix},\qquad vd^\lambda a d^k \mapsto \begin{bmatrix} \lambda +1 \\ k + 1 \end{bmatrix}. \tag{10}\]

Proposition 3.4. The mapping \(\theta: \mathcal{Q} \to \mathcal{S}\) is a bijection.

Proof. Let \(Q \in \mathcal{Q}\), with \(|Q|_v = \rho \geq 0\), decomposed according to (9). Clearly, the words in \(\mathcal{W}\) are uniquely factored into factors of the forms \(pd^k\), \(ud^k\), where \(k \geq 0\), so that \(Q\) has a unique factorization into \(m\) factors \(p d^k\), \(u d^k\), \(v d^\lambda a_j d^k\), \(k, \lambda, j \ge 0\), where \(m = |Q|_u + |Q|_p\) (since every factor contains exactly one letter in \(\{u, p\}\)). Thus, \(\theta(Q)\) is a well-defined pair \((\ell_i, r_i)_{i \in [m]}\) and this pair is an OCPS, since changing the first letter of \(Q\) to \(p\) ensures that \(\ell_1 = 0\) and the rules of (10) ensure that \(\ell_i + r_i > 0\), for every \(i \in [m]\).

Conversely, given an OCPS \(S = (\ell_i, r_i)_{i \in [m]}\in \mathcal{S}\), having \(\rho \geq 0\) pairs \((\ell_i, r_i)\) with \(\ell_i,r_i>0\), we first apply the inverse of the rules of (10), obtaining a word \(W \in \{u,d,p,v,a\}^*\) starting with \(p\) (since \(\ell_1=0\)) and factored into \(\rho\) factors \(vd^{\lambda}ad^k\) and \(m-\rho\) factors \(pd^k\), \(ud^k\), \(\lambda, k \geq 0\), i.e., of the form \[W = a_0d^{k_0} W_0 vd^{\lambda_1}a_1d^{k_1} W_1 \cdots vd^{\lambda_\rho}a_\rho d^{k_\rho} W_{\rho},\] where \(a_0=p, a_1= \cdots = a_\rho = a \text{ and } W_0, \ldots, W_\rho \in \mathcal{W}.\)

(If \(\rho=0\), then \(W = a_0d^{k_0}W_0\).) Then, according to relation (9), by setting, for every \(j \in [0,\rho]\), \(a_j = u\), if \(|W_j|_p\) is odd, or \(a_j = p\), otherwise, we obtain from \(W\) a unique word \(Q \in \mathcal{Q}\). This word satisfies \(\theta(Q) = S\), since the factorizations of \(Q\) and \(W\) coincide after the substitution \((a_0, a_1, \ldots, a_\rho) = (p,a, \ldots,a)\), hence \(\theta\) is a bijection. \(\square\)

Example 3.5. Given \(Q = ppddpdvpdpudpuvdp\), according to the rules in (10), we obtain \(\theta(Q)\) as follows:

Conversely, given \((\ell,r) \in \mathcal{S}\), we obtain \(\theta^{-1}(\ell,r)\) as follows:

The following properties of \(\theta\) are easily derived from the proof of Proposition 3.4: Properties of \(\theta\): Let \(Q \in \mathcal{Q}\). Then,

• \(\theta(Q)\) is an OCPS of \([|Q|]\) (i.e., \(\theta\) is size preserving).

• \(\theta(Q)\) has \(|Q|_u + |Q|_p\) parts.

• \(\theta(Q)\) has \(|Q|_v\) parts of the form \((\ell_i,r_i)\) with \(\ell_i >0\) and \(r_i >0\).

• The restriction of \(\theta\) to \(\mathcal{Q}^{(0)}\) is a bijection on OCPS with each part \((\ell_i, r_i)\) having \(\ell_i=0\) or \(r_i=0\). This implies that the OCPS of \([n]\) with parts consisting only of consecutive elements is equal to \(3^{n-1}\).

4. The bijection \(\phi\)

We denote by \(\mathcal{C}\) the set of generalized compositions (GC), i.e., compositions where each part of size \(s\) is colored with one out of \(s+1\) colors. More formally, the empty GC (of \(n=0\)) is denoted by \(\emptyset\), whereas a non-empty GC of \(n \in \mathbb{N}^*\) with \(m\) parts is a pair \((C, r)\) where \(C = (C_1, C_2, \ldots, C_m)\) is an \(m\)-part composition of \(n\) and \(r = (r_1, r_2, \ldots, r_m)\) is the sequence of colors of the parts of \(C\), i.e., \[C_1 + C_2 + \cdots + C_m = n, \qquad C_1, C_2, \ldots, C_m \in \mathbb{N}^* \text{ and } 0 \leq r_i \leq C_i, \text{ for } i \in [m].\]

We encode each GC \((C, r)\) by the pair of sequences of non-negative integers \((\ell, r) = (\ell_i, r_i)_{i \in [m]}\) where \(\ell_i = C_i – r_i\), for all \(i \in [m]\). Clearly, this representation uniquely defines a GC and moreover these pairs of sequences of non-negative integers are subject only to the restriction that \(\ell_i+r_i>0\) for every \(i \in [m]\) (since every part is positive). Therefore, we identify the set \(\mathcal{C}\) with the set of these pairs of sequences.

Example 4.1. The seven GCs of \(n=2\) are listed below: \[\begin{bmatrix} 2 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 0 \\ 2 \end{bmatrix}, \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}, \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}, \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}.\]

In order to define the mapping \(\phi: \mathcal{R} \to \mathcal{C}\), we first observe, by refining (7), that every word \(R \in \mathcal{R} \setminus \mathcal{R}^{(0)}\) with \(\rho\) occurrences of \(v\) is decomposed as \[R = Q_1 vd^{\lambda_1} \cdots Q_{\rho} vd^{\lambda_\rho} R_0, \tag{11}\]where \(Q_1, Q_2, \ldots, Q_\rho \in \mathcal{Q}^{(0)}, R_0 \in \mathcal{R}^{(0)}, \quad \lambda_1, \ldots, \lambda_\rho \in \mathbb{N}.\)

Moreover, we use the following Lemma:

Lemma 4.2. \(R \in \mathcal{R}^{(0)}\) iff \(R = Wb\), where \(W \in \mathcal{W}\), \(b = \begin{cases} d, & |W|_p \text{ is odd}, \\ p, & |W|_p \text{ is even}. \end{cases}\)

Proof. Let \(R \in \mathcal{W} \supset \mathcal{R}^{(0)}\) and assume that \(R\) is non-empty, so that \(R = Wb\), for some \(W \in \mathcal{W}\) and \(b \in \{u,d,p\}\). Then, \(R \in \mathcal{R}^{(0)}\) iff \(|R|_p\) is odd and \(R\) ends with \(d\) or \(p\), so that \(b\) is completely determined by the parity of \(|W|_p\). \(\square\)

Thus, using Lemmas 2.1iii) and 4.2, the decomposition of (11) is further refined as \[R = W_1 a_1 d^{k_1}vd^{\lambda_1} \cdots W_\rho a_\rho d^{k_\rho} vd^{\lambda_\rho} W_0 a_0, \tag{12}\]where \(a_j = \begin{cases} u, & \text{if } |W_j|_p \text{ is odd and } j>0, \\ d, & \text{if } |W_j|_p \text{ is odd and } j=0, \\ p, & \text{if } |W_j|_p \text{ is even}, \end{cases} \qquad 0 \leq j \leq \rho\) and \(W_0, \ldots, W_{\rho} \in \mathcal{W}\), \(k_1, \ldots, k_\rho \in \mathbb{N}\). Moreover, if \(R \in \mathcal{R}^{(0)}\), i.e., \(\rho = 0\), then the decomposition of (12) still holds with \(R = W_0a_0\).

Then, we define the mapping \(\phi\) as follows: Given \(R \in \mathcal{R}\), in order to obtain the GC \(\phi(R)\), we read the letters of \(R\) from right to left, ignoring the last letter, and we transform each occurrence of \(ud^k\), \(pd^k\) and \(ad^k vd^\lambda\), where \(a \in \{u, p\}\) and \(k, \lambda \geq 0\) are maximal, according to the rules \[pd^k \mapsto \begin{bmatrix} 0 \\ k + 1 \end{bmatrix}, \qquad ud^k \mapsto \begin{bmatrix} k + 1 \\ 0 \end{bmatrix},\qquad a d^k vd^\lambda \mapsto \begin{bmatrix} k +1 \\ \lambda + 1 \end{bmatrix}, \tag{13}\] obtaining the pairs of \(\phi(R)\) in right to left order. Note that the last letter of \(R\) can be ignored because it is uniquely determined by the remaining letters; if they contain an even number of \(p\)’s and \(v\)’s, then this letter is \(p\), otherwise it is \(d\). Also note that if \(|R|=n\), then \(\phi(R)\) is a GC of \(n-1\) and in particular, the path \(R=p\) is mapped to the empty GC.

Proposition 4.3. The mapping \(\phi: \mathcal{R} \to \mathcal{C}\) is a bijection.

Proof. Let \(R \in \mathcal{R}\), with \(|R|_v = \rho \geq 0\) and \(|R|>1\) (if \(|R|=1\), then \(R=p\) and \(\phi(R) = \emptyset\)), decomposed according to (12). It follows that the word \(R'\) obtained by deleting the last letter of \(R\) is decomposed as \[R' = W_1 a_1 d^{k_1} vd^{\lambda_1} \cdots W_{\rho} a_\rho d^{k_\rho} vd^{\lambda_\rho} W_{0}, \tag{14}\] where \(W_0, \ldots, W_{\rho} \in \mathcal{W}\), and hence \(R'\) has a unique factorization into \(m\) factors \(p d^k\), \(u d^k\), \(a_j d^k v d^\lambda\), \(k, \lambda, j \ge 0\), where \(m = |R'|_u + |R'|_p\) (since every factor contains exactly one letter in \(\{u, p\}\)). Thus, \(\phi(R)\) is a well-defined pair \((\ell_i, r_i)_{i \in [m]}\) and this pair is a GC, since the rules of (13) ensure that \(\ell_i + r_i > 0\), for every \(i \in [m]\).

Conversely, given a GC \((\ell, r) = (\ell_i, r_i)_{i \in [m]}\in \mathcal{C}\), having \(\rho \geq 0\) pairs \((\ell_i, r_i)\) with \(\ell_i, r_i>0\) (if the GC is empty, then \(\phi^{-1}(\emptyset) = p\)), we first apply the inverse of the rules of (13), obtaining a word \(W \in \{u,d,p,v,a\}^*\) factored into \(\rho\) factors \(ad^k vd^{\lambda}\) and \(m-\rho\) factors \(pd^k\), \(ud^k\), \(\lambda, k \geq 0\), i.e., of the form \[W = W_1 a_1d^{k_1}vd^{\lambda_1} \cdots W_{\rho} a_{\rho}d^{k_\rho} vd^{\lambda_\rho}W_{0}, \text{ where } a_1= \cdots = a_\rho = a \text{ and } W_0, \ldots, W_{\rho} \in \mathcal{W}.\]

(If \(\rho=0\), then \(W = W_{0}\).) Then, according to relation (14), by setting, for every \(j \in [\rho]\), \(a_j = u\), if \(|W_j|_p\) is odd, or \(a_j = p\), otherwise, we obtain from \(W\) a unique word \(R'\) decomposed as in (14). Finally, setting \(R = R'a_{0}\), where \(a_{0} = d\), if \(|W_{0}|_p\) is odd, or \(a_{0} = p\), otherwise, we obtain a word \(R \in \mathcal{R}\) which satisfies \(\phi(R) = (\ell,r)\), since the factorizations of \(R'\) and \(W\) coincide after the substitution \((a_1, \ldots, a_\rho) = (a, \ldots,a)\), hence \(\phi\) is a bijection. \(\square\)

Example 4.4. Given \[\begin{aligned} R &= ppddpdvpdpudpuvdp \\& =pd^0 \ pd^2 \ pd vd^0 \ pd \ pd^0\ ud\ pd^0\ ud^0 vd \ p, \end{aligned}\] we ignore the last letter and, according to the above rules, we obtain \[\phi(R)= \begin{bmatrix} 0 & 0 & 2 & 0 & 0 & 2 & 0 & 1 \\ 1 & 3 & 1 & 2 & 1 & 0 & 1 & 2 \end{bmatrix},\] in contrast to \[\theta(R)= \begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 2 & 0 & 1 & 2 \\ 1 & 3 & 2 & 2 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}.\]

Conversely, given \((\ell,r) \in \mathcal{C}\), we obtain \(\phi^{-1}(\ell,r)\) as follows:

The following properties of \(\phi\) are easily derived from the proof of Proposition 4.3: Properties of \(\phi\): Let \(R \in \mathcal{R}\). Then,

• \(\phi(R)\) is a GC of \(|R|-1\).

• \(\phi(R)\) has \(|R|_u + |R|_p – [R \text{ ends with } p]\) parts (where \([\ ]\) is the Iverson bracket).

• \(\phi(R)\) has \(|R|_v\) parts of the form \((\ell_i,r_i)\) with \(\ell_i >0\) and \(r_i >0\).

• The restriction of \(\phi\) to \(\mathcal{R}^{(0)}\) is a bijection on GC with each part \((\ell_i, r_i)\) having \(\ell_i=C_i-r_i=0\) or \(r_i=0\). This implies that the number of GCs of \(n\) with parts using only two colors is equal to \(2\cdot 3^{n-1}\).

5. Enumeration with respect to critical valleys

In this section, we enumerate binary paths with respect to their length and the number of critical valleys. For every \(n,k \geq 0\), let \(a_{n,k}\) denote the number of binary paths of length \(n\) having exactly \(k\) critical valleys.

As before, we transform every path \(P\) of even length into a word \(f(P) \in \{u,d,p,v\}^*\) by reading the steps of \(P\) in pairs from left to right and applying the rules \[uu \mapsto u, \qquad dd \mapsto d, \qquad ud \mapsto p, \qquad du \mapsto v.\]

Recall that the letters \(p\) and \(v\) correspond to odd peaks and odd valleys, respectively, and that a letter \(v\) corresponds to a critical valley iff the number of preceding letters in \(\{p,v\}\) is even. Thus, when one reads only the letters \(p\) and \(v\) of \(f(P)\), the critical valleys are precisely the occurrences of \(v\) in odd positions of the resulting subword.

Proposition 5.1. Let \(k,n \in \mathbb{N}\). The number \(a_{n,k}\) of binary paths of length \(n\) having exactly \(k\) critical valleys is given by \[a_{n,k}= \sum\limits_{j=k}^{\lfloor \frac{m+1}{2} \rfloor} \binom{m+1}{2j}\binom{j}{k}2^{m-j}, \qquad n = 2m. \tag{15}\] \[a_{n,k}= \sum\limits_{j=k}^{\lfloor \frac{m+2}{2} \rfloor} \binom{m+1}{2j-1}\binom{j}{k}2^{m-j+1}, \qquad n = 2m+1. \tag{16}\]

Proof. Let \(P\) be a binary path of length \(2m\), and let \(W=f(P)\). Suppose that \(W\) contains exactly \(r\) letters in \(\{p,v\}\). Then one first chooses their positions in \(\binom{m}{r}\) ways, while each one of the remaining \(m-r\) positions may be filled independently by either \(u\) or \(d\), giving \(2^{m-r}\) possibilities.

Now write \(r=2j\) or \(r=2j-1\). In both cases, the subword of \(W\) formed by the letters in \(\{p,v\}\) has exactly \(j\) odd positions. These are precisely the positions in which a letter \(v\) corresponds to a critical valley. Hence, once the positions of the letters in \(\{p,v\}\) are fixed, the number of ways to obtain exactly \(k\) critical valleys is \[\binom{j}{k} 2^{\lfloor r/2 \rfloor},\] since one chooses which \(k\) of the \(j\) odd positions contain the letter \(v\), while each even position may be filled independently by either \(p\) or \(v\).

Therefore, \[a_{2m,k} = \sum\limits_{r=0}^{m} \binom{m}{r} 2^{m-r+\lfloor r/2 \rfloor} \binom{\lceil r/2 \rceil}{k}.\]

Separating the cases \(r=2j\) and \(r=2j-1\), we obtain \[a_{2m,k} = \sum\limits_{j=k}^{m} \left( \binom{m}{2j}+\binom{m}{2j-1} \right) \binom{j}{k}2^{m-j}.\]

Using Pascal’s identity, we get (15).

Now let \(P\) be a binary path of length \(2m+1\). Its first \(2m\) steps are encoded by a word \(W=f(P')\) of length \(m\), while its last step is either \(u\) or \(d\). Suppose that \(W\) contains exactly \(r\) letters in \(\{p,v\}\).

If \(r=2j-1\) is odd, then the number of upsteps in the first \(2m\) steps is odd, so the last step cannot be a critical valley. Hence both choices for the last step contribute equally, and the number of paths with exactly \(k\) critical valleys is \[2\binom{m}{2j-1}2^{m-(2j-1)}\binom{j}{k}2^{j-1} = \binom{m}{2j-1}2^{m-j+1}\binom{j}{k}.\]

If \(r=2j\) is even, then the last step contributes one additional critical valley precisely when it is equal to \(d\). Thus the corresponding contribution is \[\binom{m}{2j}2^{m-2j} \left( \binom{j}{k}+\binom{j}{k-1} \right)2^j = \binom{m}{2j}2^{m-j}\binom{j+1}{k}.\]

Replacing \(j\) by \(j-1\) in the latter sum and combining the two cases, we obtain \[a_{2m+1,k} = \sum\limits_{j=k}^{m+1} \left( \binom{m}{2j-1}+\binom{m}{2j-2} \right) \binom{j}{k}2^{m-j+1}.\]

Again, Pascal’s identity yields (16). \(\square\)

The first values of \(a_{n,k}\) are listed in Table 1. Note that sequence \(a_{2m+1,0}\) appears as sequence \(A007070(m)\) in the OEIS [7], counting the number of generalized compositions of \(m+1\) when there are \(2^i-1\) different types of the part \(i\), \(i \ge 1\).

\(n \\backslash k\)	0	1	2	3
0	1
1	1	1
2	3	1
3	4	4
4	10	6
5	14	16	2
6	34	28	2
7	48	64	16
8	116	120	20
9	164	252	92	4
10	396	492	132	4

Remark 5.2. From Table 1, we observe that, for the first values of \(n=2m\), the numbers \(a_{2m,0}\) and \([x^{m+1}]Q(x)\) coincide.

Indeed, the following result holds:

Proposition 5.3. The number \(a_{2m,0}\) of binary paths of even length \(2m\) having no critical valleys is equal to the number \([x^{m+1}]Q(x)\) of paths in \(\mathcal{O}\) of length \(2m+2\).

Proof. Let \(P\) be a binary path of length \(2m\) with \(r \geq 0\) odd valleys and no critical valleys, and let \(W=f(P)\), so that \(|W|_v = r\) and \(|W| = m\). Since \(P\) has no critical valleys, according to Lemma 2.2i), \(W\) is decomposed as \[W=d^{\lambda_0}X_0\,v d^{\lambda_1}X_1 \cdots v d^{\lambda_{r-1}}X_{r-1} v d^{\lambda_r}X_r,\] where \(\lambda_0,\ldots,\lambda_r\in\mathbb{N}\), \(X_0,X_1,\ldots,X_{r-1} \in \mathcal{Q}^{(0)}\) and \(X_r \in \mathcal{W}\) (if \(r=0\), then \(W = d^{\lambda_0}X_r\), \(X_r \in \mathcal{W}\)).

Now, we set \[W' = ad^{\lambda_0}X_r\,v d^{\lambda_1}X_1\cdots v d^{\lambda_{r-1}}X_{r-1} v d^{\lambda_r} X_0, \qquad \text{where } a= \begin{cases} p, & \text{if } |X_r|_p \text{ is even},\\ u, & \text{if } |X_r|_p \text{ is odd}, \end{cases} \tag{17}\] (if \(r=0\), then \(W' = ad^{\lambda_0}X_r\)). The resulting word \(W'\) has length \(m+1\) and since, by Lemma 2.1ii), its component \(ad^{\lambda_0}X_r\) belongs to \(\mathcal{Q}^{(0)}\), we have that \(W'\) follows the decomposition of Lemma 2.2ii), thus \(W' \in \mathcal{Q}\) and therefore corresponds to a unique path in \(\mathcal{O}\) of length \(2m+2\).

This construction is clearly reversible: given a word in \(W' \in \mathcal{Q}\), then it is decomposed according to Lemma 2.2ii) as in (17). We remove its first letter and then undo the swap of parts \(X_r, X_0\) (if \(|W'|_v=0\), then \(W' = ad^{\lambda_0}X_r\) and no swap is necessary) to obtain \(W\) and finally \(P = f^{-1}(W)\). Therefore, the two sets are equinumerous. \(\square\)