Counting the Palstars

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-\frac{1}{2}$. In particular, ${\alpha }_2\doteq 3.33513193$.