Counting Water Cells in Pattern Restricted Compositions

Toufik Mansour^1, and Mark Shattuck²

¹Department of Mathematics, University of Haifa, 3498838 Haifa, Israel

²Department of Mathematics, University of Tennessee, 37996 Knoxville, TN, USA

Cite this paper:
Toufik Mansour and Mark Shattuck. Counting Water Cells in Pattern Restricted Compositions. Turkish Journal of Analysis and Number Theory. 2019; 7(4):98-112. doi: 10.12691/tjant-7-4-2

Abstract

In this paper, we consider statistics on compositions of a positive integer represented geometrically as bargraphs that avoid certain classes of consecutive patterns. A unit square exterior to a bargraph that lies along a horizontal line between any two squares contained within its subtended area is called a water cell since it is a place where a liquid would collect if poured along the top part of the bargraph from above. The total number of water cells in the bargraph representation of a k-ary word then gives what is referred to as the capacity of w. Here, we determine the distribution of the capacity statistic on certain pattern-restricted compositions, regarded as k-ary words. Several general classes of patterns are considered, including and where a is arbitrary. As a consequence of our results, we obtain all of the distinct distributions for the capacity statistic on avoidance classes of compositions corresponding to 3-letter patterns having at most two distinct letters. Finally, in the case of some further enumerative results are given when a=2, including algebraic and bijective proofs for the total capacity of all Carlitz partitions of a given size having a fixed number of blocks.

Keywords:
consecutive pattern combinatorial statistic pattern-avoiding composition Carlitz composition

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	P. Duchon, q-Grammars and wall polyominoes, Ann. Comb. 3 (1999), 311-321.
[2]	A. Geraschenko, An investigation of skyline polynomials, avaialable at http://people.brandeis.edu/ gessel/47a/geraschenko.pdf.
[3]	A. Blecher, C. Brennan and A. Knopfmacher, Combinatorial parameters in bargraphs, Quaest. Math. 39 (2016), 619-635.
[4]	T. Mansour and M. Shattuck, Bargraph statistics on words and set partitions, J. Difference Equ. Appl. 23: 6 (2017), 1025-1046.
[5]	T. Prellberg and R. Brak, Critical exponents from nonlinear functional equations for partially directed cluster models, J. Stat. Phys. 78 (1995), 701-730.
[6]	S. Fereti´c, A perimeter enumeration of column-convex polyominoes, Discrete Math. Theor. Comput. Sci. 9(2007), 57-84.
[7]	A. Blecher, C. Brennan and A. Knopfmacher, Levels in bargraphs, Ars Math. Contemp. 9 (2015), 287-300.
[8]	A. Blecher, C. Brennan and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. S. Afr. 71 (2016), 97-103.
[9]	J. Osborn and T. Prellberg, Forcing adsorption of a tethered polymer by pulling, J. Stat. Mech. (2010), P09018.
[10]	A. Blecher, C. Brennan and A. Knopfmacher, Capacity of words, J. Combin. Math. Combin. Comput. 107 (2018), 249-258.
[11]	S. Heubach and T. Mansour, Combinatorics of Compositions and Words (Discrete Mathematics and its Applications), Chapman & Hall/CRC, Boca Raton, 2009.
[12]	T. Mansour and B. O. Sirhan, Counting ℓ-letter subwords in compositions, Discrete Math. Theor. Comput. Sci. 8 (2006), 285-298.
[13]	T. Mansour, M. Shattuck and S. H. F. Yan, Counting subwords in a partition of a set, Electron. J. Combin. 17 (2010), #R19.
[14]	C. G. Wagner, Generalized Stirling and Lah numbers, Discrete Math. 160 (1996), 199-218.
[15]	S. Milne, A q-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc. 245 (1978), 89-118.
[16]	T. Mansour and A. O. Munagi, Enumeration of partitions by long rises, levels, and descents, J. Integer Seq. 12 (2009), Art. 09.1.8.
[17]	A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, Mathematical Association of America, Washington DC, 2003.