\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Counting Palindromes According to $r$-Runs of Ones Using Generating Functions\\
}
\vskip 1cm
\large
Helmut Prodinger\\
Department of Mathematics\\
Stellenbosch University\\
7602 Stellenbosch\\
South Africa\\
\href{mailto:hproding@sun.ac.za}{\tt hproding@sun.ac.za} \\
\end{center}

\vskip .2 in

\begin{abstract}
We derive
generating functions for the enumeration of all
palindromic binary strings of length $n$ having only runs of $1$'s of
length $\le r$.  We provide asymptotic
expressions for fixed $r$ and $n\to\infty$.  Eventually, $r$ is treated
as a random variable and an asymptotic equivalent for the largest run
of $1$'s in binary palindromes is derived.
\end{abstract}






\section{Enumeration}

In the recent paper~\cite{Nyblom13} the interest was in words over the alphabet $\{0,1\}$ which are \emph{palindromes} and have runs of $1$'s of bounded length. We firmly believe that \emph{generating functions} are the most appropriate tool here, and since they were not used in
~\cite{Nyblom13}, we present this natural approach and show as well how one can deal with the case that the maximal 1-run length is treated as a \emph{random variable}. 
It is worthwhile to note that all our methods can be found in \cite{FlSe09}.

Let us start with palindromes of \emph{even length}; they are given as $ww^R$, with a reversed copy of $w$ attached to $w$. In unrestricted words, the following factorization is 
appropriate:
\begin{equation*}
(\bold0+\bold1)^*=(\bold1^*\bold0)^*\bold1^*.
\end{equation*}
Here, we used the $*$-operation, common in the study of formal languages, so $L^*$ denotes all words that can be formed from concatenating words taken from $L$ in all possible ways. In \cite{FlSe09}, the notation
$\textsc{Seq}(L)$ is mostly used, describing all \textsc{Seq}uences (aka words), formed from $L$.
Now, the mentioned factorization is a very common one for binary words. Each word is (uniquely) decomposed according to each appearence of the letter $0$; between them, there are runs (possibly empty) of the letter $1$. If a word has $s$ letters $0$, then there are $s+1$ such runs of $1$'s. In terms of generating functions, since the transition $A\to A^*$ means $f\to \frac1{1-f}$, the factorization reads as
\begin{equation*}
\frac1{1-2z}=\frac1{1-\dfrac{z}{1-z}}\frac1{1-z}.
\end{equation*}
This factorization can immediately be generalized to the instance when the 1-runs should not exceed the parameter $r$. Then  we first consider the set of restricted runs
\begin{equation*}
\bold1^{\le r}=\{\varepsilon,1,11,\dots,1^r\},
\end{equation*}
which translates into
\begin{equation*}
1+z+\cdots+z^r=\frac{1-z^{r+1}}{1-z}.
\end{equation*}
Then we get the formal expression
\begin{equation*}
(\bold1^{\le r}\bold0)^*\bold1^{\le r},
\end{equation*}
which translates into
\begin{equation*}
\frac1{1-\dfrac{z(1-z^{r+1})}{1-z}}\frac{1-z^{r+1}}{1-z}=\frac{1-z^{r+1}}{1-2z+z^{r+2}}.
\end{equation*}


Now, going to palindromes of even length, the last group of ones must be bounded by $\lfloor \frac r2\rfloor$.
So a syntactic description of palindromes of even length with bounded 1-runs is
\begin{equation*}
(\bold1^{\le r}\bold0)^*\bold1^{\le \lfloor \frac r2\rfloor};
\end{equation*}
this describes the first half of the word only.
From this we go immediately to generating functions, by replacing both letters by a variable $z$. In this way, we count half of the length of the palindromes of even length.
If one wants the full length, one must replace $z$ by $z^2$. So we get
\begin{equation}\label{eve}
\frac{1}{1-z\dfrac{1-z^{r+1}}{1-z}}\dfrac{1-z^{ \lfloor \frac r2\rfloor+1}}{1-z}
=\frac{1-z^{ \lfloor \frac r2\rfloor+1}}{1-2z+z^{r+2}}.
\end{equation}
One can read off the coefficient of $z^n$ in the power series expansion of this expression, which leads to a clumsy expression:

Set 
\begin{equation*}
a_{n,r}=[z^n]\frac{1}{1-2z+z^{r}},
\end{equation*}
then 
\begin{equation*}
a_{n,r}-2a_{n-1,r}+a_{n-r,r}=0, 
\end{equation*}
and initial conditions $a_{n,r}=2^n$ for $n<r$. 

Then the number of palindromes of even length $2n$ with all 1-runs $\le r$ is given by
\begin{equation*}
[z^n]\frac{1-z^{ \lfloor \frac r2\rfloor+1}}{1-2z+z^{r+2}}=	
a_{n,r+2}-a_{n-\lfloor \tfrac r2\rfloor-1,r+2}.
\end{equation*}

