\documentclass[12pt]{article} \usepackage{e-jc} \specs{P3.25}{21(3)}{2014} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \allowdisplaybreaks \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \usepackage{amscd} \usepackage{amsfonts} \usepackage{float} \title{\bf Counting the Palstars} \author{L. Bruce Richmond\\ \small Combinatorics and Optimization\\[-0.8ex] \small University of Waterloo \\[-0.8ex] \small Waterloo, ON N2L 3G1 \\[-0.8ex] \small Canada \\ \small {\tt lbrichmo@uwaterloo.ca} \and Jeffrey Shallit\\ \small School of Computer Science\\[-0.8ex] \small University of Waterloo \\[-0.8ex] \small Waterloo, ON N2L 3G1 \\[-0.8ex] \small Canada \\ \small {\tt shallit@cs.uwaterloo.ca} } \date{\dateline{Jun 12, 2014}{Jul 28, 2014}{Aug 13, 2014}\\ \small Mathematics Subject Classifications: 05A05, 05A15, 05A16, 68R15} \begin{document} \maketitle \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \begin{abstract} A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes. We show that, asymptotically, there are $D_k \alpha_k^n$ palstars of length $2n$ over a $k$-letter alphabet, where $D_k$ and $\alpha_k$ are positive constants with $2k-1 < \alpha_k < 2k-{1 \over 2}$. In particular, $\alpha_2 \doteq 3.33513193$. \bigskip\noindent \textbf{Keywords:} palindrome, palstar, prime palstar unique factorization, generating function, enumeration. \end{abstract} \section{Introduction} We are concerned with finite strings over a finite alphabet $\Sigma_k$ having $k \geq 2$ letters. A {\it palindrome} is a string $x$ equal to its reversal $x^R$, like the English word {\tt radar}. If $T, U$ are sets of strings over $\Sigma_k$ then (as usual) $TU = \lbrace tu \ : \ t \in T, u \in U \rbrace$. Also $T^i = \overbrace{TT \cdots T}^i$ and $T^* = \bigcup_{i \geq 0} T^i$ and $T^+ = \bigcup_{i \geq 1} T^i$. We define $$P = \lbrace x\, x^R \ : \ x \in \Sigma_k^+ \rbrace,$$ the language of nonempty even-length palindromes. Following Knuth, Morris, and Pratt \cite{Knuth&Morris&Pratt:1977}, we call a string $x$ a {\it palstar} if it belongs to $P^*$, that is, if it can be written as the concatenation of elements of $P$. Clearly every palstar is of even length. We call $x$ a {\it prime palstar} if it is a nonempty palstar, but not the concatenation of two or more palstars; alternatively, if $x \in P^+ - P^2 P^* $ where $-$ is set difference. Thus, for example, the the English word {\tt noon} is a prime palstar, but the English word {\tt appall} and the French word {\tt assailli} are palstars that are not prime. Knuth, Morris, and Pratt \cite{Knuth&Morris&Pratt:1977} proved that no prime palstar is a proper prefix of another prime palstar, and, consequently, every palstar has a unique factorization as a concatenation of prime palstars. A nonempty string $x$ is a {\it border} of a string $y$ if $x$ is both a prefix and a suffix of $y$ and $x \not= y$. We say a string $y$ is {\it bordered} if it has a border. Thus, for example, the English word {\tt ionization} is bordered with border {\tt ion}. Otherwise a word is {\it unbordered}. Rampersad et al.~\cite{Rampersad&Shallit&Wang:2011} recently gave a bijection between the unbordered strings of length $n$ and the prime palstars of length $2n$. As a consequence they obtained a formula for the number of prime palstars. Despite some interest in the palstars themselves \cite{Manacher:1975,Galil&Seiferas:1978}, it seems no one has enumerated them. Here we observe that the bijection mentioned previously, together with the unique factorization of palstars, provides an asymptotic enumeration for the number of palstars. \section{Generating function for the palstars} Again, let $k \geq 2$ denote the size of the alphabet. Let $p_k(n)$ denote the number of palstars of length $2n$, and let $u_k (n)$ denote the number of unbordered strings of length $n$. \begin{lemma} For $n \geq 1$ and $k \geq 2$ we have $$ p_k (n) = \sum_{1 \leq i \leq n} u_k(i) p_k(n-i) .$$ \label{one} \end{lemma} \begin{proof} Consider a palstar of length $2n > 0$. Either it is a prime palstar, and by \cite{Rampersad&Shallit&Wang:2011} there are $u_k(n) = u_k (n) p_k (0)$ of them, or it is the concatenation of two or more prime palstars. In the latter case, consider the length of this first factor; it can potentially be $2i$ for $1 \leq i \leq n$. Removing this first factor, what is left is also a palstar. This gives $u_k (i) p_k (n-i)$ distinct palstars for each $i$. Since factorization into prime palstars is unique, the result follows. \end{proof} Now we define generating functions as follows: \begin{eqnarray*} P_k (X) &=& \sum_{n \geq 0} p_k (n) X^n \\ U_k (X) &=& \sum_{n \geq 0} u_k (n) X^n . \end{eqnarray*} The first few terms are as follows: \begin{eqnarray*} P_k (X) &=& 1 + kX + (2k^2-k)X^2 + (4k^3-3k^2)X^3 + (8k^4-8k^3+k)X^4 + \cdots \\ U_k (X) &=& 1 + kX + (k^2-k)X^2 + (k^3-k^2)X^3 + (k^4-k^3-k^2+k)X^4 + \cdots . \end{eqnarray*} \begin{theorem} $$P_k (X) = {1 \over {2-U_k (X)}}.$$ \label{two} \end{theorem} \begin{proof} From Lemma~\ref{one}, we have \begin{eqnarray*} U_k (X) P_k (X) &=& \left(\sum_{n \geq 0} u_k (n) X^n \right) \left(\sum_{n \geq 0} p_k (n) X^n \right) \\ &=& 1 + \sum_{n \geq 1} \left(\sum_{0 \leq i \leq n} u_k(i) p_k (n-i) \right) X^n \\ &=& 1+ \left( \sum_{n \geq 1} \sum_{1 \leq i \leq n} u_k(i) p_k (n-i) X^n \right) + \sum_{n \geq 1} p_k(n) X^n \\ &=& 1 + \left( \sum_{n \geq 1} p_k (n) X^n \right) + \sum_{n \geq 1} p_k (n) X^n \\ &=& 2 P_k (X) - 1, \end{eqnarray*} from which the result follows immediately. \end{proof} \section{The main result} \begin{theorem} For all $k \geq 2$ there are positive constants $D_k$ and $\alpha_k$, with $2k -1 < \alpha_k < 2k-{1 \over 2}$, such that the number of palstars of length $2n$ is asymptotically $D_k \alpha_k^n$. \end{theorem} \begin{proof} From Theorem~\ref{two} and the ``First Principle of Coefficient Asymptotics'' \cite[p.~260]{Flajolet&Sedgewick:2009}, it follows that the asymptotic behavior of $[X^n] P_k (X)$, the coefficient of $X^n$ in $P_k (X)$, is controlled by the behavior of the roots of $U_k (X) = 2$. Since $u_{k}(0) = 1$ and $U_{k}(X) \rightarrow \infty$ as $X \rightarrow \infty$, the equation $U_k (X) = 2$ has a single positive real root, which is $\rho = \rho_k = \alpha_k^{-1}$. We first show that $2k -1 < \alpha_k < 2k-{1 \over 2}$. Recalling that $u_k(n)$ is the number of unbordered strings of length $n$ over a $k$-letter alphabet, we see that $u_k(n) \leq k^n - k^{n-1}$ for $n \geq 2$, since $k^n$ counts the total number of strings of length $n$, and $k^{n-1}$ counts the number of strings with a border of length $1$. Similarly $$u_k(n) \geq \begin{cases} k^n - k^{n-1} - \cdots - k^{n/2}, & \text{if $n \geq 2$ is even}; \\ k^n - k^{n-1} - \cdots - k^{(n+1)/2}, & \text{if $n \geq 2$ is odd}, \end{cases} $$ since this quantity represents removing strings with borders of lengths $1, 2, \ldots, n/2$ (resp., $1,2, \ldots, (n-1)/2$) if $n$ is even (resp., odd) from the total number. Here we use the classical fact that if a word of length $n$ has a border, it has one of length $\leq n/2$. It follows that for real $X > 0$ we have \begin{align*} U_k (X) = \sum_{n \geq 0} u_k(n) X^n = 1 + kX + \sum_{n \geq 2} u_k(n) X^n &\leq 1 + kX + \sum_{n \geq 2} (k^n - k^{n-1}) X^n \\ & = {{kX^2 - 1} \over {kX - 1 }} . \end{align*} Similarly for real $X > 0$ we have \begin{align*} U_k(X) & = \sum_{n \geq 0} u_k(n) X^n \\ &= 1 +kX + \sum_{l \geq 1} u_k (2l) X^{2l} + \sum_{m \geq 1} u_k (2m+1) X^{2m+1} \\ &\geq 1 + kX + \sum_{l \geq 1} (k^{2l} - k^{2l-1} - \cdots - k^l) X^{2l} + \sum_{m \geq 1} (k^{2m+1} - \cdots - k^{m+1}) X^{2m+1} \\ &= {{1-2kX^2} \over {(kX-1)(kX^2-1)}} . \end{align*} This gives, for $k \geq 2$, that $$ 2 < {{(2k-1) (4k^2 - 6k+1) } \over {(k-1)^2 (4k-1)}} \leq U_k \left({1 \over {2k-1}} \right) $$ and $$ U_k\left({ 1 \over {2k-{1\over 2}}}\right) \leq {{16k^2-12k+1} \over {(4k-1)(2k-1)}} < 2 .$$ It follows that ${1 \over {2k -{1 \over 2}}} < \rho_k < {1 \over {2k-1}} $ and hence $2k -1 < \alpha_k < 2k-{1 \over 2}$. To understand the asymptotic behavior of $[X^n] P_k (X)$, we need to rule out other (complex) roots with the same magnitude as $\rho$. Here we follow the argument of the anonymous referee, which replaces our earlier and more complicated argument \cite{Richmond&Shallit:2014}. Suppose $X = -\rho$ is a solution. Then, since $u_k (n) > 0$ for all $n$, we have $$2 = \sum_{n \geq 0} u_k (n) (-\rho)^n < \sum_{n \geq 0} u_k (n) \rho^n = 2.$$ This is a contradiction, so if there exists another solution it must be of the form $$X = \rho e^{i \psi} = \rho(\cos n\psi + i \sin n \psi)$$ with $0 < \psi < 2\pi$. Since $2 - U_k (X) = 0$, the imaginary part of $U_k(\rho e^{i \psi})$ must equal $0$. Therefore \begin{align*} 0 &= 2 - \sum_{n \geq 0} u_k (n) \rho^n \cos n \psi \\ &= 2 - \sum_{n \geq 0} u_k (n) \rho^n + \sum_{n \geq 0} u_k (n) \rho^n (1- \cos n \psi) \\ &= \sum_{n \geq 0} u_k (n) \rho^n (1-\cos n \psi) . \end{align*} Since $u_k(n) > 0$ and $\rho^n > 0$ for all $n$, we must have $1 - \cos n \psi = 0$ for all $n$. So for all $n$ there exists an integer $\ell_n$ such that $n \psi = 2 \pi \ell_n$. Hence $$\psi = (n+1) \psi - n \psi = 2 \pi \ell_{n+1} - 2\pi \ell_n = 2 \pi (\ell_{n+1} - \ell_n) .$$ Since $\ell_{n+1}$ and $\ell_n$ are both integers, this contradicts the assumption $0 < \psi < 2\pi$. Therefore $P_k (X)$ has only one singularity with $|X| = \rho$. It remains to determine the order of the zero $\rho$. From above $U_{k}(X) = 2$ has a solution $\alpha_{k}^{-1}$ which satisfies $2k - 1 < \alpha_{k} < 2k - {1 \over 2}$. Nielsen \cite{Nielsen:1973} showed that $u_k (n) = \Theta(k^{n})$, and so $U_{k}(X)$ has radius of convergence $1/k$. Therefore $1/\alpha_{k}$ lies in the region where $U_{k}$ is analytic. Hence $2 - U_{k}(X)$ is analytic at $1/\alpha_{k}$ and has a zero at $1/\alpha_{k}$ of multiplicity $m$. If $m \ge 2$, then the derivative of $2 - U_{k}(X)$ equals $0$ at $X = 1/\alpha_{k}$. However $C_k := U'_k(\alpha_k^{-1}) > 0$ since $u_{k}(n) > 0$ for some $n$. Thus $2 - U_{k}(X)$ has a simple zero at $X = 1/\alpha_{k}$, and so $P_{k}(X)$ has a simple pole at $X = 1/\alpha_{k}$. Near $\alpha_{k}^{-1}$ the generating function $ U_{k}(X)$ has the expansion $2 + C_k(X - \alpha_{k}^{-1}) + C'_k(X - \alpha_{k}^{-1})^{2} + \cdots$. Furthermore $$P_{k}(X) = \frac{1}{2 - U_{k}(X)} = \frac{1}{-C_k(X - 1/\alpha_{k}) - C'_k(X - 1/\alpha_{k})^{2} + \cdots}.$$ As we have seen, $$P_{k}(X) - \frac{\alpha_{k}}{C_k}\left(\frac{1}{1 - \alpha_{k}X}\right)$$ has no singularity on the circle $|X| = 1/\alpha_{k}$, and so it has radius of convergence $> 1/\alpha_{k}$. Now $$P'_k(X) = \frac{U'_k(X)}{(2 - U_{k}(X))^{2}},$$ so from standard results (e.g., \cite[Thm.~IV.7, p.~244]{Flajolet&Sedgewick:2009}) there exists a positive $\delta$ such that \begin{align*} [X^{n}]P_{k}(X) &= [X^{n}]\frac{1}{C_k(1/\alpha_{k} -X)} +\cdots \\ & = [X^{n}]\frac{\alpha_{k}}{C_k}\left(\frac{1}{1 - \alpha_{k}X}\right) + \cdots \\ & = \frac{\alpha_{k}^{n + 1}}{C_k} + O\left(\left(\alpha_{k} - \delta\right)^{n}\right). \\ \end{align*} Now, setting $D_k = \alpha_k/C_k$ completes the proof. \end{proof} \section{Numerical results} Here is a table giving the first few values of $P_k (n)$. {\setlength{\tabcolsep}{3pt} \begin{figure}[H] \begin{center} \begin{tabular}{cccccccccccc} \hline $n = $ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline $k = 2$& 1 & 2 & 6 & 20 & 66 & 220 & 732 & 2440 & 8134 & 27124 & 90452 \\ $k = 3$& 1 & 3 & 15 & 81 & 435 & 2349 & 12681 & 68499 & 370023 & 1998945 & 10798821 \\ $k = 4$& 1 & 4 & 28 & 208 & 1540 & 11440 & 84976 & 631360 & 4690972 & 34854352 & 258971536 \\ \hline \end{tabular} \end{center} \end{figure}} By truncating the power series $U_k(X)$ and solving the equation $U_k (X) = 2$ we get better and better approximations to $\alpha_k^{-1}$. For example, for $k = 2$ we have {\small \begin{eqnarray*} \alpha_2^{-1} &\doteq & 0.29983821359352690506155111814579603919303182364781730366339199333065202 \\ \alpha_2 & \doteq & 3.3351319300335793676678962610376244842363270634405611577104447308511860 \\ C_2 & \doteq & 6.278652437421018217684895562492005276088368718322063642652328654828673 \\ D_2 & \doteq & 0.5311859452764195757199152035728758998220694173731602615487298417 \end{eqnarray*} } To determine an asymptotic expansion for $\alpha_k$ as $k \rightarrow \infty$, we compute the Taylor series expansion for $P_k(n)/P_k(n+1)$, treating $k$ as an indeterminate, for $n$ large enough to cover the error term desired. For example, for $O(k^{-10})$ it suffices to take $k = 16$, which gives $$ \alpha_k^{-1} = {1 \over {2k}} + {1 \over {8k^2}} + {3 \over {32k^3}} + {1 \over {16k^4}} + {{27} \over {512k^5}} + {{93} \over {2048k^6}} + {{83} \over {2048k^7}} + {{155} \over {4096k^8}} + {{4735} \over {131072k^9}} + O(k^{-10}) $$ and hence $$ \alpha_k = 2k - {1 \over 2} - {1 \over {4k}} - {3 \over {32k^2}} - {5 \over {64k^3}} - {{31} \over {512k^4}} - {{25} \over {512k^5}} - {{23} \over {512 k^6}} - {{683} \over {16384k^7}} + O(k^{-8}).$$ \subsection*{Acknowledgment} We thank the anonymous referee for his/her very helpful report. \begin{thebibliography}{2} \bibitem{Galil&Seiferas:1978} Z. Galil and J. Seiferas. \newblock A linear-time on-line recognition algorithm for ``palstar''. \newblock {\em J. ACM} {\bf 25} (1978), 102--111. \bibitem{Flajolet&Sedgewick:2009} P. Flajolet and R. Sedgewick. \newblock {\em Analytic Combinatorics}. \newblock Cambridge University Press, 2009. \bibitem{Knuth&Morris&Pratt:1977} D.~E. Knuth, J.~Morris, and V.~Pratt. \newblock Fast pattern matching in strings. \newblock {\em SIAM J. Comput.} {\bf 6} (1977), 323--350. \bibitem{Manacher:1975} G. Manacher. \newblock A new linear-time ``on-line'' algorithm for finding the smallest initial palindrome of a string. \newblock {\em J. ACM} {\bf 22} (1975), 346--351. \bibitem{Nielsen:1973} P. T. Nielsen. \newblock A note on bifix-free sequences. \newblock {\em IEEE Trans. Info. Theory} {\bf IT-19} (1973), 704--706. \bibitem{Rampersad&Shallit&Wang:2011} N. Rampersad, J. Shallit, and M.-w. Wang. \newblock Inverse star, borders, and palstars. \newblock {\em Info. Proc. Letters} {\bf 111} (2011), 420--422. \bibitem{Richmond&Shallit:2014} L. B. Richmond and J. Shallit. \newblock Counting the palstars. \newblock Preprint, June 11 2014, available at \arxiv{1311.2318}. \end{thebibliography} \end{document}