Binary Words Avoiding xxRx and Strongly Unimodal Sequences

Abstract

In previous work, Currie and Rampersad showed that the growth of the number of binary words avoiding the pattern xxxR 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 xxRx. Curiously, the analysis for xxRx is much simpler than that for xxxR. We derive our results by giving a bijection between the set of binary words avoiding xxRx and a class of sequences closely related to the class of “strongly unimodal sequences”.