We can alternatively express the coefficients in (\ref{eve}) using the
 \emph{higher order Fibonacci numbers}, as it was done in \cite{Nyblom13}:
Consider $U_{n,r}=U_{n-1,r}+\cdots+U_{n-r,r}$ for $n\ge r$, with initial values
$U_{0,r}=\dots=U_{r-2,r}=0$, $U_{r-1,r}=1$. Then
\begin{equation*}
\sum_{n\ge0}U_{n,r}z^n=\frac{z^{r-1}}{1-(z^r+\cdots+ z)}=\frac{z^{r-1}}{1-z\frac{1-z^r}{1-z}}=
\frac{z^{r-1}(1-z)}{1-2z+z^{r+1}}.
\end{equation*}
Further,
\begin{equation*}
\sum_{n\ge0}(U_{0,r}+\cdots+U_{n,r})z^n=
\frac{z^{r-1}}{1-2z+z^{r+1}},
\end{equation*}
or
\begin{equation*}
\sum_{k=0}^{n+r}U_{k,r+1}=[z^n]\frac{1}{1-2z+z^{r+2}}.
\end{equation*}
Consequently
\begin{align*}
[z^n]\frac{1-z^{ \lfloor \frac r2\rfloor+1}}{1-2z+z^{r+2}}&=	
[z^n]\frac{1}{1-2z+z^{r+2}}-[z^{n-\lfloor \frac r2\rfloor-1}]\frac{1}{1-2z+z^{r+2}}\\
&=\sum_{k=0}^{n+r}U_{k,r+1}-\sum_{k=0}^{n-\lfloor \frac r2\rfloor-1+r}U_{k,r+1}\\
&=\sum_{k=n-\lfloor \frac r2\rfloor+r}^{n+r}U_{k,r+1}.
\end{align*}
This is the expression given in \cite{Nyblom13} once one changes the index of summation.
Note that $r-\lfloor\frac{r}{2}\rfloor=\lceil\frac r2\rceil$.




Now we move to palindromes of odd length with middle letter 1: $w1w^R$. Then $w$ is described by
\begin{equation*}
(\bold1^{\le r}\bold0)^*\bold1^{\le \lfloor \frac {r-1}2\rfloor}.
\end{equation*}
In this way, the last group of ones plus the middle 1 plus the first group of ones of the reversed word
is still $\le r$ as it should.

The corresponding generating function is
\begin{equation*}
\frac{1-z^{ \lfloor \frac {r-1}2\rfloor+1}}{1-2z+z^{r+2}}
\end{equation*}
and the coefficient of $z^n$ (counting palindromes of odd length $2n+1$ with middle letter 1)
is
\begin{equation*}
a_{n,r+2}-a_{n-\lfloor \tfrac {r-1}2\rfloor-1,r+2}.
\end{equation*}

Again, we can alternatively express the corresponding number by higher order Fibonacci numbers:
\begin{align*}
[z^n]\frac{1-z^{ \lfloor \frac {r-1}2\rfloor+1}}{1-2z+z^{r+2}}&=	
[z^n]\frac{1}{1-2z+z^{r+2}}-[z^{n-\lfloor \frac {r-1}2\rfloor-1}]\frac{1}{1-2z+z^{r+2}}\\
&=\sum_{k=0}^{n+r}U_{k,r+1}-\sum_{k=0}^{n-\lfloor \frac {r-1}2\rfloor-1+r}U_{k,r+1}\\
&=\sum_{k=n-\lfloor \frac {r-1}2\rfloor+r}^{n+r}U_{k,r+1}.
\end{align*}
Note that $r-\lfloor\frac{r-1}{2}\rfloor=\lfloor\frac{r}{2}\rfloor+1$.

Finally we move to palindromes of odd length with middle letter 0: $w0w^R$.
Then we have
\begin{equation*}
(\bold1^{\le r}\bold0)^*\bold1^{\le r},
\end{equation*}
since the middle 0 interrupts the last run of ones of the first group. The corresponding generating function
is
\begin{equation*}
\frac{1-z^{ r+1}}{1-2z+z^{r+2}},
\end{equation*}
where again the coefficient of $z^n$ refers to a palindrome of length $2n+1$ with middle 0.

Explicitly we get 
\begin{equation*}
[z^n]\frac{1-z^{ r+1}}{1-2z+z^{r+2}}=a_{n,r+2}-a_{n-r-1,r+2}.
\end{equation*}
In terms of higher order Fibonacci numbers, this reads
\begin{align*}
[z^n]\frac{1-z^{r+1}}{1-2z+z^{r+2}}&=	
[z^n]\frac{1}{1-2z+z^{r+2}}-[z^{n-r-1}]\frac{1}{1-2z+z^{r+2}}\\
&=\sum_{k=0}^{n+r}U_{k,r+1}-\sum_{k=0}^{n-1}U_{k,r+1}\\
&=\sum_{k=n}^{n+r}U_{k,r+1}.
\end{align*}


