A bijective proof of an enumerative property of legal bracketings
type: Item
instance of: scholarly article
title: A bijective proof of an enumerative property of legal bracketings
zbMATH Open document ID: 0891.05004
DOI: 10.1016/S0012-365X(96)00020-9
author: S. Benchekroun
author: Paul Moszkowski
published in: Discrete Mathematics
publication date: 1998-07-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 1109974
zbMATH Keywords: legal bracketing
zbMATH Keywords: balanced parenthesis system
zbMATH Keywords: Dyck word
zbMATH Keywords: Narayana numbers
Wikidata QID: Q114122935
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Q3752390
cites work: A new enumerative property of the Narayana numbers
cites work: Subdivision des nombres de Narayana suivant deux paramètres supplémentaires. (Subdivision of Narayana numbers following two supplementary parameters)
cites work: Q5847555
cites work: Six etudes in generating functions
Recommended article: A new enumerative property of the Narayana numbers
Recommended article: A bijection on Dyck paths and its consequences
Recommended article: Q4598978
Recommended article: A bijection on bilateral Dyck paths
Recommended article: An extension of the Catalan problem
Recommended article: Arbres et suites majeures. (Trees and major sequences)
Recommended article: An explanatory bijection of some remarkable properties of bridges
Recommended article: The Bricklayer Problem and the Strong Cycle Lemma
Recommended article: A symmetric variation of a distribution of Kreweras and Poupard
Recommended article: A new bijection between ordered trees and legal bracketings
description: scientific article; zbMATH DE number 1109974