Partially ordered generalized patterns

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)

Abstract

We introduce partially ordered generalized patterns (POGPs), which further generalize the generalized permutation patterns (GPs) introduced by Babson and Steingrímsson [Sémin. Lotharingien Combin. B44b (2000) 18]. A POGP p is a GPe some of whose letters are incomparable. Thus, in an occurrence of p in a permutation π, two letters that are incomparable in p pose no restrictions on the corresponding letters in π. We describe many relations between POGPs and GPs and give general theorems about the number of permutations avoiding certain classes of POGPs. These theorems have several known results as corollaries but also give many new results. We also give the generating function for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, provided we know the exponential generating function for the number of permutations that avoid p.
Original languageEnglish
Pages (from-to)212-229
Number of pages18
JournalDiscrete Mathematics
Volume298
Issue number1-3
DOIs
Publication statusPublished - 6 Aug 2005

Keywords

  • permutations
  • non-overlapping occurrences of patterns
  • POGP
  • generalized patterns

Fingerprint

Dive into the research topics of 'Partially ordered generalized patterns'. Together they form a unique fingerprint.

Cite this