Columns of fixed height in bargraphs

Document Type : Research Paper


The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, Private Bag 3, Wits 2050,Johannesburg, South Africa


We obtain the generating function for the number of columns of fixed height $r$ in a bargraph (classified according to semi-perimeter). As initial case for two distinct methods we first find the generating function for columns of height $1$. Then using a first-return-to-level-$1$ decomposition, we obtain the rational function version of the continued fraction generating function which allows us to derive separate recursions for its numerator and denominator. This then allows us to get the asymptotic average number of columns for each $r$. We also obtain an equivalent generating function by exploiting a sequential decomposition for bargraphs in terms of columns of height $r$.


Main Subjects

[1] A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Appl.
Math., 180(2015) 36–44.
[2] A. Blecher, C. Brennan and A. Knopfmacher, Levels in bargraphs, Ars Math. Contemp., 9 (2015) 297–310.
[3] A. Blecher, C. Brennan and A. Knopfmacher, Peaks in bargraphs, Transactions of the Royal Society of South Africa,
71 (2016) 97–103.
[4] A. Blecher, C. Brennan and A. Knopfmacher, Combinatorial parameters in bargraphs, Quaest. Math., 39 (2016)
[5] A. Blecher, C. Brennan, A. Knopfmacher, T. Mansour and M. Shattuck, Counting permutations by the number of
vertical edges in their bargraphs, J. Autom. Lang. Comb., 25 (2020) 279–290.
[6] M. Bousquet-Mélou and A. Rechnitzer, The site perimeter of bargraphs, Adv. in Appl. Math., 31 (2003) 86–112.
[7] M. Bousquet-Mélou and R. Brak, Exactly solved models of polyominoes and polygons, Chapter 3 of Polygons, Poly-ominoes and Polycubes, Lecture notes in physics, 775, Springer, Berlin, Heidelberg 2009, 43-78.
[8] D. Callan, T. Mansour and J. L. Ramirez, Statistics on bargraphs of Catalan words, J. Autom. Lang. Comb., 26
(2021) 177–196.
[9] E. Deutsch and S. Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, Discrete Appl. Math. 221
(2017) 54–66.
[10] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
[11] A. Geraschenko, An investigation of skyline polyominoes.
[12] E. J. Janse van Rensburg and A. Rechnitzer, Exchange symmetries in Motzkin path and bargraph models of
copolymer adsorption, Electron. J. Comb., 9 (2002).
[13] T. Mansour and A. Sh. Shabani, Enumerations on Bargraphs, Discrete Math. Lett., 2 (2019) 65–94.
[14] T. Mansour, Border and tangent cells in bargraphs, Discrete Math. Lett., 1 (2019) 26–29.
[15] T. Mansour, A. Sh. Shabani and M. Shattuck, Counting corners in compositions and set partitions presented as
bargraphs, J. Difference Equ. Appl., textbf24 (2018) 992–1015.
[16] T. Mansour and M. Shattuck, Counting water cells in bargraphs of compositions and set partitions, Applicable
Analysis and Discrete Mathematics 12 (2018) 413–438.
[17] T. Mansour and M. Shattuck, Statistics on bargraphs of inversion sequences of permutations, Discrete Math. Lett., 4 (2020) 42–49.
[18] A. Owczarek and T. Prellberg, Exact solution of the discrete (1 + 1)-dimensional SOS model with field and surface interactions, J. Statist. Phys., 70 (1993) 1175–1194.
[19] T. Prellberg and R. Brak, Critical exponents from nonlinear functional equations for partially directed cluster
models, J. Stat. Phys., 78 (1995) 701–730.
  • Receive Date: 24 January 2022
  • Revise Date: 20 December 2022
  • Accept Date: 03 January 2023
  • Published Online: 01 March 2024