The site-perimeter of words

We define [k]=\{۱‎, ‎۲‎, ‎۳,\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:

‎words‎ , ‎bargraphs‎ , ‎site-perimeter‎ , ‎generating functions