Counting the Palstars
Keywords:
palindrome, palstar, prime palstar, bordered word, analytic combinatorics,
Abstract
A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes. We show that, asymptotically, there are $\Theta(\alpha_k^n)$ palstars of length $2n$ over a $k$-letter alphabet, where $\alpha_k$ is a constant such that $2k-1 < \alpha_k < 2k-{1 \over 2}$. In particular, $\alpha_2\doteq 3.33513193$.
Published
2014-08-13
How to Cite
Richmond, L. B., & Shallit, J. O. (2014). Counting the Palstars. The Electronic Journal of Combinatorics, 21(3), #P3.25. https://doi.org/10.37236/4459
Article Number
P3.25