Combinatorial parameters in bargraphs

Abstract

Bargraphs are non-intersecting lattice paths in N2 0 with 3 allowed types of steps; up (0, 1), down (0,−1) and horizontal (1, 0). They start at the origin with an up step and terminate immediately upon return to the x-axis. We unify the study of integer compositions (ordered partitions) with that of bargraph lattice paths by obtaining a single generating function for both these structures. We also obtain the asymptotic expected size of the underlying composition associated with an arbitrary bargraph as the semiperimeter tends to infinity (equivalently the expected value for the total area under the bargraph). In addition, the number of descents, the number of up steps and the number of level steps are found together with their asymptotic expressions for large semiperimeter.

Mathematics Subject Classification (2010): Primary: 05A15, 05A16; Secondary: 60C05.

Key words: Bargraphs, compositions, generating functions.