Mathematics – Combinatorics
Scientific paper
2001-10-03
Mathematics
Combinatorics
Scientific paper
Babson and Steingr\'{\i}msson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Claesson presented a complete solution for the number of permutations avoiding any single pattern of type $(1,2)$ or $(2,1)$. For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. With respect to being equidistributed there are three different classes of patterns of type $(1,2)$ or $(2,1)$. We present a recursion for the number of permutations containing exactly one occurrence of a pattern of the first or the second of the aforementioned classes, and we also find an ordinary generating function for these numbers. We prove these results both combinatorially and analytically. Finally, we give the distribution of any pattern of the third class in the form of a continued fraction, and we also give explicit formulas for the number of permutations containing exactly $r$ occurrences of a pattern of the third class when $r\in\{1,2,3\}$.
Claesson Anders
Mansour Toufik
No associations
LandOfFree
Counting occurrences of a pattern of type (1,2) or (2,1) in permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting occurrences of a pattern of type (1,2) or (2,1) in permutations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-475089