Avoidance of partially ordered patterns in compositions

Silvia Heubach, Sergey Kitaev, Toufik Mansour

Research output: Contribution to journalArticle

Abstract

A partially ordered (generalized) pattern (POP) is a generalized pattern some of whose letters are incomparable. In this paper, we study avoidance of POPs in compositions and generalize results for avoidance of POPs in permutations and words. Specifically, we obtain results for the generating functions for the number of compositions that avoid shuffle patterns and multi-patterns. In addition, we give the generating function for the distribution of the maximum number of non-overlapping occurrences of a segmented POP t among the compositions of n, provided we know the generating function for the number of compositions of n that avoid t.
LanguageEnglish
Pages123–134
Number of pages12
JournalPure Mathematics and Applications
Volume17
Issue number1-2
Publication statusPublished - 2007

Fingerprint

Generating Function
Shuffle
Permutation
Generalise

Keywords

  • compositions
  • partially ordered generalized patterns
  • non-over-lapping occurrences
  • generating functions

Cite this

Heubach, Silvia ; Kitaev, Sergey ; Mansour, Toufik. / Avoidance of partially ordered patterns in compositions. In: Pure Mathematics and Applications. 2007 ; Vol. 17, No. 1-2. pp. 123–134.
@article{1d9fc1c35d6a45a5a3b8b5dd59ca164f,
title = "Avoidance of partially ordered patterns in compositions",
abstract = "A partially ordered (generalized) pattern (POP) is a generalized pattern some of whose letters are incomparable. In this paper, we study avoidance of POPs in compositions and generalize results for avoidance of POPs in permutations and words. Specifically, we obtain results for the generating functions for the number of compositions that avoid shuffle patterns and multi-patterns. In addition, we give the generating function for the distribution of the maximum number of non-overlapping occurrences of a segmented POP t among the compositions of n, provided we know the generating function for the number of compositions of n that avoid t.",
keywords = "compositions, partially ordered generalized patterns, non-over-lapping occurrences, generating functions",
author = "Silvia Heubach and Sergey Kitaev and Toufik Mansour",
year = "2007",
language = "English",
volume = "17",
pages = "123–134",
journal = "Pure Mathematics and Applications",
issn = "1218-4586",
number = "1-2",

}

Heubach, S, Kitaev, S & Mansour, T 2007, 'Avoidance of partially ordered patterns in compositions' Pure Mathematics and Applications, vol. 17, no. 1-2, pp. 123–134.

Avoidance of partially ordered patterns in compositions. / Heubach, Silvia; Kitaev, Sergey; Mansour, Toufik.

In: Pure Mathematics and Applications, Vol. 17, No. 1-2, 2007, p. 123–134.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Avoidance of partially ordered patterns in compositions

AU - Heubach, Silvia

AU - Kitaev, Sergey

AU - Mansour, Toufik

PY - 2007

Y1 - 2007

N2 - A partially ordered (generalized) pattern (POP) is a generalized pattern some of whose letters are incomparable. In this paper, we study avoidance of POPs in compositions and generalize results for avoidance of POPs in permutations and words. Specifically, we obtain results for the generating functions for the number of compositions that avoid shuffle patterns and multi-patterns. In addition, we give the generating function for the distribution of the maximum number of non-overlapping occurrences of a segmented POP t among the compositions of n, provided we know the generating function for the number of compositions of n that avoid t.

AB - A partially ordered (generalized) pattern (POP) is a generalized pattern some of whose letters are incomparable. In this paper, we study avoidance of POPs in compositions and generalize results for avoidance of POPs in permutations and words. Specifically, we obtain results for the generating functions for the number of compositions that avoid shuffle patterns and multi-patterns. In addition, we give the generating function for the distribution of the maximum number of non-overlapping occurrences of a segmented POP t among the compositions of n, provided we know the generating function for the number of compositions of n that avoid t.

KW - compositions

KW - partially ordered generalized patterns

KW - non-over-lapping occurrences

KW - generating functions

UR - http://puma.dimai.unifi.it/17_1_2.php

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

M3 - Article

VL - 17

SP - 123

EP - 134

JO - Pure Mathematics and Applications

T2 - Pure Mathematics and Applications

JF - Pure Mathematics and Applications

SN - 1218-4586

IS - 1-2

ER -