Counting water cells in bargraphs of compositions and set partitions

Applicable Analysis and Discrete Mathematics

article

Toufik Mansour¹  Mark Shattuck² 

[1] Department of Mathematics, University of Haifa;Institute for Computational Science & Faculty of Mathematics and Statistics, Ton Duc Thang University

关键词: polynomial generalization;    bargraphs;    compositions;    Set partitions;   

DOI  :  10.2298/AADM170428010M

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

In this paper, we consider statistics on compositions and set partitions represented geometrically as bargraphs. By a water cell, we mean a unit squareexterior to a bargraph that lies along a horizontal line between any twosquares contained within the area subtended by the bargraph. That is, ifa large amount of a liquid were poured onto the bargraph from above andallowed to drain freely, then the water cells are precisely those cells where theliquid would collect. In this paper, we count both compositions and set partitions according to the number of descents and water cells in their bargraphrepresentations and determine generating function formulas for the joint distributions on the respective structures. Comparable generating functionsthat count non-crossing and non-nesting partitions are also found. Finally,we determine explicit formulas for the sign balance and for the first momentof the water cell statistic on set partitions, providing both algebraic andcombinatorial proofs.

【 授权许可】

Unknown