\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