• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Using homological duality in consecutive pattern avoidance

Electronic Journal of Combinatorics. 2011. Vol. 18. No. 2:9. P. 1-17.
Khoroshkin A., Shapiro B.

This paper deals with consecutive pattern avoidance. Recall that, in combinatorics, one suggests to consider the following notion of divisibility for permutations. We say that the permutation σ∈Sn is divisible by π∈Sm iff there exists an interval [i+1,i+m] of length m such that the integers in the sequence (σ(i),…,σ(i+m−1)) has the same local order as the integers in the sequence (π(1),…,π(m)). In other words π(s)>π(t)⇔σ(i+s)>σ(i+t). We say that σ is divisible from the left (resp. from the right) by π iff in the above assumptions the interval [i+1,i+m] is the leftmost (resp. rightmost) sub-interval of [1,n] of length m. Finally, we say that σ avoids π iff σ is not divisible by π. We proved that the generating series for the number of permutations avoiding elements of a given collection of patterns from a given set S depends only on the combinatorics of the overlappings of patterns in these sets. We say that ν is an overlapping of π1 and π2 if ν is divisible from the left by π1 and divisible from the right by π2 but the length of ν is strictly less than the sum of lengths of π1 and π2. We present a direct algorithm for the computation of the inverse generating functions. As an application we present a large class of patterns where this algorithm is fast and, in particular, allows to obtain a linear ordinary differential equation with polynomial coefficients satisfied by the inverse generating function.