Mathematics – Combinatorics
Scientific paper
2003-09-17
Mathematics
Combinatorics
17 pages, 1 figures, 2 tables
Scientific paper
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 \cite{Reg1998} for exact asymptotics for the number of words on $k$ letters of length $n$ that avoids the pattern $12...(\ell+1)$. Moreover, we give the first combinatorial proof of the exact formula \cite{Burstein} for the number of words on $k$ letters of length $n$ avoiding a three letter permutation pattern.
Brändén Petter
Mansour Toufik
No associations
LandOfFree
Finite automata and pattern avoidance in words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finite automata and pattern avoidance in words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite automata and pattern avoidance in words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-137695