1Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1, Canada 2School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada
The electronic journal of combinatorics, Tome 21 (2014) no. 3
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$.
Classification :
05A05, 05A15, 05A16, 68R15
Mots-clés :
palindrome, palstar, prime palstar, bordered word, analytic combinatorics
Affiliations des auteurs :
L. Bruce Richmond
1
;
Jeffrey O Shallit
2
1
Combinatorics and Optimization, University of Waterloo, Waterloo, ON N2L 3G1, Canada
2
School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada
@article{10_37236_4459,
author = {L. Bruce Richmond and Jeffrey O Shallit},
title = {Counting the palstars},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/4459},
zbl = {1300.05017},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4459/}
}
TY - JOUR
AU - L. Bruce Richmond
AU - Jeffrey O Shallit
TI - Counting the palstars
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4459/
DO - 10.37236/4459
ID - 10_37236_4459
ER -
%0 Journal Article
%A L. Bruce Richmond
%A Jeffrey O Shallit
%T Counting the palstars
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4459/
%R 10.37236/4459
%F 10_37236_4459
L. Bruce Richmond; Jeffrey O Shallit. Counting the palstars. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4459
