Counting Descents and Ascents Relative to Equivalence Classes mod k

摘要

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 + j ? 1 in σ have the same relative order as the elements of τ. If $Upsilon$ 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 $tau in Upsilon$ . A number of recent papers have studied the distribution of τ-matches and $Upsilon$ -matches in permutations. In this paper, we consider a more refined 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 $Upsilon$ -equivalence mod k matches for certain subsets of permutations of length 2.