A bijective proof of an enumerative property of legal bracketings
A legal bracketing (or balanced parenthesis system or Dyck word) of length \(n\) is a word \(L\) on the alphabet \(\{a,b\}\) with \(n\) \(a\)'s and \(n\) \(b\)'s any prefix of which contains at least as many \(a\)'s as \(b\)'s. A jump (resp. landing) is a maximal subword of \(a\)'s (resp. \(b\)'s), a sequence is either a jump or a landing, and a long nonfinal sequence (LNFS) is a sequence of at least two letters which is not the last sequence of \(L\). It was shown in [\textit{G. Kreweras} and \textit{P. Moszkowski}, A new enumerative property of Narayana numbers, J. Stat. Plann. Inference 14, 63-67 (1986; Zbl 0602.05005)] that the Narayana numbers \(U(n,k)= (1/n) {n\choose k} {n\choose k+1}\) count the legal bracketings of length \(n\) with \(k\) LNFSs. In the present paper, a bijection is presented between these objects and legal bracketings of length \(n\) with \(k+1\) peaks (occurences of \(ab)\) or, equivalently, with \(k\) troughs (occurrences of \(ba)\). The authors claim that this result constitutes a bijective proof of the result in [Kreweras and Moszkowski, op. cit.]. This claim would follow from the hypothesis that there are \(U(n,k)\) legal bracketings of length \(n\) with \(k+1\) peaks, but this reviewer found in the article neither a proof of this hypothesis nor a reference to such a proof.
scientific article; zbMATH DE number 1109974