In previous work, Currie and Rampersad showed that the growth of the number of binary words avoiding the pattern x x xR was intermediate between polynomial and exponential. We now show that the same result holds for the growth of the number of binary words avoiding the pattern x xR x . Curiously, the analysis for x xR x is much simpler than that for x x xR. We derive our results by giving a bijection between the set of binary words avoiding x xR x and a class of sequences closely related to the class of "strongly unimodal sequences".
展开▼
机译:在先前的工作中,Currie和Rampersad表明避免模式x x xR的二进制单词数量的增长在多项式和指数之间。现在我们表明,相同的结果对于避免模式x xR x的二进制字数的增长也成立。奇怪的是,对于x xR x的分析比对于x x xR的分析要简单得多。通过给出避免x xR x的二元词集合与与“强单峰序列”类别密切相关的一类序列之间的二射,我们得出了结果。
展开▼