\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 Palindromic Binary Strings \\
\vskip .12in
Without $r$-Runs of Ones
}
\vskip 1cm
\large
M. A. Nyblom \\
School of Mathematics and Geospatial Science\\
RMIT University\\
Melbourne, Victoria 3001\\
Australia\\
\href{mailto:michael.nyblom@rmit.edu.au}{\tt michael.nyblom@rmit.edu.au} \\
\end{center}
\vskip .2 in
\begin{abstract}
A closed-form expression is derived for the enumeration of all
palindromic binary strings of length $n>r$ having no $r$-runs of $1$'s,
in terms of the $r$-Fibonacci sequence. A similar closed-form
expression for the number of zeros contained in all such palindromic
binary strings is derived in terms of the number of zeros contained in
all binary strings having no $r$-runs of $1$'s.
\end{abstract}
\section{Introduction}
Grimaldi \cite{grim0} and Hayes \cite{haye1}
have noted the well-known fact that the number of binary strings of length $n$, in which there are no consecutive $1$'s is given by $F_{n+2}$, where
$F_{n}$ denotes the $n$-th Fibonacci number generated from the difference equation $F_{n}=F_{n-1}+F_{n-2}$, for $n\geq 2$, with $F_{0}=0$ and
$F_{1}=1$. Thus for binary strings of length, say $n=3$, there are exactly $F_{5}=5$ binary strings in which there are no consecutive $1$'s, namely $000,001,010,100$ and $101$. The property of a binary string having no consecutive $1$'s
(or equivalently no consecutive zeros), can easily be generalized to the property that a binary string has no substrings of length $r$
consisting of $r$ consecutive ones, where $r$ is a fixed integer greater than or equal to $2$. We
shall refer to this property in short, by saying that a binary
string has no $r$-runs of $1$'s. Both the author \cite{nylb} and
Bollinger \cite{bollin} showed that the number of such binary strings is given by $U_{n+r}$, where $\{ U_{n}\}$ denotes the well-known $r$-Fibonacci sequence generated by the $r$-th order linear difference equation $U_{n}=\sum_{i=1}^{r}U_{n-i}$, for $n\geq r$, with $U_{0}=U_{1}=\cdots =U_{r-2}=0$ and $U_{r-1}=1$.
In this paper we shall first be concerned with counting the number of
palindromic binary strings, having no $r$-runs of $1$'s. Letting
$P_r (n)$ denote the
number of such binary strings having length $n>r\geq 2$,
we will show that
\begin{equation}
P_{r}(n)=\begin{cases}
\sum_{i=0}^{\lfloor\frac{r-1+(-1)^{r+1}}{2}\rfloor}U_{\frac{n}{2}+r-1-i},
& \text{if $n$ even;} \\
\sum_{i=-1}^{\lfloor\frac{r-2+(-1)^{r}}{2}\rfloor}U_{\frac{n-1}{2}+r-1-i},
& \text{if $n$ odd.} \end{cases}
\label{eq:1}
\end{equation}
where $\{ U_{n}\}$ is the $r$-Fibonacci sequence. Thus for example when $r=2$ and so $U_{n}=F_{n}$, then the number of palindromic binary strings of length, say $n=3$, having no consecutive $1$'s, would be $P_{2}(3)=F_{3}+F_{2}=2+1=3$, namely $000$, $101$ and $010$.
In addition to establishing the closed-form expression for $P_{r}(n)$
in Section~\ref{sectwo}, we shall also address the problem of enumerating the
total number of zeros contained in the $P_{r}(n)$ palindromic strings.
Such a characteristic was studied by Grimaldi et al.~\cite{grim1,grim2}
for both binary and ternary strings, as well as their palindromic
counterparts, and was expressed in terms of Fibonacci and Lucas
numbers. In the case of the palindromic binary strings in question, we
shall approach the problem of enumerating the number of zeros, by first
deriving an $r$-th order non-homogeneous difference equation for the
number of zeros, denoted $Z_{r}(n)$, in all $U_{n+r}$ binary strings
of length $n\geq 1$ having no $r$-runs of $1$'s. By employing a similar
argument used to derive $P_{r}(n)$, we shall then in Section~\ref{secthree}
produce
a closed-form expressions in the style of (\ref{eq:1}) for the number
of zeros contained in all $P_{r}(n)$ palindromic binary strings, in
terms of the characteristic $Z_{r}(\cdot )$ and the $r$-Fibonacci
sequence $U_{n}$.
\section{Main result}
\label{sectwo}
To begin we note that all palindromic binary string of length $n\leq r$ will have no $r$-runs of $1$'s, with the exception of the string $\underbrace{11\cdots 11}_{r \text{ 1's}}$. Thus as the number of palindromic binary strings of length $n$ is $2^{\frac{2n+1+(-1)^{n+1}}{4}}$, we have $P_{r}(n)=2^{\frac{2n+1+(-1)^{n+1}}{4}}$ for $1\leq nr$, we will require the following technical lemma.
\begin{lemma}\label{L1}
Given an integer $r\geq 1$, then $\max\{ s\in\mathbb{Z}:2s+1r$.
\begin{theorem}\label{T1}
The number of palindromic binary strings of length $n>r\geq 2$ having no $r$-runs of $1$'s is given by
\[
P_{r}(n)=\begin{cases}
\sum_{i=0}^{\lfloor\frac{r-1+(-1)^{r+1}}{2}\rfloor}U_{\frac{n}{2}+r-1-i},
& \text{if $n$ even;} \\
\sum_{i=-1}^{\lfloor\frac{r-2+(-1)^{r}}{2}\rfloor}U_{\frac{n-1}{2}+r-1-i}, &
\text{if $n$ odd.} \end{cases}
\]
where $\{ U_{n}\}$ is the $r$-Fibonacci sequence.
\end{theorem}
\begin{proof}
We first note that all palindromic binary strings of an even length $n=2m$, are constructed by concatenating to the left of a binary string with its mirror image of length $m$. Similarly all palindromic binary strings of an odd length $n=2m+1$, are constructed by concatenating to the right and left of a central entry, containing either a $0$ or $1$, a binary string of length $m$ and its mirror image respectively.
\renewcommand{\arraystretch}{0.7}
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|r|r|}
\hline
\,\,\,\,\, Mirror String of Length $m$ & Binary String of Length $m$ \,\,\,\,\, \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\hline
Mirror String of Length $m$ & $0/1$ & Binary String of Length $m$ \\
\hline
\end{tabular}
\caption{Even and odd length palindromic binary strings}
\end{center}
\end{table}
Thus all palindromic binary strings in question are constructed in this manner, using the binary strings having no $r$-runs of $1$'s, provided that a possible resulting central substring consisting entirely of $1$'s does not exceed or reach a length equal to $r$. With this in mind we further observe that for a fixed integer $r\geq 2$, the set of $U_{n+r}$ binary strings of length $n>r$ having no $r$-runs of $1$'s, can be partitioned into $r$ disjoint sets containing those binary strings whose left-hand entries are $0,10,110,\ldots ,\underbrace{11\cdots 1}_{(r-1) \text{ 1's}}\, 0$ respectively. We now examine more closely the construction of the even and odd length palindromic binary strings in question.
\bigskip
\noindent{\bf Case 1: Even Length $n=2m>r$.}
\medskip
In this instance, if the right binary string of length $m$ has a
left-hand entry of $0$, then the remaining binary string of length
$m-1$ cannot contain $r$-runs of $1$'s, and so there must be
$U_{m-1+r}$ such strings in total. Similarly, if the right binary
string of length $m$ has a left-hand entry of $\underbrace{11\cdots
1}_{s \text{ 1's}} \, 0$, where $1\leq s2$, then both the above sets of
binary strings can be used, provided the binary strings having the
left-hand entry of $\underbrace{11\cdots 1}_{s \text{ 1's}}\, 0$ are such that
$2sr$.}
\medskip
Now if the palindromic strings in question of length $n=2m+1$ have a central entry containing a $0$, then any binary string of length $m$ having no $r$-runs of $1$'s can be used to
concatenate to the right of this central entry, and to the left with its mirror image, and so there must be $U_{m+r}$ such strings in total. Alternatively if the central entry contains a $1$, then if the right binary string of length $m$ has a left-hand entry of $0$, then the remaining binary string of length $m-1$ cannot contain $r$-runs of $1$'s, and so there must be $U_{m-1+r}$ such strings in total. Similarly if the right binary string of length $m$ has a left-hand entry of $\underbrace{11\cdots 1}_{s \text{ 1's}}\, 0$, where $1\leq s3$, then the above three sets of binary strings can be used, provided the binary strings having a left-hand entry of $\underbrace{11\cdots 1}_{s \text{ 1's}}\, 0$ are such that $2s+1r$ having no
$r$-runs of $1$'s. To help achieve this end, it will first be necessary to obtain a recurrence relation for the number of zeros contained in all $U_{n+r}$ binary strings having no $r$-runs of $1$'s, of length $n\geq 1$. We first note that the total number of zeros contained in the set of all $2^{n}$ binary strings of length $n\geq 1$, is given by $Z(n)=n2^{n-1}$. Interested readers can consult Nyblom \cite{nylb} for a proof.
\begin{lemma}\label{L2}
For a fixed integer $r\geq 2$, the total number of zeros that occur in the $U_{n+r}$ binary strings of length $n\geq 1$ having no $r$-runs of $1$'s, satisfy the following $r$-th order recurrence relation
\[
Z_{r}(n)=\sum_{i=1}^{r}Z_{r}(n-i) +U_{n+r}\mbox{ ,}
\]
for $n>r$, with the $r$ initial conditions $Z_{r}(n)=n2^{n-1}$, for $n=1,2,\ldots ,r$.
\end{lemma}
\begin{proof}
Recall that the binary strings of length $n>r$ having no $r$-runs of
$1$'s, can be partitioned into $r$ disjoint sets containing those
binary strings whose left-hand entry are $0,10,110,\ldots
,\underbrace{11\cdots 1}_{(r-1) \text{ 1's}}\, 0$
respectively. Now if the binary
strings in question have a left-hand entry of $0$, then the remaining
$U_{n-1+r}$ substrings of length $n-1$ will by definition contribute
$Z_{r}(n-1)$ zeros, making a total contribution of
$Z_{r}(n-1)+U_{n-1+r}$ zeros. Similarly if the binary strings in
question have a left-hand entry of $\underbrace{11\cdots 1}_{i \text{ 1's}}\, 0$,
where $1\leq ir$
\begin{eqnarray*} Z_{r}(n) & = &
Z_{r}(n-1)+U_{n-1+r}+\sum_{i=1}^{r-1}(Z_{r}(n-i-1)+U_{n-i-1+r})\\
& = & \sum_{i=1}^{r}(Z_{r}(n-i) +U_{n-i+r})\\ & = &
\sum_{i=1}^{r}Z_{r}(n-i) +\sum_{i=1}^{r}U_{n-i+r}\\ & = &
\sum_{i=1}^{r}Z_{r}(n-i) +U_{n+r}\mbox{ .}
\end{eqnarray*} Clearly the number of zeros that occur in the binary
strings of length $1\leq n\leq r$ having no $r$-runs of $1$'s, must be
equal to the number of zeros in all binary strings having corresponding
length, consequently $Z_{r}(n)=Z(n)=n2^{n-1}$, for $n=1,2,\ldots ,r$.
\end{proof}
By employing a similar argument used to establish Theorem \ref{T1}, we can now obtain an expression for the number of zeros contained in all palindromic binary strings of length $n>r\geq 2$ having no $r$-runs of $1$'s, in terms of the characteristic $Z_{r}(\cdot )$, and the $r$-Fibonacci sequence $\{ U_{n}\}$.
\begin{theorem}\label{T2}
For a fixed integer $r\geq 2$, the total number of zeros that occur in the $P_{r}(n)$ palindromic binary strings of length $n>r$ having no $r$-runs of $1$'s is
\begin{equation}
\tilde{Z_{r}}(n)=\begin{cases}
2\sum_{i=0}^{\lfloor\frac{r-1+(-1)^{r+1}}{2}\rfloor}(U_{\frac{n}{2}+r-1-i}+Z_{r}(\frac{n}{2}-1-i)), & \text{if $n$ even;} \\
U_{\frac{n-1}{2}+r}+2Z_{r}(\frac{n-1}{2})+2\sum_{i=0}^{\lfloor\frac{r-2+(-1)^{r}}{2}\rfloor}(U_{\frac{n-1}{2}+r-1-i}+Z_{r}(\frac{n-1}{2}-1-i)), &
\text{if $n$ odd.} \end{cases}
\label{eq:4}
\end{equation}
\end{theorem}
\begin{proof}
In what follows recall the construction of the $P_{r}(n)$ palindromic binary strings of length $n>r$ outlined in the proof of Theorem~\ref{T1}. Now in the case of an even length $n=2m$ when $r=2$, then the $U_{m-1+r}=U_{m+1}$ right substrings contained in
\begin{table}[htbp]
\begin{tabular}{|r|r|r|r|}
\hline
\quad\quad\,\,\,\,\,\,\,\,\,\,\,\, Mirror String of Length $m-1$\,\,\,\,\,\, & $0$ & $0$ & \,\,\,\,\,\,String of Length $m-1$\,\,\,\,\,\,\,\,\,\,\,\,\quad\quad \\
\hline
\end{tabular}
\end{table}
\noindent will by definition contribute $Z_{r}(m-1)=Z_{2}(m-1)$ zeros, together with the additional $U_{m+1}$ left-hand zeros bringing
a total contribution, with the mirror string, of $2(U_{m+1}+Z_{2}(m-1))$ zeros, and so $\tilde{Z_{2}}(2m)=2(U_{m+1}+Z_{2}(m-1))$. However when $r>2$, then the above string, together with the $U_{m-s-1+r}$ additional right substrings contained in
\begin{table}[htbp]
\begin{tabular}{|r|r|r|r|}
\hline
Mirror String of Length $m-s-1$ & $01\cdots 11 $ & $11\cdots 10$ & String of Length $m-s-1$ \\
\hline
\end{tabular}
\end{table}
\noindent for, $1\leq s\leq \lfloor\frac{r-1+(-1)^{r+1}}{2}\rfloor$, will each contribute $Z_{r}(m-s-1)$ zeros, together with the additional $U_{m-s-1+r}$ zero from each substring $\underbrace{11\cdots 1}_{s \text{ 1's}}\, 0$, bringing a total contribution, with the mirror string, of
\begin{eqnarray}
\tilde{Z_{r}}(2m) & = & 2(U_{m-1+r}+Z_{r}(m-1))+2\sum_{s=1}^{\lfloor\frac{r-1+(-1)^{r+1}}{2}\rfloor}(U_{m-s-1+r}+Z_{r}(m-s-1))\nonumber\\
& = & 2\sum_{i=0}^{\lfloor\frac{r-1+(-1)^{r+1}}{2}\rfloor}(U_{\frac{n}{2}-i-1+r}+Z_{r}(\frac{n}{2}-i-1))\label{eq:5}
\end{eqnarray}
zeros, noting here that the right-hand side of (\ref{eq:5}) agrees with $\tilde{Z_{2}}(2m)$, when $r=2$.
In the case of an odd length $n=2m+1$ when $r=2$ and $r=3$, then the $U_{m+r}$ and $U_{m-1+r}$ right substring contained in
\begin{table}[htbp]
\begin{tabular}{|r|r|r|}
\hline
\quad\quad\quad\quad\quad\quad Mirror String of Length $m$ & $0$ & Binary String of Length $m$ \quad\quad\quad\quad\quad\quad\quad\\
\hline
\end{tabular}\\
\begin{tabular}{|r|r|r|r|r|r|}
\hline
\quad\quad\,\, Mirror String of Length $m-1$ & 0 & $1$ & 0 & Binary String of Length $m-1$ \quad\quad\quad\quad\\
\hline
\end{tabular}
\end{table}
\noindent for
respectively, will each contribute $Z_{r}(m)$ and $Z_{r}(m-1)$ zeros. In the first palindromic string, by adding the $U_{m+r}$ centered zeros brings a total contribution, with the mirror substring, of $U_{m+r}+2Z_{r}(m)$ zeros. However in the second palindromic string, by adding the $U_{m-1+r}$ left-hand zeros brings a total contribution, with the mirror substring, of $2(U_{m-1+r}+Z_{r}(m-1))$ zeros. Thus the total number of zeros contained in the first two palindromic strings is
\[
(U_{m+r}+2Z_{r}(m))+2(U_{m-1+r}+Z_{r}(m-1))\mbox{ ,}
\]
and so $\tilde{Z_{2}}(2m+1)=(U_{m+2}+2Z_{2}(m))+2(U_{m+1}+Z_{2}(m-1))$ and $\tilde{Z_{3}}(2m+1)=(U_{m+3}+2Z_{3}(m))+2(U_{m+2}+Z_{3}(m-1))$. Now when $r>3$, then the above two strings together with the $U_{m-s-1+r}$ additional right substrings contained in
\begin{table}[htbp]
\begin{tabular}{|r|r|r|r|r|}
\hline
Mirror String of Length $m-s-1$ & $01\cdots 11 $ & 1 & $11\cdots 10$ & String of Length $m-s-1$ \\
\hline
\end{tabular}
\end{table}
\noindent for $1\leq s\leq \lfloor\frac{r-2+(-1)^{r}}{2}\rfloor$, will each contribute $Z_{r}(m-s-1)$ zeros, together with the additional $U_{m-s-1+r}$ zeros from the substring
$\underbrace{11\cdots 1}_{s \text{ 1's}}\, 0$, bringing a total contribution, with the mirror string, of
\begin{eqnarray}
\tilde{Z_{r}}(2m+1) & = & U_{m+r} +2Z_{r}(m)+2(U_{m-1+r}+Z_{r}(m-1)) \nonumber \\
& + & 2\sum_{s=1}^{\lfloor\frac{r-2+(-1)^{r}}{2}\rfloor}(U_{m-s-1+r}+Z_{r}(m-s-1))\nonumber\\
& = & U_{m+r} +2Z_{r}(m)+2\sum_{i=0}^{\lfloor\frac{r-2+(-1)^{r}}{2}\rfloor}(U_{m+r-1-i}+Z_{r}(m-1-i))\label{eq:6}
\end{eqnarray}
zeros, noting here that the right-hand side of (\ref{eq:6}) agrees with $\tilde{Z_{2}}(2m+1)$ and $\tilde{Z_{3}}(2m+1)$, when $r=2$ and $r=3$ respectively.
\end{proof}
To illustrate both Theorem~\ref{T1} and Theorem~\ref{T2}, suppose we wish to calculate the total number of Palindromic binary strings of length $n=5$ having no consecutive $1$'s, and the total number of zeros contained in these strings. In this case when we set $r=2$ and $n=5$ into (\ref{eq:1}) and (\ref{eq:4}), noting here that the $2$-Fibonacci sequence $U_{n}=F_{n}$, one finds that $P_{2}(5)=F_{4}+F_{3}=3+2=5$ while $\tilde{Z_{2}}(5)=F_{4}+2Z_{2}(2)+2(F_{3}+Z_{1}))=3+(2)(4)+2(2+1)=17$, which is in agreement with palindromic strings displayed below.
\begin{table}[htbp]
\begin{center}
\hspace{2cm}
\begin{tabular}{|r r r r r|}
\hline
0 & 0 & 0 & 0 & 0 \\
\hline
0 & 1 & 0 & 1 & 0 \\
\hline
1 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 0 & 0 \\
\hline
1 & 0 & 1 & 0 & 1 \\
\hline
\end{tabular}
\caption{The 5 palindromic binary strings of length 5 having no $2$-runs of $1$'s}
\end{center}
\end{table}
\begin{thebibliography}{9}
\bibitem{bollin} R. C. Bollinger, Fibonacci $k$-sequence, Pascal-$t$
triangles, and $k$-in-a-row problems, {\em Fibonacci Quart.}
{\bf 22} (1984), 146--151.
\bibitem{grim0} R. P. Grimaldi, {\em Discrete and Combinatorial
Mathematics}, 2nd edition, Addison-Wesley, 1989.
\bibitem{grim1} R. P. Grimaldi and S. Heubach, Binary strings without odd
runs of zeros, {\em Ars Combinatoria} {\bf 75} (2005), 241--255.
\bibitem{grim2} R. P. Grimaldi, Ternary strings with no consecutive
$1$'s, {\em Ars Combinatoria} {\bf 89} (2008), 321--343.
\bibitem{haye1} B. Hayes, D. S. Pearson, and M. Andreoli, Solutions 10196,
{\em Amer. Math. Monthly} {\bf 101} (1984), 363--365.
\bibitem{nylb} M. A. Nyblom, Enumerating binary strings without
$r$-runs of ones, {\em Int. Math. Forum}, {\bf 7} (2012), 1865--1876.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B39; Secondary 05A15.
\noindent \emph{Keywords: } binary strings,
$r$-Fibonacci sequence, $r$-run of ones.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A001590} and
\seqnum{A053602}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 7 2013;
revised version received September 13 2013.
Published in {\it Journal of Integer Sequences}, October 13 2013.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}