Kitaev, Sergey (2005) Partially ordered generalized patterns. Discrete Mathematics, 298 (1-3). pp. 212-229. ISSN 0012-365XFull text not available in this repository. (Request a copy from the Strathclyde author)
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.
|Keywords:||permutations, non-overlapping occurrences of patterns, POGP, generalized patterns, Electronic computers. Computer science, Discrete Mathematics and Combinatorics, Theoretical Computer Science|
|Subjects:||Science > Mathematics > Electronic computers. Computer science|
|Department:||Faculty of Science > Computer and Information Sciences|
|Depositing user:||Pure Administrator|
|Date Deposited:||14 Oct 2014 14:43|
|Last modified:||22 Mar 2017 13:34|