Nondecreasing Dyck paths and \(q\)-Fibonacci numbers (Q1363665)

To formulate the results of this interesting paper recall some terminology and fix the notation. For any word in the free monoid \(X^*\) of words over the alphabet \(X= \{x,\overline x\}\) denote by \(|w|_a\) the number of occurrences of the letter \(a\in X\) in \(w\); the length of \(w\) is given by \(|w|= \sum_{a\in X}|w|_a\). The set of words \(w\in X^*\) characterized by the conditions \((*)\) \(|u|_x\geq |u|_{\overline x}\) for any prefix \(u\) of \(w\) and \((**)\) \(|w|_x= |w|_{\overline x}\), is called the set of Dyck words; denote it \(W_{\mathcal D}\) and observe that \(|\{w\mid w\in W_{\mathcal D}\) and \(|w|= 2n\}|= {1\over n+1}{2n\choose n}\)---the \(n\)th Catalan number. For a Dyck word \(w\) any of its two-letter subsequences of the type \(x\overline x\) is called a peak of \(w\). Any subsequence \(\overline xx\) is named valley, and any \(x^h\overline x^h\) is called a pyramid of \(w\) of height \(h\). By a path is meant a sequence of points \(s_k= (i_k,j_k)\), \(k=0,1,\dots,2n\), with \(s_k\in \mathbb{N}^2\). A step is a pair of two consecutive points in the path. \(j_k\) is called the altitude of \(s_k\). Dyck words are used to codify Dyck paths, i.e. sequences \(s=(s_0, s_1,\dots, s_{2n})\) of points in \(\mathbb{N}^2\) with the steps \((s_i, s_{i+1})\), where \(s_i= (x_i,y_i)\) and \(s_{i+1}= (x_i+ 1,y_i+1)\) or \(s_{i+1}= (x_i+ 1,y_i-1)\). Denote by \(P_{\mathcal D}\) the set of Dyck paths and by \(P^*_{\mathcal D}\) the subset of nonincreasing Dyck paths, i.e. of paths \(s\) such that \(\text{alt}(s_{i_1})\leq\cdots\leq\text{alt}(s_{i_t})\) for all valley points \(s_{i_1},\dots, s_{i_t}\) of \(s\). Further, for a set \(S= \{S_n\mid n\in\mathbb{N}\}\) graded by a function \(p:S\to\mathbb{N}\), the authors consider an operator \(\theta: S_n\to P(S_{n+1})\) satisfying the following two conditions: (1) \((\forall y\in S_{n+1})(\exists x\in S_n)(y\in\theta(x))\) and (2) (\(x_1\neq x_2\) in \(S_n)\) implies \(\theta(x_1)\cap \theta(x_2)=\varnothing\). It is observed that when taking any word \(w\in W^*_{\mathcal D}\), with \(w= w'w_p'w''_p w''\) being its factorization with \(w_p'w''_p\) the last pyramid of \(w\), then the operator \(\theta^*: W^*_{\mathcal D}\to 2^{W^*_{\mathcal D}}\) defined by \[ \theta^*(w)= \{u\in W^*_{\mathcal D}\mid u= w'w_p' z'x\overline xz'' w'',\;w''_p= z'z''\in \{\overline x\}^+,\;z''\in\{\overline x\}^*\} \] satisfies (1) and (2). This allows the authors to construct each path \(s\in P^*_{\mathcal D}\) starting with some other path \(s'\in P^*_{\mathcal D}\) uniquely defined for path \(s\). So, a recursive description for the paths in \(P^*_{\mathcal D}\) is obtained. Using this description, the generating function \(F(x,y,z)\) for nondecrasing Dyck paths is found, defined as a series \(\sum_{s\in P^*_{\mathcal D}}x^{l(s)}y^{p(s)}z^{f(s)}\) with \(l(s)\) and \(p(s)\) being the numbers of rises and peaks for \(s\), correspondingly, and \(f(s)\) being the number of positions in the `\(s\)-fringe'. Also the functional equation for \(F(x,y,z)\) is found (Theorems 2.4 and 2.5). Thereafter, the area \(a(s)\) of a nondecreasing Dyck path \(s\) is involved, being defined as the sum of altitudes of the points of \(s\). The corresponding generating function \(F(x,y,q)= \sum_{s\in P^*_{\mathcal D}}x^{l(s)}y^{p(s)}q^{a(s)}\) is given in terms of the so-called pyramid paths' generating function. It is proved also (Theorem 3.3) that \(F(x,1,q)= \sum_{n\geq 0}F_n(q)x^n\), where \(F_n(q)\) is the \(q\)-Fibonacci number defined by \[ F_0(q)= 0,\;F_1(q)= q\quad\text{and}\quad F_{n+2}(q)= F_{n+1}(q) q^{2n+3}+ \sum^n_{k=0} q^{(k+1)^2}F_{n- k+ 1}(q). \]