### Abstract

Original language | English |
---|---|

Pages (from-to) | 212-229 |

Number of pages | 18 |

Journal | Discrete Mathematics |

Volume | 298 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 6 Aug 2005 |

### Fingerprint

### Keywords

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

### Cite this

*Discrete Mathematics*,

*298*(1-3), 212-229. https://doi.org/10.1016/j.disc.2004.03.017

}

*Discrete Mathematics*, vol. 298, no. 1-3, pp. 212-229. https://doi.org/10.1016/j.disc.2004.03.017

**Partially ordered generalized patterns.** / Kitaev, Sergey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Partially ordered generalized patterns

AU - Kitaev, Sergey

PY - 2005/8/6

Y1 - 2005/8/6

N2 - 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.

AB - 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.

KW - permutations

KW - non-overlapping occurrences of patterns

KW - POGP

KW - generalized patterns

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/partial_order_patterns_perm.pdf

U2 - 10.1016/j.disc.2004.03.017

DO - 10.1016/j.disc.2004.03.017

M3 - Article

VL - 298

SP - 212

EP - 229

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -