کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419286 683773 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Strongly restricted permutations and tiling with fences
ترجمه فارسی عنوان
تعویض های بسیار محدود و کاشی کاری با نرده ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

We identify bijections between strongly restricted permutations of {1,2,…,n}{1,2,…,n} of the form π(i)−i∈Wπ(i)−i∈W, where WW is any finite set of integers which is independent of ii and nn, and tilings of an nn-board (a linear array of nn square cells of unit width) using square tiles and (12,g)-fence tiles where g∈Z+g∈Z+. A (12,g)-fence is composed of two pieces of width 12 separated by a gap of width gg. The tiling approach allows us to obtain the recurrence relation for the number of permutations when W={−1,d1,…,dr}W={−1,d1,…,dr} where dr>0dr>0 and the remaining dldl are non-negative integers which are independent of ii and nn. 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 187, 31 May 2015, Pages 82–90
نویسندگان
, ,