<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Counting Descents and Ascents Relative to Equivalence Classes mod k
Jeffrey Liese
Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA
Annals of Combinatorics 11 (3-4) p.481-506 September, 2007
AMS Subject Classification:05A05, 05A15, 05A19
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 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 τє. A number of recent papers have studied the distribution of τ-matches and -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 -equivalence mod k matches for certain subsets of permutations of length 2.
Keywords: permutations, restricted descent sets, rook placements


1. J. Haglund, Rook theory and hypergeometric series, Adv. Appl. Math. 17 (4) (1996) 408-- 459.

2. S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (1-2) (2003) 110--125.

3. S. Kitaev, Generalized patterns in words and permutations, Ph.D. thesis, Chalmers University of Technology and Göteborg University, 2003.

4. S. Kitaev, Partially ordered generalized patterns, Discrete Math. 298 (2005) 212--229.

5. S. Kitaev and T. Mansour, Partially ordered generalized patterns and k-ary words, Ann. Combin. 7 (2) (2003) 191--200.

6. S. Kitaev and J. Remmel, Classifying descents according to parity, Ann. Combin. 11 (2) (2007) 173--193.

7. S. Kitaev and J. Remmel, Classifying descents according to equivalence mod k, Electron. J. Combin. 13 (1) (2006) #R64.

8. G. Gasper, Summation formulas for basic hypergeometric series, SIAM J. Math. Anal. 12 (1981) 196--200.