An explanatory bijection of some remarkable properties of bridges
A bridge is a balanced parenthesis system, or Dyck word---that is, a word on the alphabet \(\{0,1\}\) with \(n\) occurrences each of 1 and 0 such that in any prefix there are at least as many occurrences of 1 as of 0. The range of a bridge \(P\) is \(n\), the number of occurrences of 1 in \(P\). The geometric representation of a bridge is obtained from the standard Dyck path by a 45-degree counter-clockwise rotation: starting at the origin (0,0), the path goes north by one unit for each 1 in the bridge and east by one unit for each 0, ending at \((n,n)\) and never going below the diagonal \(x=y\). An arch is a part (interval) of the bridge between two successive points on the diagonal. A plateau is a maximal (by inclusion) interval of zeros. The height of a bridge \(P\) is the maximum value of \(y-x\) for any point \((x,y)\) on the geometric representation of \(P\). The degree of a bridge \(P\) is the number of arches in the support of \(P\), described geometrically by extending all the plateaus to the diagonal and then going north until \(P\) is reached.NEWLINENEWLINENEWLINEThe following results about bridges of range \(n\) are found in \textit{G. Kreweras} [Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Cahier no. 15, Paris, 1970, pp. 3-41]. (1) The bridges with \(\alpha\) arches are equinumerous with those beginning with \(\alpha\) ones. (2) The bridges with \(\beta\) plateaus are equinumerous with those with \(n-\beta+1\) plateaus. (3) The bridges of degree \(\gamma\) are equinumerous with those of height \(\gamma\). The results are proved there by finding the number of bridges with each of the above properties. NEWLINENEWLINENEWLINEIn the article under review, a bijection \(w\) on the set of bridges of range \(n\) is found such that \((1')\) if \(P\) begins with \(\alpha\) ones, then \(w(P)\) has \(\alpha\) arches; \((2')\) if \(P\) has \(\beta\) plateaus, then \(w(P)\) has \(n- \beta+1\) plateaus; \((3')\) if \(P\) is of degree \(\gamma\), then \(w(P)\) is of height \(\gamma\).
- An involution on Dyck paths and its consequences
- Dyck path enumeration
- A bijective proof of an enumerative property of legal bracketings
- The Catalan matroid
- Ideals of quasi-symmetric functions and super-covariant polynomials for \(\mathcal S_n\)
- scientific article; zbMATH DE number 3989356 (Why is no real title available?)
- Sweep maps: a continuous family of sorting algorithms
- An explanatory bijection of some properties of bridges
This page was built for publication: An explanatory bijection of some remarkable properties of bridges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961467)
