The site-perimeter of words

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...

Full description

Saved in:
Bibliographic Details
Published in:Transactions on combinatorics 2017-06, Vol.6 (2), p.37-48
Main Authors: Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher, Toufik Mansour
Format: Article
Language:English
Subjects:
bargraphs
generating functions
site-perimeter
words
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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‎.
ISSN:2251-8657
2251-8665
DOI:10.22108/toc.2017.21465