2003/09/17 by Petter Brändén, Brändén, Petter, Toufik Mansour +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #math.CO #msc:05A05 #msc:05A15 #msc:68Q45 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0309269
17 pages, 1 figures, 2 tables
arxiv created 2003/09/17 · arxiv updated 2009/12/01
We say that a word w on a totally ordered alphabet avoids the word v if there are no subsequences in w order-equivalent to v. In this paper we suggest a new approach to the enumeration of words on at most k letters avoiding a given pattern. By studying an automaton which for fixed k generates the words avoiding a given pattern we derive several previously known results for these kind of problems, as well as many new. In particular, we give a simple proof of the formula \citeReg1998 for exact asymptotics for the number of words on k letters of length n that avoids the pattern 12...(ℓ+1). Moreover, we give the first combinatorial proof of the exact formula \citeBurstein for the number of words on k letters of length n avoiding a three letter permutation pattern.