Partially ordered generalized patterns and k-ary words

Sergey Kitaev, Toufik Mansour

Research output: Contribution to journalArticle

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.
Original languageEnglish
Pages (from-to)191-200
Number of pages10
JournalAnnals of Combinatorics
Volume7
Issue number2
DOIs
Publication statusPublished - Jul 2003

Keywords

  • words
  • generalized patterns
  • partially ordered generalized patterns
  • generating functions

Fingerprint Dive into the research topics of 'Partially ordered generalized patterns and k-ary words'. Together they form a unique fingerprint.

  • Cite this