Counting ordered patterns in words generated by morphisms

Sergey Kitaev, Toufik Mansour, Patrice Seebold

Research output: Contribution to journalArticle

Abstract

We start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms. We consider certain patterns with gaps (classical patterns) and those with no gaps (consecutive patterns). Occurrences of the patterns are known,
in the literature, as rises, descents, (non-)inversions, squares and p-repetitions. We give recurrence formulas in the general case, then deducing exact formulas for particular families of morphisms. Many (classical or new) examples are given illustrating the techniques and
showing their interest.
LanguageEnglish
Article numberA-3
Number of pages28
JournalIntegers: Electronic Journal of Combinatorial Number Theory
Volume8
Issue number1
Publication statusPublished - 29 Jan 2008

Fingerprint

Morphisms
Counting
Recurrence Formula
Descent
Consecutive
Inversion

Keywords

  • classical patterns
  • ordered patterns
  • morphisms

Cite this

@article{b95824f19d7f4afe909bd4e831113619,
title = "Counting ordered patterns in words generated by morphisms",
abstract = "We start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms. We consider certain patterns with gaps (classical patterns) and those with no gaps (consecutive patterns). Occurrences of the patterns are known,in the literature, as rises, descents, (non-)inversions, squares and p-repetitions. We give recurrence formulas in the general case, then deducing exact formulas for particular families of morphisms. Many (classical or new) examples are given illustrating the techniques andshowing their interest.",
keywords = "classical patterns, ordered patterns, morphisms",
author = "Sergey Kitaev and Toufik Mansour and Patrice Seebold",
year = "2008",
month = "1",
day = "29",
language = "English",
volume = "8",
journal = "Integers: Electronic Journal of Combinatorial Number Theory",
issn = "1553-1732",
number = "1",

}

Counting ordered patterns in words generated by morphisms. / Kitaev, Sergey; Mansour, Toufik; Seebold, Patrice.

In: Integers: Electronic Journal of Combinatorial Number Theory, Vol. 8, No. 1, A-3, 29.01.2008.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Counting ordered patterns in words generated by morphisms

AU - Kitaev, Sergey

AU - Mansour, Toufik

AU - Seebold, Patrice

PY - 2008/1/29

Y1 - 2008/1/29

N2 - We start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms. We consider certain patterns with gaps (classical patterns) and those with no gaps (consecutive patterns). Occurrences of the patterns are known,in the literature, as rises, descents, (non-)inversions, squares and p-repetitions. We give recurrence formulas in the general case, then deducing exact formulas for particular families of morphisms. Many (classical or new) examples are given illustrating the techniques andshowing their interest.

AB - We start a general study of counting the number of occurrences of ordered patterns in words generated by morphisms. We consider certain patterns with gaps (classical patterns) and those with no gaps (consecutive patterns). Occurrences of the patterns are known,in the literature, as rises, descents, (non-)inversions, squares and p-repetitions. We give recurrence formulas in the general case, then deducing exact formulas for particular families of morphisms. Many (classical or new) examples are given illustrating the techniques andshowing their interest.

KW - classical patterns

KW - ordered patterns

KW - morphisms

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

UR - http://www.westga.edu/~integers/cgi-bin/get.cgi

M3 - Article

VL - 8

JO - Integers: Electronic Journal of Combinatorial Number Theory

T2 - Integers: Electronic Journal of Combinatorial Number Theory

JF - Integers: Electronic Journal of Combinatorial Number Theory

SN - 1553-1732

IS - 1

M1 - A-3

ER -