\documentclass{article}

\begin{document}
\bibliographystyle{plain}
\title{The Number of Binary Cube-Free Words of length up to  47
and Their Numerical Analysis}

\author{Anne E. Edlin}

\maketitle

\begin{abstract}
An analog of the work of Noonan and Zeilberger on square-free ternary words is 
given for the 
case of cube-free binary words.  
As in their work, the Goulden-Jackson Cluster Method is 
used to derive a rigorous upper bound, as well as a non-rigorous
estimate, for the limit of the $n^{th}$ roots of the terms.
The Maple implementation of this work is available from this 
paper's website {\bf
http://www.math.temple.edu/$\sim$anne/cubefree.html}. 
\end{abstract}

\subsection*{Preface}
In order to define a cube-free word we must first define a factor of a word.  
Given a word $w=w_1w_2 \ldots w_n$, a {\it factor} of $w$ is any subword of 
the form $w_kw_{k+1} \ldots  w_{k+j}$ where  $1 \leq k \leq n$ and 
$0 \leq j \leq n-1$.
A word is {\it cube-free} if it contains no factors of the form $xxx$, where 
$x$ is any word. 
My Maple package Cubefree (available from {\bf 
http://www.math.temple.edu/$\sim$anne/cubefree.html}) can be used to derive 
cube-free words on any given alphabet up to the required length.  The number of 
binary cube-free words of length at most n for $0 \leq n \leq 47$ are given 
below.

\subsection*{The Sequence of Binary Cube-Free Words of length up to 47}
1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716,
2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664,
    158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868,
    3226896, 4703372, 6855388, 9992596, 14565048, 21229606, 30943516,
    45102942, 65741224, 95822908, 139669094.

\subsection*{The `Connective Constant'}

Let $a_n$ denote the number of cube-free binary words of length $n$.
The values of $a_n$ for $n=0, \dots, 47$ are given above.
It is well-known, and easy to see, that
$\mu := \lim_{n \rightarrow \infty} a_n^{1/n}$ exists.
Using the `memory-45' analog (i.e. the corresponding sequence
that enumerates words that avoid cubes $x^3$, with $length(x) \leq 15$),
that was generated using the Maple package, up to word-length
$300$, we find the rigorous upper bound 
$\mu <1.457579200596766$.

Using Zinn's method, we also found that, assuming that
$a_n \sim n^{\theta} \mu^n$, then
$\mu \approx 1.457$, and $\theta \approx 0$. Hence it is
reasonable to conjecture that $a_n \sim \mu^n$, where
$\mu := \lim_{n \rightarrow \infty} a_n^{1/n} \approx 1.457$.

\begin{thebibliography}{1}

\bibitem{noonan}
John Noonan and Doron Zeilberger, \emph{The Goulden-Jackson Cluster Method: 
Extensions, Applications and Implementations}, preprint.  Available from the 
paper's website {\bf http://www.math.temple.edu/$\sim$zeilberg/gj.html}.

\end{thebibliography}

\end{document}