Partially
Ordered Generalized Patterns and *k*-ary Words

Sergey Kitaev and Toufik Mansour

Matematik, Chalmers tekniska högskola och Göteborgs universitet,
412 96 Göteborg, Sweden

{kitaev, toufik}@math.chalmers.se

Annals of Combinatorics 7 (2) p.191-200 June, 2003

Abstract:

Recently, Kitaev [9]
introduced partially ordered generalized patterns (POGPs) in the symmetric group,
which further generalize the generalized permutation patterns introduced by
Babson and Steingrímsson [1]. A POGP p is a GP some of whose letters are
incomparable. In this paper, we study the generating functions (g.f.) for the
number of k-ary words avoiding some POGPs. We give analogues, extend and generalize
several known results, as well as get some new results. In particular, we give
the g.f. for the entire distribution of the maximum number of non-overlapping
occurrences of a pattern p with no dashes (which is allowed to have repetition
of letters), provided we know the g.f. for the number of k-ary words that avoid
p.

References:

1. E. Babson and E. Steingrimsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. B44b (2000) 18 pp.

2. A. Burstein, Enumeration of words with forbidden patterns, Ph.D. Thesis, University of Pennsylvania, 1998.

3. A. Burstein and T. Mansour, Words restricted by patterns with at most 2 distinct letters, Elect. J. Combin. 9 (2) (2002) #R3.

4. A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Ann. Combin. 7 (2003) 1每14.

5. A. Burstein and T. Mansour, Counting occurrences of some subword patterns, Discrete Math. Theoret. Comput. Sci. 6 (1) (2003) 1每12.

6. A. Claesson, Generalised pattern avoidance, Europ. J. Combin. 22 (2001) 961每971.

7. A. Claesson and T. Mansour, Enumerating permutations avoiding a pair of Babson- Steingr赤msson Patterns<, preprint, CO/0107044.

8. S. Kitaev, Multi-avoidance of generalised patterns, Discrete Math. 260 (2003) 89每100.

9. S. Kitaev, Partially ordered generalized patterns, Discrete Math., to appear.

10. D.E. Knuth, The Art of Computer Programming, 2nd Ed., Addison Wesley, Reading, MA, 1973.

11. R. Simion and F. Schmidt, Restricted permutations, Europ. J. Combin. 6 (4) (1985) 383每406.

12. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge University Press, 1997.