\section{Asymptotics}

We refer to the paper~\cite{Knuth78} which might be the first to consider asymptotics for
words of restricted runs. The recent paper~\cite{PrWa12} has many examples of this type. 
Here, we only consider the key steps and refer for error bounds to the cited literature.

One has to study the \emph{dominant} zero of the denominator, denoted by $\rho$, which is
close to $\frac12$ when $r$ gets large (no restriction). From
\begin{equation*}
1-2\rho+\rho^{r+2}=0
\end{equation*}
we infer
\begin{equation*}
\rho=\frac12+\frac12\rho^{r+2}\approx \frac12+\frac1{2^{r+3}}.
\end{equation*}
This procedure is called \emph{bootstrapping}.
We also need the constant $A$ in 
\begin{equation*}
\frac1{1-2z+z^{r+2}}\sim \frac{A}{1-z/\rho}\qquad\text{as $z\to\rho$},
\end{equation*}
which we get by L'Hopital's rule as
\begin{equation*}
A=\frac{-1/\rho}{-2+(r+2)z^{r+1}}\bigg|_{z=\rho}=
\frac{-1/\rho}{-2+(r+2)\rho^{r+1}}=
\frac{1}{2\rho-(r+2)(2\rho-1)}.
\end{equation*}
So we get the following asymptotic formul\ae, valid for $n\to\infty$ and fixed $r$:
\begin{align*}
[z^n]\frac{1-z^{ \lfloor \frac r2\rfloor+1}}{1-2z+z^{r+2}}&\sim
(1-\rho^{ \lfloor \frac r2\rfloor+1})A\rho^{-n},\\
[z^n]\frac{1-z^{ \lfloor \frac {r-1}2\rfloor+1}}{1-2z+z^{r+2}}
&\sim
(1-\rho^{ \lfloor \frac {r-1}2\rfloor+1})A\rho^{-n},\\
[z^n]\frac{1-z^{ r+1}}{1-2z+z^{r+2}}
&\sim
(1-\rho^{r+1})A\rho^{-n}.
\end{align*}


And now we turn to the instance where $r$ is a random variable $X$, and compute, as a showcase,
the expected value, so we answer the question about the average value of the longest 1-run in
palindromes, in the 3 respective models. As mentioned, this was basically done already by Knuth. When $r$ gets large, the constant $A$ may be replaced by 1, terms of the form $\rho^r$
may be dropped, and in $\rho^{-n}$, it is enough to use the approximation
\begin{equation*}
\rho^{-n}\sim 2^n{(1-2^{-r-2})}^n\sim 2^n\exp(-n/2^{r+2}).
\end{equation*}
Furthermore, to get a probability distribution, we have to divide by $2^n$, which is the number of binary words of length $n$. So the probability that the parameter $X$  is $\le r$
is in all 3 instances approximated by
\begin{equation*}
\exp(-n/2^{r+2}).
\end{equation*}
For an expected value, one has to compute
\begin{equation*}
\sum_{r\ge0}\big[1-\exp(-n/2^{r+2})\big].
\end{equation*}
This evaluation can be found in many texts \cite{Knuth78, FlSe09, PrWa12}; it is done with the \emph{Mellin transform}, and the result is
\begin{equation*}
\log_2n+\frac\gamma{\log2}-\frac32-\frac1{\log2}\sum_{k\neq0}\Gamma\Big(
\frac{2k\pi i}{\log2}\Big)e^{-2k\pi i\cdot\log_2n}.
\end{equation*}
Observe that the series in this expression represents a periodic function with small amplitude. 

Asymptotically, thus, palindromes with middle letter 0 resp.\ 1 resp.\ no middle letter all lead to the same result.

\bibliographystyle{plain}

\begin{thebibliography}{1}

\bibitem{FlSe09}
P.~Flajolet and R.~Sedgewick.
\newblock {\em Analytic Combinatorics}.
\newblock Cambridge University Press, Cambridge, 2009.

\bibitem{Knuth78}
D.~E. Knuth.
\newblock The average time for carry propagation.
\newblock {\em Indag. Math.} {\bf 40} (1978), 238--242.

\bibitem{Nyblom13}
M.~A. Nyblom.
\newblock Counting palindromic binary strings without $r$-runs of ones.
\newblock {\em J. Integer Sequences} {\bf 16} (2013), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Nyblom/nyblom13.html}{Article
13.8.7}.

\bibitem{PrWa12}
H.~Prodinger and S.~Wagner.
\newblock Bootstrapping and double-exponential limit laws.
\newblock Submitted.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 05A15.

\noindent \emph{Keywords: } binary string, generating function, $r$-run
of ones, asymptotics.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 29 2013;
revised version received April 6 2014; April 15 2014. 
Published in {\it Journal of Integer Sequences}, April 15 2014.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}