Publication: Strongly restricted permutations and tiling with fences
Issued Date
2015-01-01
Resource Type
ISSN
0166218X
Other identifier(s)
2-s2.0-84928205201
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Discrete Applied Mathematics. Vol.187, (2015), 82-90
Suggested Citation
Kenneth Edwards, Michael A. Allen Strongly restricted permutations and tiling with fences. Discrete Applied Mathematics. Vol.187, (2015), 82-90. doi:10.1016/j.dam.2015.02.004 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/36201
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Strongly restricted permutations and tiling with fences
Author(s)
Other Contributor(s)
Abstract
© 2015 Elsevier B.V. We identify bijections between strongly restricted permutations of {1,2,⋯,n} of the form π(i)-iεW, where W is any finite set of integers which is independent of i and n, and tilings of an n-board (a linear array of n square cells of unit width) using square tiles and (12,g)-fence tiles where gε<sup>Z+</sup>. A (12,g)-fence is composed of two pieces of width 12 separated by a gap of width g. The tiling approach allows us to obtain the recurrence relation for the number of permutations when W={-1,<sup>d1</sup>,⋯,<sup>dr</sup>} where <sup>dr</sup>>0 and the remaining <sup>dl</sup> are non-negative integers which are independent of i and n. This is a generalization of a previous result. Terms in this recurrence relation, along with terms in other recurrences we obtain for more complicated cases, can be identified with certain groupings of interlocking tiles. The ease of counting tilings gives rise to a straightforward way of obtaining identities concerning the number of occurrences of patterns such as fixed points or excedances in restricted permutations. We also use the tilings to obtain the possible permutation cycles.