Segmented partially ordered generalized patterns

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

We continue the study of partially ordered generalized patterns (POGPs) considered in [E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire, 2000, B44b:18pp] for permutations and in [A. Burstein, T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electron. J. Combin. 9 (2) (2002) #R3] for words. We deal with segmental POGPs (SPOGPs). We state some general results and treat a number of patterns of length 4. We prove a result from [S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math. 260 (2003) 89–100] in a much simpler way and also establish a connection between SPOGPs and walks on lattice points starting from the origin and remaining in the positive quadrant. We give a combinatorial interpretation of the powers of the (generalized) Fibonacci numbers. The entire distribution of the maximum number of non-overlapping occurrences of a generalized pattern with no dashes in permutations or words studied in [S. Kitaev, Partially ordered generalized patterns, Discrete Math. to appear, S. Kitaev, T. Mansour, Partially ordered generalized patterns and k-ary words, Ann. Combin. 7 (2003) 191–200], respectively, has its counterpart in case of SPOGPs.
Original languageEnglish
Pages (from-to)420-428
Number of pages9
JournalTheoretical Computer Science
Volume349
Issue number3
Early online date6 Oct 2005
DOIs
Publication statusPublished - 16 Dec 2005

Keywords

  • pattern avoidance
  • distribution
  • walks on lattice points
  • words
  • permutations
  • segmental patterns

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

Cite this