c Birkhauser Verlag, Basel, 2007 Annals of Combinatorics Counting Descents and Ascents Relative to Equivalence Classes mod k

AMS Subject Classication: 05A05, 05A15, 05A19 Abstract. Given a permutation τ of length j, we say that a permutation σ has a τ-match starting at position i, if the elements in position i; i+1; : : : ; i+ j1 in σ have the same relative order as the elements of τ. If ϒ is the set of permutations of length j, then we say that a permutation σ has a ϒ-match starting at position j if it has a τ-match at position j for some τ 2 ϒ. A number of recent papers have studied the distribution of τ-matches and ϒ-matches in permutations. In this paper, we consider a more rened pattern matching condition where we take into account conditions involving the equivalence classes of the elements mod k for some integer k 2. In this paper, we prove explicit formulas for the number of permutations of n which have s τ-equivalence mod k matches when τ is of length 2. We also show that similar formulas hold for ϒ-equivalence mod k matches for certain subsets of permutations of length 2