تعداد نشریات | 43 |
تعداد شمارهها | 1,677 |
تعداد مقالات | 13,681 |
تعداد مشاهده مقاله | 31,731,898 |
تعداد دریافت فایل اصل مقاله | 12,540,566 |
The site-perimeter of words | ||
Transactions on Combinatorics | ||
مقاله 8، دوره 6، شماره 2، شهریور 2017، صفحه 37-48 اصل مقاله (255.96 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22108/toc.2017.21465 | ||
نویسندگان | ||
Aubrey Blecher1؛ Charlotte Brennan* 2؛ Arnold Knopfmacher1؛ Toufik Mansour1 | ||
1University of the Witwatersrand | ||
21 Jan Smuts Avenue | ||
چکیده | ||
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. | ||
کلیدواژهها | ||
words؛ bargraphs؛ site-perimeter؛ generating functions | ||
مراجع | ||
[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. | ||
آمار تعداد مشاهده مقاله: 602 تعداد دریافت فایل اصل مقاله: 451 |