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.