Nhảy đến nội dung

Nine classes of permutations enumerated by binomial transform of Fine’s sequence

Authors: 

Toufik Mansour, Mark Shattuck*

Source title: 
Discrete Applied Mathematics, 226: 94-105, 2017 (ISI)
Academic year of acceptance: 
2017-2018
Abstract: 

The problem of avoidance of a single permutation pattern or of a pair of patterns of length four has been well studied. Less is known concerning the avoidance of three 4-letter patterns. In this paper, we determine up to symmetry all triples of 4-letter patterns such that the number of members of avoiding any one of them is given by the binomial transform of Fine’s sequence (see A033321 in OEIS). We make use of both algebraic and combinatorial proofs in order to establish our results. In a couple of cases, we introduce certain auxiliary statistics on Swhich give rise to a system of functional equations that can be solved using the kernel method. In another case, a direct bijection is defined between members of the avoidance class in question and the set of skew Dyck paths.