Counting the Palstars

  • L. Bruce Richmond
  • Jeffrey O Shallit
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
Article Number
P3.25