Nhảy đến nội dung

Counting corners in compositions and set partitions presented as bargraphs

Authors: 

Toufik Mansour, Armend Sh. Shabani & Mark Shattuck

Source title: 
Journal of Difference Equations and Applications, 24(6): 992-1015, 2018 (ISI)
Academic year of acceptance: 
2018-2019
Abstract: 

In this paper, we consider statistics on compositions of a fixed number and set partitions of a fixed size represented geometrically as bargraphs. By a corner of a bargraph, we mean a vertex along its polygonal boundary, where types of corners are identified by the sequence of steps directly before and after. Here, we find a generating function formula of the joint distribution for the statistics on compositions of n recording the number of corners of types uh or dh. We also find an explicit formula for the total number of corners of either type in all compositions of n, supplying both algebraic and combinatorial proofs. We then determine the joint distribution on compositions for corners of type uhi for all i less than some fixed number as well as the comparable distributions for corners of type uhi and hid on set partitions of size n having k blocks. In deriving our results, we solve various types of difference equations that are satisfied by the generating functions, using inductive arguments to determine closed form expressions.