<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue2" %>
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
AMS Subject Classification: 05A05, 05A15
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.
Keywords: words, generalized patterns, partially ordered generalized patterns, generating functions


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.