Chimneys in compositions and bargraphs

Margaret Archibald; Aubrey Blecher; Arnold Knopfmacher; Toufik Mansour

doi:10.47443/dml.2023.103

Author(s)

Margaret Archibald 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

Aubrey Blecher 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

Arnold Knopfmacher 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

Toufik Mansour Department of Mathematics, University of Haifa,199 Abba Khoushy Ave, 3498838 Haifa,Israel

Abstract

Motivated by cut points in graph theory, we consider a similar notion in compositions and bargraphs. This is equivalent to counting r-chimneys (a single column extending beyond its immediate neighbours by at least r cells in a bargraph). We establish generating functions for compositions that avoid or count 2-chimneys. Thereafter, in the case of bargraphs we provide two methods for obtaining these generating functions as well as asymptotic estimates for the more general r-chimneys where r≥1.

Publication Details

Page(s) 122-129

DOI 10.47443/dml.2023.103

Published Journal: Discrete Mathematics Letters, Volume: 12, Issue: 0, Year: 2023

Request the full text from PASTIC

Keywords

Generating Function, chimneys, compositions, bargraphs