Interior vertices and edges in bargraphs

Toufik Mansour and Armend Sh. Shabani
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 25, 2019, Number 2, Pages 181-189
DOI: 10.7546/nntdm.2019.25.2.181-189
Full paper (PDF, 198 Kb)

Details

Authors and affiliations

Toufik Mansour
Department of Mathematics, University of Haifa
3498838 Haifa, Israel

Armend Sh. Shabani
Department of Mathematics, University of Prishtina
10000 Prishtine, Republic of Kosovo

Abstract

In this paper, we consider two statistics on bargraphs, which are defined to be lattice paths in the first quadrant, starting at the origin and ending upon first return to the x-axis. Each bargraph is represented as a sequence of columns π₁π₂…π_m such that column k contains π_k cells. First we enumerate interior vertices, where naturally, interior vertex is a vertex that belongs to exactly four cells of bargraphs. Then we enumerate d-edges – edges that contain d interior vertices. More precisely, we find the generating function for the number of bargraphs with n cells and m columns according: to interior vertices and according to horizontal (vertical) d-edges. In addition we consider several special cases in detail, where we obtain asymptotic results for total number of statistics under consideration.

Keywords

• Bargraphs
• Generating functions
• Interior vertices
• Interior edges

2010 Mathematics Subject Classification

• 05A18

References

1. Owczarek, A. & Prellberg, T. (1993). Exact solution of the discrete (1 + 1)-dimensional SOS model with field and surface interactions, J. Stat. Phys., 70 (5/6), 1175–1194.
2. Duchon, P. (1999). q-Grammars and wall polyominoes, Ann. Comb., 3, 311–321.
3. Geraschenko, A., An investigation of skyline polynomials, Available online: http://people.brandeis.edu/%7egessel/47a/geraschenko.pdf.
4. Prellberg, T. & Brak, R. (1995). Critical exponents from nonlinear functional equations for partially directed cluster models, J. Stat. Phys., 78, 701–730.
5. Feretic, S. (2007). A perimeter enumeration of column-convex polyominoes, Discrete Math. Theor. Comput. Sci., 9, 57–84.
6. Blecher, A., Brennan, C., & Knopfmacher, A. (2015). Levels in bargraphs, Ars Math. Contemp., 9, 297–310.
7. Blecher, A., Brennan, C., & Knopfmacher, A. (2016). Peaks in bargraphs, Trans. Royal Soc. S. Afr., 71, 97–103.
8. Blecher, A., Brennan, C., & Knopfmacher, A. (2016). Combinatorial parameters in bargraphs, Quaest. Math., 39, 619–635.
9. Blecher, A., Brennan, C., & Knopfmacher, A. (2017). Walls in bargraphs, Online J. Anal. Combin., 12, 12, 1–11.
10. Deutsch, E. & Elizalde, S. (2017). Statistics on bargraphs viewed as cornerless Motzkin paths, Discrete Appl. Math., 221, 54–66.
11. Heubach, S. & Mansour, T. (2009). Combinatorics of Compositions and Words, Chapman & Hall/CRC, Boca Raton.
12. Blecher, A., Brennan, C., Knopfmacher, A., & Mansour, T. (2016). Counting corners in partitions, Ramanujan J., 39 (1), 201–224.
13. Mansour, T. & Shattuck, M. (2017). Bargraph statistics on words and set partitions, J. Diff. Eq. Appl,, 23 (6), 1025–1046.
14. Mansour, T., Shabani, A. Sh., & Shattuck, M. (2018). Counting corners in compositions and set partitions presented as bargraphs, J. Diff. Eq. Appl., 24 (6), 849–1022.
15. Mansour, T. & Shattuck, M. (2018). Combinatorial parameters on bargraphs of permutations, Trans. Combin., 7 (2), 1–16.
16. Osborn, J. & Prellberg, T. (2010). Forcing adsorption of a tethered polymer by pulling, J. Stat. Mech., P09018.
17. Mansour, T. (2018). Interior vertices in set partitions, Advances in Applied Mathematics, 101, 60–69.
18. Mansour, T. (2019). Border and tangent cells in bargraphs, Discrete Mathematics Letters, 1, 26–29.