×

zbMATH — the first resource for mathematics

A bijection between bargraphs and Dyck paths. (English) Zbl 1401.05146
Summary: Bargraphs are a special class of column-convex polyominoes. They can be identified with lattice paths with unit steps north, east, and south that start at the origin, end on the \(x\)-axis, and stay strictly above the \(x\)-axis everywhere except at the endpoints. Bargraphs, which are used to represent histograms and to model polymers in statistical physics, have been enumerated in the literature by semiperimeter and by several other statistics, using different methods such as the wasp-waist decomposition of Feretić, and a bijection with certain Motzkin paths.
In this paper we describe an unusual bijection between bargraphs and Dyck paths, and study how some statistics are mapped by the bijection. As a consequence, we obtain a new interpretation of Catalan numbers, as counting bargraphs where the semiperimeter minus the number of peaks is fixed.

MSC:
05C30 Enumeration in graph theory
05B50 Polyominoes
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] A. Blecher, C. Brennan, A. Knopfmacher, Walls in bargraphs, preprint.
[2] Blecher, A.; Brennan, C.; Knopfmacher, A., Levels in bargraphs, Ars Math. Contemp., 9, 287-300, (2015) · Zbl 1329.05013
[3] Blecher, A.; Brennan, C.; Knopfmacher, A., Combinatorial parameters in bargraphs, Quaest. Math., 39, 619-635, (2016)
[4] Blecher, A.; Brennan, C.; Knopfmacher, A., Peaks in bargraphs, Trans. R. Soc. South Africa, 71, 97-103, (2016)
[5] Blecher, A.; Brennan, C.; Knopfmacher, A.; Prodinger, H., The height and width of bargraphs, Discrete Appl. Math., 180, 36-44, (2015) · Zbl 1303.05045
[6] Bousquet-Mélou, M.; Rechnitzer, A., The site-perimeter of bargraphs, Adv. Appl. Math., 31, 86-112, (2003) · Zbl 1020.05007
[7] Deutsch, E.; Elizalde, S., Statistics on bargraphs viewed as cornerless Motzkin paths, Discrete Appl. Math., 221, 54-66, (2017) · Zbl 1357.05067
[8] Feretić, S., The column-convex polyominoes perimeter generating function for everybody, Croat. Chem. Acta, 69, 741-756, (1996)
[9] Feretić, S., A perimeter enumeration of column-convex polyominoes, Discrete Math. Theor. Comput. Sci., 9, 57-84, (2007) · Zbl 1153.05306
[10] Prellberg, T.; Brak, R., Critical exponents from nonlinear functional equations for partially directed cluster models, J. Stat. Phys., 78, 701-730, (1995) · Zbl 1102.82316
[11] Stanley, R. P., Catalan Numbers, (2015), Cambridge University Press: Cambridge University Press New York, viii+215 pp · Zbl 1317.05010
[12] The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.