The site-perimeter of words

Document Type : Research Paper

Authors

1 University of the Witwatersrand

2 1 Jan Smuts Avenue

Abstract

We define $[k]=\{1‎, ‎2‎, ‎3,\ldots,k\}$ to be a (totally ordered) {\em alphabet} on $k$ letters‎. ‎A {\em word} $w$ of length $n$ on the alphabet $[k]$ is an element of $[k]^n$‎. ‎A word can be represented by a bargraph which is a family of column-convex polyominoes whose lower edge lies on the $x$-axis and in which the height of the $i$-th column in the bargraph equals the size of the $i$-th part of the word‎. ‎Thus these bargraphs have heights which are less than or equal to $k$‎. ‎We consider the site-perimeter‎, ‎which is the number of nearest-neighbour cells outside the boundary of the polyomino‎. ‎The generating function that counts the site-perimeter of words is obtained explicitly‎. ‎From a functional equation we find the average site-perimeter of words of length $n$ over the alphabet $[k]$‎. ‎We also show how these statistics may be obtained using a direct counting method and obtain the minimum and maximum values of the site-perimeters‎.

Keywords

Main Subjects

References

[1] A. Bacher, Average site p erimeter of directed animals on the two-dimensional lattices, Discrete Math., 312 (2012) 1038-1058.
[2] A. Blecher, C. Brennan and A. Knopfmacher, The site-p erimeter in p ermutations, Utilitas Math., in press.
[3] M. Bousquet-Melou, A metho d for the enumeration of various classes of column-convex p olygons, Discrete Math., 154 (1996) 1-25.
[4] M. Bousquet-Melou and A. Rechnitzer, The site-p erimeter of bargraphs, Adv. in Appl. Math., 31 (2003) 86-112.
[5] M. Delest, D. Gouyou-Beauchamps and B. Vauquelin, Enumeration of parallelogram p olyomino es with given b ond and site p erimeter, Graphs Combin., 3 (1987) 325-339.
[6] G. F ulep and N. Sieb en, Polyiamonds and p olyhexes with minimum site-p erimeter and achievement games, Elect. J. Combin., 17 (2010) ♯R65.
[7] G. Grimmett, Percolation, Springer-Verlag, New York, 1989.
[8] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Discrete Mathematics and its applications, CRC press, Taylor and Francis group, 2010.
[9] N. Sieb en, Polyomino es with minimum site-p erimeter and full set achievement games, Europ. J. Combin., 29 (2008) 108-117.
[10] D. Stauffer and A. Aharony, An Introduction to Percolation Theory, 2nd edition, Taylor and Francis, London, 1992.

Files

History

  • Receive Date: 26 January 2016
  • Revise Date: 20 January 2017
  • Accept Date: 29 January 2017
  • Published Online: 01 June 2017

Share

How to cite

Statistics