Blecher, A., Brennan, C., Knopfmacher, A., Mansour, T. (2017). The site-perimeter of words. Transactions on Combinatorics, 6(2), 37-48. doi: 10.22108/toc.2017.21465

Aubrey Blecher; Charlotte Brennan; Arnold Knopfmacher; Toufik Mansour. "The site-perimeter of words". Transactions on Combinatorics, 6, 2, 2017, 37-48. doi: 10.22108/toc.2017.21465

Blecher, A., Brennan, C., Knopfmacher, A., Mansour, T. (2017). 'The site-perimeter of words', Transactions on Combinatorics, 6(2), pp. 37-48. doi: 10.22108/toc.2017.21465

Blecher, A., Brennan, C., Knopfmacher, A., Mansour, T. The site-perimeter of words. Transactions on Combinatorics, 2017; 6(2): 37-48. doi: 10.22108/toc.2017.21465

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.

[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. Stauﬀer and A. Aharony, An Introduction to Percolation Theory, 2nd edition, Taylor and Francis, London, 1992.