\documentclass[12pt,reqno]{article}

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

\newcommand{\pat}{\mathfrak{p} }
\newcommand{\fine}{$\hfill \square$}
\newcommand{\barx}{\bar{x}}

\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}
\usepackage{epsfig}

\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 Binary Words Avoiding Alternating 
\\
\vskip .1in
Patterns 
}
\vskip 1cm
\large
Stefano Bilotta, Elisabetta Grazzini,\footnote{ Corresponding author.} and Elisa Pergola\\
Dipartimento di Sistemi e Informatica \\
Universit\`a di Firenze\\
Viale G. B. Morgagni 65 \\
50134 Firenze \\
Italy\\
\href{mailto:egrazzini@unifi.it}{\tt egrazzini@unifi.it}
\end{center}

\vskip .2 in

\begin{abstract}
Let $F^{[\pat]}$ denote the set of binary words, with no more 0's
than 1's, that do not contain the pattern $\pat =
(10)^j1$ as a factor for any fixed $j \geq 1$. We give the generating
function for the integer sequence enumerating, according to the
number of 1's, the words in $F^{[\pat]}$.
\end{abstract}


\section{Introduction}
In this paper we consider the set $F \subset \{0,1\}^*$ of binary
words $\omega$ such that $|\omega|_0 \leq |\omega|_1$, for any
$\omega \in F$, where
$|\omega|_0$ and $|\omega|_1$ denote the
number of 0's and 1's in the word $\omega$, respectively. We study
the enumeration of the subset $F^{[\pat]} \subset F$ of binary
words excluding a given pattern $\pat = p_0 \cdots p_{\ell-1} \in
\{0,1\}^\ell$, i.e., a word $\omega$ is contained in
$F^{[\pat]}$ if and only if
there is no sequence of consecutive indices $i, i+1,
\ldots,i+\ell-1$ such that $\omega_i\omega_{i+1} \cdots
\omega_{i+\ell-1} = p_0 p_1\cdots p_{\ell-1}$.

If we consider the set of binary words without any restriction,
the defined language is regular, and it can be enumerated on the
basis of the number of bits $1$ and $0$ by using classical results
(see, e.g., \cite{GO80,GO81,SF95}). With the additional
restriction that the words 
have no more 0's than 1's, the language
$F^{[\mathfrak{p}]}$ is no longer regular,
and it becomes more
difficult to deal with. For example, in order to generate the
language $F^{[\mathfrak{p}]}$ for each forbidden pattern $\pat$ an
``ad hoc'' grammar (from which the generating function can be
obtained) must be defined. Consequently, for each pattern $\pat$ a
different generating function enumerating the words in
$F^{[\mathfrak{p}]}$ must be computed. Our aim is to determine a
constructive algorithm suggesting a more unified approach, which
makes it possible to generate all binary words in the class
$F^{[\mathfrak{p}]}$. Furthermore, this approach
allows us to obtain a
generating function for the enumeration of the class, according to
the number of 1's, which applies to each forbidden pattern~$\pat$.

In this paper we compute an explicit formula for the generating
function which counts the words of $F^{[\pat]}$ according to the
number of 1's where $\pat = (10)^j1$, for any fixed~$j \geq 1$.

In order to obtain the enumeration of the class
$F^{[\mathfrak{p}]}$ according to the number of 1's, we use a
standard method, called the ECO-method, for the enumeration of
combinatorial objects which admit recursive descriptions in terms
of generating trees (see, e.g., \cite{genfun}). So, we first
construct all binary words belonging to $F$ and avoiding the
pattern $\pat = (10)^j1$, for any fixed $j \geq 1$. Then, we
obtain the succession rule \cite{BDPP99,CORTE00,FPPR03},
describing the generating algorithm, from which we can compute the
generating function enumerating the words in $F^{[\mathfrak{p}]}$.


We \cite{BMPP11} introduced an algorithm for the construction of
all binary words in $F$ having a fixed number of 1's and excluding
those containing the forbidden pattern $1^{j+1}0^j$, for any fixed
$j~\geq~1$. That algorithm first generates all the words in $F$, and
then it eliminates those containing the forbidden pattern.
Basically, the construction marks in an appropriate way the
forbidden patterns in the words and generates $2^C$ copies of each
word having $C$ forbidden patterns such that the $2^{C-1}$
instances containing an odd number of marked forbidden pattern are
annihilated by the other $2^{C-1}$ instances containing an even
number of marked forbidden patterns. For example, the words
$00110\overline{110}$ and $00\overline{110}110$, containing two
copies of the forbidden pattern $\pat=110$, (the marked forbidden
patterns are over-lined) are eliminated by the words $00110110$
and $00\overline{110}\overline{110}$, respectively.

This is possible since no prefix of $\pat=1^{j+1}0^j$ is also a
suffix of $\pat$, that is the forbidden patterns do not overlap
and so they are uniquely identified inside the words.

However, the algorithm in \cite{BMPP11} cannot be used to generate
the words in $F^{[\mathfrak{p}]}$ when $\pat = (10)^j1$ since now the
forbidden patterns may overlap inside the words. For example, in
$\omega = 110101010$ there are two overlapping copies of the
forbidden pattern $\pat = (10)^21$. So, we propose a new algorithm
that generates (all and) only the words in $F$ avoiding the
forbidden pattern $\pat = (10)^j1$, for any fixed~$j \geq 1$.

The paper is organized as follows. In Section~\ref{sec:basic} we
give some basic definitions and notation. In particular, we recall
how every binary word can be represented as a path on the
Cartesian plane.

In Section~\ref{sec:algo} we give a construction, according to the
number of 1's, for the set of binary words in $F$ excluding the
pattern $\pat = (10)^j1$, for any fixed $j \geq 1$. The generating
function enumerating such words according to the number of 1's is
given in Section~\ref{sec:enum}.

\section{Basic definitions and notation}\label{sec:basic} We begin with some definitions.
Recall that $F \subset \{0,1\}^*$ is the set of binary  words
$\omega$ such that $|\omega|_0 \leq |\omega|_1$, for any $\omega
\in F$, where  $|\omega|_0$ and $|\omega|_1$ denote the number
of 0's and 1's in the word $\omega$, respectively.

Given $|\omega| = |\omega|_0 + |\omega|_1$ the \emph{length} of
$\omega \in F$, we let $\omega^h$,  ($h
>0$) denote
the word with length $h \cdot |\omega|$ obtained by linking $\omega$ to itself $h$
times, that is, $\omega^h = \underbrace{\omega\,\omega \cdots
\omega}_{h}$ and
 $\omega^0 = \varepsilon$, $\varepsilon$ being the empty word.

Each word $\omega \in F$ can be naturally represented as a path on
the Cartesian plane by associating a \emph{rise} (or \emph{up})
\emph{step}, defined by (1,1) and indicated by $x$, with each bit
1 in $\omega$ and a \emph{fall} (or \emph{down}) \emph{step},
defined by (1,-1) and indicated by $\barx$, with each bit 0 in
$\omega$. For example, the word $\omega~=~11011010010000101111$ is
represented by the path $\gamma~=~xx\barx xx\barx x\barx\barx
x\barx\barx\barx\barx x\barx xxxx$ (see Figure~\ref{fig:path}). An
\emph{up-down} step is the sequence $x\barx$.

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig_path.eps, width =1.6in, clip=}
\caption{\small{The path representing  $\omega
=11011010010000101111$}} \label{fig:path}
\end{center}
\end{figure}

Hereafter we refer interchangeably to words or their graphical
representation on the Cartesian plane, i.e., paths. So we let
$F$ 
denote both the set of patterns $\pat$ avoiding binary words, and
the set of corresponding paths.

\noindent In the rest of this paper, a path is
\begin{itemize}
\item[-] \emph{primitive}, if it begins and ends at ordinate 0 and
remains strictly above the $x$-axis;

\item[-] \emph{positive}, if it begins
 at ordinate 0 and remains above or on the $x$-axis;
\item[-] \emph{negative}, if it begins and ends at ordinate 0 and
remains below or on the $x$-axis (remark that a negative path in
$F^{[\pat]}$ necessarily ends at ordinate 0);

\item[-] \emph{strongly negative}, if it begins and ends at
ordinate -1 and remains below or on the line $y=-1$;

\item[-]  \emph{underground}, if it ends with a negative suffix.
\end{itemize}

The \emph{complement} of a path $\varphi$ is
 the path $\varphi^c$ obtained from $\varphi$ by switching rise and fall
 steps.


\section{A construction for the set
$F^{[\pat]}$}\label{sec:algo}


In this section we show the constructive algorithm to generate the
set $F^{[\pat]}$, $\pat = (x\barx)^jx= (10)^j1$ for any fixed $j
\geq 1$, according to the number of rise steps, or equivalently to
the number of 1's.

The proof that the construction given in this section allows to
generate all the words in $F^{[\pat]}$ with $n$ 1's for any fixed
forbidden pattern $\pat = (x\barx)^jx= (10)^j1$, $j \geq 1$, is
given in \cite{BGPP12}.

Given a path $\omega \in F^{[\pat]}$ with $n$ rise steps, we
generate a given number of paths in $F^{[\pat]}$ with $n+h$ rise
steps, $1 \leq h \leq j$, by means of constructive rules. The
number and the shape of the generated paths depend on the ordinate
$k$ of the endpoint of $\omega$ and on its suffix. With regard to
$k$, we can point out three cases: $k=0$, $k=1$ and $k \geq 2$,
while as for the suffix we consider whether it is equal to
$(x\barx)^j$ or not. When $k=0$, we must pay attention also to the
case in which $\omega$ is an underground path ending with the
pattern $(x\barx)^{j-1}x$.

As we will show further on, for each $\omega \in F^{[\pat]}$ such
that $k=0$ or $k \geq 2$, the generating algorithm produces two or
more positive paths and one underground path with $n+h$ rise
steps, $1 \leq h \leq j$, while, when $k=1$, it produces only one
positive path with $n+h$ rise steps.

The generating algorithm of the class  $F^{[\pat]}$ with $\pat =
(x\barx)^jx = (10)^j1$, for any fixed $j \geq 1$, is described in
the following sections. The constructive rules related to the
special cases in which the suffix of $\omega$ is $(x\barx)^j$ or
$(x\barx)^{j-1}x$ are described in Sections
\ref{sec:positivesuffix} and \ref{sec:negativesuffix},
respectively. In Section \ref{sec:simplecase} we examine all the
other simple cases.

\noindent The starting point of the algorithm is the empty word
$\varepsilon$. $\omega_{|k}$ denotes a path with endpoint at
ordinate $k$.


\subsection{Simple cases}\label{sec:simplecase} In this section we
describe the constructive rules to be applied when the suffix of
$\omega$ is neither $(x\barx)^j$ nor $(x\barx)^{j-1}x$. We point
out three cases for the ordinate $k$ of the endpoint of $\omega$:
$k=0$, $k=1$ and $k \geq 2$.
\begin{description}


\item [$k=0$.] A path $\omega \in F^{[\pat]}$, with $n$ rise steps
and such that its endpoint has ordinate 0, generates, for any $h$,
$1 \leq h \leq j$, three paths with $n+h$ rise steps: a path
ending at ordinate 1 by adding to $\omega$ a rise step and a
sequence of $h-1$ up-down steps; a path ending at ordinate 0 by
adding to $\omega$ a rise step, a sequence of $h-1$ up-down steps
and a fall step, and an underground path obtained by the one
generated in the previous step and mirroring on $x$-axis its
rightmost primitive suffix. Figure~\ref{fig:zero1} shows the above
described operations; the number above the right arrow corresponds
to the value of $h$. Both in this and in the following figures we
consider $j=4$, that is, $\pat=(x\barx)^4x = (10)^41$.
\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig0_1.eps, width =3.5in, clip=} \caption{\small{The
paths generated by $\omega_{|0}$}} \label{fig:zero1}
\end{center}
\end{figure}

Therefore,
\begin{equation}\label{alfa}
\omega_{|0} \Rightarrow
\begin{cases}
\omega_{|0}x\,(x\barx)^{h-1};\\
\omega_{|0}x(x\barx)^{h-1}\barx;\\
\omega_{|0}\barx (\barx x)^{h-1}x.
\end{cases}
\end{equation}


\item [$k=1$.] A path $\omega \in F^{[\pat]}$, with $n$ rise steps
and such that its endpoint has ordinate 1, generates, for any $h$,
$1 \leq h \leq j$, a path with $n+h$ rise steps with endpoint at
ordinate 2 obtained by adding to $\omega$ a rise step and a
sequence of $h-1$ up-down steps (see Figure~\ref{fig:uno1}).

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig1_1.eps, width =2.3in, clip=} \caption{\small{The
paths generated by $\omega_{|1}$}} \label{fig:uno1}
\end{center}
\end{figure}

Therefore,
\begin{equation}\label{beta}
\omega_{|1}\Rightarrow \omega_{|1}x(x\barx)^{h-1}.
\end{equation}

\item [$k \geq 2$.] A path $\omega \in F^{[\pat]}$, with $n$ rise
steps and such that its endpoint has ordinate $k$, $k \geq 2$,
generates, for any $h$, $1 \leq h \leq j$, $k+2$ paths with $n+h$
rise steps: a path ending at ordinate $(k+1)$ by adding to
$\omega$ a rise step and a sequence of $h-1$ up-down steps; $k-1$
paths ending at ordinate $(k-1), (k-2), \ldots, (1)$,
respectively,  by adding to $\omega$ a rise step, a sequence of
$m$, $2 \leq m \leq k$, fall steps and a sequence of $h-1$ up-down
steps; a path ending at ordinate 0 by adding to $\omega$ a rise
step, a sequence of $k$ fall steps, a sequence of $h-1$ up-down
steps and a fall step, and an underground path which will be
described in Section~\ref{sec:under}. Figure~\ref{fig:due1} shows
the above described operations.

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig2_1.eps, width =5.3in, clip=} \caption{\small{The
paths generated by $\omega_{|k}, k\geq 2$}} \label{fig:due1}
\end{center}
\end{figure}

Therefore,

\begin{equation}\label{gamma}
\omega_{|k} \Rightarrow
\begin{cases}
\omega_{|k}x(x\barx)^{h-1};&\\
\omega_{|k}x(\barx)^m(x\barx)^{h-1},& \text{$2 \leq m \leq k$;}\\
\omega_{|k}x(\barx)^k(x\barx)^{h-1}\barx.&
\end{cases}
\end{equation}
\end{description}

At this point it is clear that:
\begin{enumerate}
\item when the path $\omega$ ends with the suffix $(x\barx)^j$ the
paths obtained by means of the constructions (\ref{alfa}),
(\ref{beta}) and (\ref{gamma}) contain the forbidden pattern
$\pat=(x\barx)^jx$. So, we will act as described in
Section~\ref{sec:positivesuffix};

\item when $\omega$ is an underground path ending with the pattern
$(x\barx)^{j-1}x$, some  paths generated by means of the above
constructions might contain the forbidden pattern
$\pat=(x\barx)^jx$. So, we will follow the procedure described in
Section~\ref{sec:negativesuffix}.

\end{enumerate}

\subsection{Paths ending with
$(x\barx)^j$}\label{sec:positivesuffix} Even when the path
$\omega$ ends with the suffix  $(x\barx)^j$, the number and the
shape of the generated paths depend on the ordinate $k$ of the
endpoint of $\omega$.  Let $\varrho=(x\barx)^j$ be the suffix of
$\omega$.
\begin{description}

\item [$k=0$.] A path $\omega \in F^{[\pat]}$, with $n$ rise steps
and such that its endpoint has ordinate~0, generates, for any $h$,
$1\leq h \leq j$, three paths with $n+h$ rise steps (see
Figure~\ref{fig:zero2}): a path ending at ordinate~1, by inserting
a sequence of $h-1$ up-down steps and a rise step on the left of
$\varrho$; a path ending at ordinate~0, by inserting a sequence of
$h-1$ up-down steps and a rise step on the left of $\varrho$ and
adding a fall step at the end of $\omega$, and an underground
path, obtained by mirroring on $x$-axis the rightmost primitive
suffix of the path generated in the previous step.

Therefore,

\begin{equation}\label{alfa1}
\omega_{|0}\varrho \Rightarrow
\begin{cases}
\omega_{|0}(x\barx)^{h-1}x\varrho;\\
\omega_{|0}(x\barx)^{h-1}x\varrho\,\barx;\\
\omega_{|0}(x\barx)^{h-1}\barx \barx (x\barx)^{j-1}xx.\\
\end{cases}
\end{equation}

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig0_2.eps, width =5.3in, clip=} \caption{\small{The
paths generated by $\omega_{|0}(x\barx)^j$}} \label{fig:zero2}
\end{center}
\end{figure}


\item [$k=1$.] A path $\omega \in F^{[\pat]}$, with $n$ rise steps
and such that its endpoint has ordinate 1, generates, for any $h$,
$1 \leq h \leq j$, a path with $n+h$ rise steps with endpoint at
ordinate~2, obtained by inserting a sequence of $h-1$ up-down
steps and a rise step on the left of the suffix $\varrho$ (see
Figure~\ref{fig:uno2}). Therefore,

\begin{equation}\label{beta1}
\omega_{|1}\varrho \Rightarrow
\omega_{|1}(x\barx)^{h-1}x\,\varrho.
\end{equation}

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig1_2.eps, width =2.8in, clip=} \caption{\small{The
paths generated by $\omega_{|1}(x\barx)^j$}} \label{fig:uno2}
\end{center}
\end{figure}

\item [$k \geq 2$.] A path $\omega \in F^{[\pat]}$, with $n$ rise
steps and such that its endpoint has ordinate $k$, $k \geq 2$,
generates, for any $h$, $1 \leq h \leq j$, $k+2$ paths with $n+h$
rise steps (see Figure~\ref{fig:due2}): a path  ending at
ordinate~$(k+1)$, by inserting a sequence of $h-1$ up-down steps
and a rise step on the left of the suffix $\varrho$; $k-1$ paths
ending at ordinate $(k-1), (k-2), \ldots, (1)$, respectively, by
inserting a sequence of $h-1$ up-down steps, a rise step and a
sequence of $m$, $2 \leq m \leq k$, fall steps on the left of
$\varrho$; a path ending at ordinate~0, by first inserting a
sequence of $h-1$ up-down steps, a rise step and a sequence of $k$
fall steps on the left of $\varrho$, and then adding a fall step
at the end of $\omega$, and an underground path which will be
described in Section~\ref{sec:under}.

Therefore,

\begin{equation}\label{gamma1}
\omega_{|k}\varrho \Rightarrow
\begin{cases}
\omega_{|k}(x\barx)^{h-1}x\varrho;\\
\omega_{|k}(x\barx)^{h-1}x(\barx)^m\,\varrho, &\text{$2\leq m \leq k$};\\
\omega_{|k}(x\barx)^{h-1}x\,(\barx)^k\,\varrho\,\barx.
\end{cases}
\end{equation}


\begin{figure}[!htb]
\begin{center}
\epsfig{file=Fig2_2.eps, width =6.3in, clip=}\caption{\small{The
paths generated by $\omega_{|k}(x\barx)^j, k\geq 2$}}
\label{fig:due2}
\end{center}
\end{figure}

\end{description}


\subsection{Paths ending with
$(x\barx)^{j-1}x$}\label{sec:negativesuffix} The paths $\omega \in
F^{[\pat]}$ ending on the $x$-axis with the sequence
$(x\barx)^{j-1}x$ have the following shape
$$\omega_{|0} =\mu\,\barx \,\eta\,x\,(\barx x)^{j-1}$$
where $\mu$ is a path ending on the $x$-axis and $\eta$ is either
the empty path $\varepsilon$ or a strongly negative path.

The constructions applied to paths ending at ordinate 0 described
in (\ref{alfa}) (see Figure~\ref{fig:zero1}) can be used even for
the paths ending with the sequence $(x\barx)^{j-1}x$, when $h \geq
2$, or to generate the paths ending at ordinate 1 or on the
$x$-axis with a positive suffix, when $h=1$. Nevertheless, when
$h=1$, by applying the construction, we obtain an underground path
which contains the forbidden pattern $\pat= (x\barx)^jx$.

Therefore if the path ends with the sequence $(x\barx)^{j-1}x$ and
$h=1$, in order to generate the underground path we proceed as
follows. Two cases must be taken into consideration.

\begin{description}

\item[1)] $\mu$ \textbf{does not end with a peak }$x\barx$. \\The
underground path is obtained by adding the path $\barx x$ to
$\omega_{|0}$, mirroring on $x$-axis the rightmost suffix $(\barx
x)^j$ of $\omega_{|0}\barx x$ and shifting the sequence
$(x\barx)^j$ between $\mu$ and the sub-path $\barx \,\eta \,x$.
Therefore, the path $\omega_{|0} =\mu\,\barx \,\eta\,x\,(\barx
x)^{j-1}$ generates the underground path $\mu\,(x\barx)^j\,\barx
\,\eta \,x$ (see Figure~\ref{fig:casoa}). Note that this
construction applies to $\omega$ even if $\mu = \varepsilon$.

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Caso_abis.eps, width =3.3in,
clip=}\caption{\small{The underground path generated by
$\omega_{|0}$ in the case 1)}}\label{fig:casoa}
\end{center}
\end{figure}


\item[2)] $\mu$ \textbf{ends with a peak} $x\barx$. \\When the
path $\mu$ ends with a peak $x\barx$, that is, $\mu= \mu'x\barx$,
the insertion of the sequence $(x\barx)^j$ between $\mu$ and the
sequence $\barx \, \eta \,x$ produces the forbidden pattern $\pat
= (x\barx)^jx$. Let us consider the following subcases: $\eta \neq
\varepsilon$ and $\eta = \varepsilon$.
\begin{description}
\item [2.1)] $\eta  \neq \varepsilon$. \\The underground path is
obtained by shifting the rightmost peak $x\barx$ of $\mu$ to the
right of the sub-path $\barx \,\eta \,x$, mirroring on $x$-axis
the sequence $(\barx x)^{j-1}$ and adding to such path the steps
$\barx\, x$. So, when $h=1$, the underground path with negative
suffix generated by $\omega_{|0} =\mu'\,x\,\barx \, \barx \,\eta
\,x\,(\barx x)^{j-1}$ is $\mu'\, \barx \,\eta \,x\,(x\barx)^{j}\,
\barx \, x$ (see Figure~\ref{fig:casob1}).

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Caso_b1bis.eps, width =3.4in, clip=}
\caption{\small{The underground path generated by $\omega_{|0}$ in
the case 2.1)}} \label{fig:casob1}
\end{center}
\end{figure}

\item [2.2)] $\eta  = \varepsilon$. \\In this case, the
underground path obtained by means of the construction described
in~2.1) is $\omega' = \mu'\, \barx \,x\,(x\barx)^{j}\, \barx \, x$
and it contains the forbidden pattern $\pat = (x\barx)^jx$ if
$\mu'$ ends with the sequence $(\barx x)^j$ or with the sequence
$\barx \, \eta' \, x\,(\barx x)^{j-1}$, where $\eta'$ is a
non-empty strongly negative path. Let us take the longest suffix
of $\omega_{|0} =\mu'\, x\,\barx \,(\barx x)^{j}$ into account so
that $\omega_{|0} = \varphi \, \nu_1 \,  \nu_2 \ldots \nu_k$,
where
$$\begin{cases}
\nu_1=\barx \, \lambda \, x \, (\barx x)^{j-1} \, x \, \barx;\\
\nu_i = (\barx x)^j \, x\, \barx, & \text{$1 < i < k$};\\
\nu_k=(\barx x)^{j},
\end{cases}$$
and $\lambda$ is the empty path or is a strongly negative path.
Every sequence $\nu_i$, $1 \leq i \leq k$, will be changed into
$\bar{\nu_i}$ in the following way.
\begin{description}

\item[2.2.1)] If $\varphi$ is a path that does not end with a peak
$x\,\barx$, then

$$\begin{cases}
\bar{\nu}_1= (x\barx)^j\,\barx \, \lambda \,x;\\
\bar{\nu}_i=(x \barx)^j\, \barx \, x, & \text{$1 < i < k$};\\
\bar{\nu}_k=(x\barx)^j\,\barx \,x.
\end{cases}$$

The underground path generated by $\omega_{|0}$ is
$\varphi\,\bar{\nu}_1 \ldots \bar{\nu}_k$ (see
Figure~\ref{fig:casob2i}).

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Caso_2bi.eps, width =3.7in, clip=}
\caption{\small{The underground paths generated by $\omega_{|0}$
in the case 2.2.1)}} \label{fig:casob2i}
\end{center}
\end{figure}

\item[2.2.2)] If $\varphi$ ends with a peak $x\barx$, that is,
$\varphi=\varphi'\,x\barx$, then

$$\begin{cases}
\bar{\nu}_1= \barx \, \lambda \,x(x\barx)^j\, \barx \,x;  \\
\bar{\nu}_i=(x \barx)^j\, \barx \, x, &\text{$1 < i < k$};\\
\bar{\nu}_k=(x\barx)^j\,\barx \,x.
\end{cases}$$
The underground path generated by $\omega_{|0}$ is
$\varphi'\,\bar{\nu}_1 \ldots \bar{\nu}_k$ (see
Figure~\ref{fig:casob2ii}).

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Caso_2bii.eps, width =3.8in, clip=}
\caption{\small{The underground paths generated by $\omega_{|0}$
in the case 2.2.2)}} \label{fig:casob2ii}
\end{center}
\end{figure}

\end{description}
\end{description}

\end{description}


\subsection{The underground path generated by
$\omega_{|k}$}\label{sec:under} In this section, we describe how
to obtain the underground path generated by $\omega_{|k}, k \geq
2$.
For any $h$, $1 \leq h \leq j$, let $\omega' =\nu\varphi$ be
the path obtained from  $\omega_{|k}$ and ending on the $x$-axis
with a positive suffix; $\varphi$ is the rightmost suffix in
$\omega'$ which is primitive.

If the path $\varphi^c$ does not contain the forbidden pattern
$\pat$, the underground path generated by $\omega_{|k}$ is
$\nu\varphi^c$.

If the path $\varphi^c$ contains the forbidden pattern $\pat$, we
must apply a \emph{swap} operation $\Phi$ in order to obtain a
path $\varphi_1=\Phi(\varphi^c)$ avoiding the forbidden pattern.
The underground path generated by $\omega_{|k}$ is $\nu\varphi_1$.

Before describing the $\Phi$ operation on $\varphi^c$, let us
consider the following proposition.
\begin{proposition}\label{prop1}Let $\mu \in F^{[\pat]}$ be a primitive path;
$\mu^c$ contains the forbidden pattern $\pat = (x\barx)^jx$ if and only
if $\mu$ contains the pattern $\mathfrak{p'}=(\barx)^2(x\barx)^j\barx$.
\end{proposition}

 From Proposition~\ref{prop1} it follows that, if $\varphi^c$
contains the forbidden pattern $\pat$, then it is preceded and
followed by at least a rise step.

Operation $\Phi$ must generate a path $\varphi_1$ avoiding the
forbidden pattern $\pat= (x\barx)^jx$ and such that $\varphi_1^c
\in F\backslash F^{[\pat]}$; in this way $\varphi_1$ is not the
complement of any path in $F^{[\pat]}$. The path $\varphi_1
=\Phi(\varphi^c)$ is obtained as follows:

\begin{itemize}
\item [i)] consider the straight line $r$ from the beginning of
the pattern $\mathfrak{p} =(x\barx)^jx$ and let $t_1$ be the
rightmost point in which $r$ intersects $\varphi^c$ on the left of
$\pat$ such that $t_1$ is preceded by at least two fall steps. Let
$\delta_2=(x\barx)^m$, $0 \leq m < j$, be the subsequence on the
right of $t_1$ and followed by at least a fall step;

\item [ii)] \emph{swap} the initial subsequence
$\delta_1=(x\barx)^j$ of $\pat$  and $\delta_2$. It is
straightforward to see that $\delta_2$ can not be equal to
$(x\barx)^j$ since $\varphi$ does not contain the forbidden
pattern $\pat =(x\barx)^jx$ (see Figure~\ref{fig:swap}.a)). When
$m=0$, that is, $\delta_2$ is the empty word, we simply insert
$\delta_1$ into $t_1$ (see Figure~\ref{fig:swap}.b)).
\end{itemize}
Operation $\Phi$ is applied to each forbidden pattern in
$\varphi^c$.


\begin{figure}[!htb]
\begin{center}
\epsfig{file=Figura1.eps, width =4in, clip=} \caption{\small{Some
examples of the $\Phi$ operation, $\pat=(x\barx)^3x$}}
\label{fig:swap}
\end{center}
\end{figure}

\begin{proposition}\label{prop2} Let $\varphi_1 = \Phi(\varphi^c)$, then
$\varphi_1^c \in F\backslash F^{[\pat]}$.
\end{proposition}
\begin{proof}The $\Phi$ operation transforms the subsequence $\varrho_1=
(\barx)^m\,\delta_2\,\barx$, ($m \geq 2$), of $\varphi^c$  into
the subsequence $\varrho_2 =(\barx)^m\,\delta_1\,\barx
=(\barx)^m\,(x\barx)^j\,\barx$ of $\varphi_1$. The complement of
$\varrho_2$ is
$$\varrho_2^c= (x)^{m}\,(\barx x)^j\,x\, = (x)^{m-1}\,(x\barx)^j\,x\,x.$$
So, $\varphi_1^c$ contains the forbidden pattern
$\pat=(x\barx)^jx$.
\end{proof}

\begin{proposition} \label{prop3} Let $\mu \in F\backslash F^{[\pat]}$ be a primitive
path such that $\mu^c \in F^{[\pat]}$. Then there exists a path
$\eta \in F^{[\pat]}$ such that $\mu^c =\Phi(\eta^c)$.
\end{proposition}
\begin{proof} If $\mu \in F\backslash F^{[\pat]}$ and $\mu^c \in
F^{[\pat]}$ then $\mu^c$ contains the pattern $\barx
\barx(x\barx)^j\barx$; we apply to $\mu^c$ the following operation
$\Phi^{-1}$.
\begin{itemize}
\item [i)]Consider the straight line $r$ from the end of the
 pattern $(x\barx)^j$ and let $t_2$ be the leftmost
 point where $r$ intersects $\mu^c$ on the right of $(x\barx)^j$ such that $t_2$
 is followed by at least two rise steps. Let $\delta_2=(x\barx)^m$, $0 \leq m < j$, be
 the subsequence on the left of $t_2$ and preceded by at least a rise
 step.

\item [ii)] Swap the subsequence $(x\barx)^j$ and $\delta_2$. When
$m=0$, that is, $\delta_2$ is the empty word, we simply insert
$(x\barx)^j$ into $t_2$.
\end{itemize}

\end{proof}

Figure~\ref{fig:tree} shows the initial steps of the generating
algorithm of the paths corresponding to words in $F^{[\pat]}$,
with $\pat = (x\barx)^2x = (10)^21$.

\begin{figure}[!htb]
\begin{center}
\epsfig{file=Figura3.eps, width =4in, clip=}\caption{\small{The
initial steps of the generating algorithm of the paths
corresponding to words in $F^{[\pat]}$, $\pat = (x\barx)^2x =
(10)^21$. Dotted lines are related to $h=2$} }\label{fig:tree}
\end{center}
\end{figure}

Recall that, following the above constructions, given a path
$\omega$, the number of generated paths depends only on the
ordinate of endpoint of $\omega$.

Therefore, the complete generating algorithm can be briefly
described by the succession rule~(\ref{one}). For more details on
succession rules, the reader is invited to see
\cite{BDPP99,CORTE00,FPPR03}.
\begin{equation}\label{one}
 \begin{cases}
   (0)\\
   (0)\stackrel{h}{\rightsquigarrow}(0)(0)(1)& \text{$1 \leq h \leq j$}\\
   (1)\stackrel{h}{\rightsquigarrow}(2)& \text{$1 \leq h \leq j$}\\
   (k)\stackrel{h}{\rightsquigarrow}(0)(0)(1)\cdots(k-1)(k+1)& \text{$1 \leq h \leq j, \, k \geq 2$}\\
\end{cases}
\end{equation}

In the succession rule (\ref{one}) each number corresponds to the
ordinate of the endpoint of a path. The zero in the first line in
(\ref{one}) is associated with the empty path. Given the pattern
$\pat =(x\barx)^jx= (10)^j1$, the second line in (\ref{one}) says
that a path with $n$ rise steps and ending at ordinate 0 generates
two paths with $n+h$ rise steps, $1\leq h \leq j$, and ending at
ordinate 0, and one path with $n+h$ rise steps and ending at
ordinate 1, i.e., the second line is associated with operations
$(1)$ and $(4)$. Similarly, the third line is associated with
operations $(2)$ and $(5)$. The last line describes the
construction when the endpoint of the path has ordinate $k \geq
2$, underground path included.




\section{Enumeration of $F^{[\mathfrak{p}]}$}\label{sec:enum}

With reference to the succession rule~(\ref{one}), let $A_0$ be
the set of paths whose endpoints have ordinate~0, let $A_1$ be the
set of paths whose endpoints have ordinate~1 and let $A_k$ be the
set of paths whose endpoints have ordinate~$k$, $k \geq 2$. Then
$F^{[\mathfrak{p}]} = A_0 \cup A_1 \cup A_k$.

The paths in $A_0$ with $n$ rise steps are obtained from the paths
in $A_0$ with $n-h$, $1\leq h\leq j$, rise steps by means of the
first production of (\ref{one}) and from those in $A_k$ with $n-h$
rise steps by means of the last production of (\ref{one}).

The paths in $A_1$ with $n$ rise steps are obtained from the paths
in $A_0$ with $n-h$, $1\leq h\leq j$, rise steps by means of the
first production of (\ref{one}) and from those in $A_k$ with $n-h$
rise steps by means of the last production of (\ref{one}).

The paths in $A_k$ with $n$ rise steps are obtained from the paths
in $A_1$ with $n-h$, $1\leq h\leq j$, rise steps by means of the
second production of (\ref{one}) and from those in $A_k$ with
$n-h$ rise steps by means of the last production of (\ref{one}).

Let $n(\omega)$ be the number of rise steps of a path $\omega \in
F^{[\mathfrak{p}]}$ and let $f(\omega)$ be the ordinate of the
last point of $\omega$ itself. From the succession
rule~(\ref{one}) we obtain

\begin{eqnarray}
A_0(x,1)&=&1+2\sum_{h=1}^{j}\sum_{\omega \in
A_0}x^{n(\omega)+h}y^0 + 2\sum_{h=1}^{j}\sum_{\omega \in
A_k}x^{n(\omega)+h}y^0\label{eqn:azero},\\
A_1(x,y)&=&\sum_{h=1}^{j}\sum_{\omega \in A_0}x^{n(\omega)+h}y +
\sum_{h=1}^{j}\sum_{\omega \in
A_k}x^{n(\omega)+h}y\label{eqn:auno},\\
A_k(x,y)&=&\sum_{h=1}^{j}\sum_{\omega \in A_1}x^{n(\omega)+h}y^2
+\sum_{h=1}^{j}\sum_{\omega \in A_k}\sum_{i=2}^{f(\omega)-1}
x^{n(\omega)+h}y^i +\nonumber\\ &&+ \sum_{h=1}^{j}\sum_{\omega \in
A_k}x^{n(\omega)+h}y^{f(\omega)+1}\label{eqn:acappa}.
\end{eqnarray}

Since $$\sum_{h=1}^j\sum_{w\in A_0}x^{n(\omega)+h}y^0
=\sum_{h=1}^jx^h  \sum_{w\in A_0}x^{n(\omega)}y^0 =\sum_{h=1}^jx^h
A_0(x,1) = \frac{(x-x^{j+1})}{1-x}A_0(x,1),
$$
going on in the same way with the other terms, (\ref{eqn:azero}),
(\ref{eqn:auno}) and (\ref{eqn:acappa}) can rewritten

\begin{eqnarray}
A_0(x,1)&=&1+\frac{2(x-x^{j+1})}{1-x}A_0(x,1) +
\frac{2(x-x^{j+1})}{1-x}A_k(x,1)\label{eqn:azero1},\\
A_1(x,y)&=&\frac{y(x-x^{j+1})}{1-x}A_0(x,1) +
\frac{y(x-x^{j+1})}{1-x}A_k(x,1)\label{eqn:auno1},\\
A_k(x,y)&=&\frac{y^2(x-x^{j+1})}{1-x}A_1(x,1) +
\frac{(x-x^{j+1})}{(1-x)(y-1)}A_k(x,y)-\nonumber\\
&&-\frac{y^2(x-x^{j+1})}{(1-x)(y-1)}A_k(x,1)+
\frac{y(x-x^{j+1})}{1-x}A_k(x,y).\label{eqn:acappa1}
\end{eqnarray}
 From (\ref{eqn:acappa1}) we obtain
$$(y^2(x-x^{j+1})-y(1-x^{j+1}) +1-x^{j+1})A_k(x,y)=\\$$$$=
y^2(x-x^{j+1})A_k(x,1)- y^2(y-1)(x-x^{j+1})A_1(x,1).$$

Let $$y_0=\frac{1-x^{j+1}- \sqrt{(1-x^{j+1})^2 - 4
(x-x^{j+1})(1-x^{j+1})}}{2(x-x^{j+1}}$$ be a solution of
$$y^2(x-x^{j+1})-y(1-x^{j+1}) +1-x^{j+1}=0.$$  By using the kernel method \cite{genfun} we have
$$A_k(x,1) = (y_0-1)A_1(x,1).$$
By solving (\ref{eqn:azero1}) and (\ref{eqn:auno1}) we obtain
$$A_0(x,1) =
\frac{1-x+2(x-x^{j+1})(y_0-1)A_1(x,1)}{(1-x)-2(x-x^{j+1})},$$
$$A_1(x,1)= \frac{x-x^{j+1}}{(1-x)-(x-x^{j+1})(y_0+1)}.$$

Hence, we can state the following result.
\begin{proposition} \label{prop4}
The generating function $F_{j}(x)$, $j\geq 1$, for the words
$\omega \in F^{[\mathfrak{p}]}$ according to the number of 1's is
given by

$$F_{j}(x)= F_j(x,1) = A_0(x,1)+A_1(x,1)+A_k(x,1)=$$ $$=\frac{2(1-x^{j+1})}{3x^{j+1}-4x+1+
\sqrt{(1-x^{j+1})^2-4(x-x^{j+1})(1-x^{j+1})}}.$$
\end{proposition}

The first numbers of the sequences enumerating the binary words in
$F^{[\mathfrak{p}]}$, with $\pat=(10)^j1$, according to the number
$n$ of 1's, $1\leq n\leq 10$, and the value of $j$, $1 \leq j \leq
10$, are shown in Table~\ref{tab:conta}.

\begin{table}[ht]
\begin{center}
\small
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|}
\cline{2-11}\multicolumn{1}{r|}{}&\multicolumn{10}{c|}{$n$}\\
\hline
 $j$&1&2&3&4&5&6&7&8&9&10\\
\hline 1&3&7&18&48&131&363&1017&2873&8169&23349\\
2&3&10&32&109&377&1324&4697&16795&60425&218485\\
3&3&10&35&123&445&1631&6036&22511&84460&318438\\
4&3&10&35&126&459&1699&6350&23911&90572&344737\\
5&3&10&35&126&462&1713&6418&24225&91979&350910\\
6&3&10&35&126&462&1716&6432&24293&92293&352317\\
7&3&10&35&126&462&1716&6435&24307&92361&352631\\
8&3&10&35&126&462&1716&6435&24310&92375&352699\\
9&3&10&35&126&462&1716&6435&24310&92378&352713\\
10&3&10&35&126&462&1716&6435&24310&92378&352716\\
 \hline
\end{tabular}
\normalsize
\end{center}
\caption{The sequences enumerating the binary words in
$F^{[\mathfrak{p}]}$, with $\pat=(10)^j1$, according to the number
$n$ of 1's} \label{tab:conta}
\end{table}



\section{Conclusions and further developments}
In this paper we give the generating function which counts
particular binary words, according to the number of 1's, excluding
a fixed pattern $\mathfrak{p}=(10)^j1$, $j \geq 1$.

Successive studies should take into consideration binary words
avoiding different forbidden patterns both from an enumerative and
a constructive point of view.

Moreover, it would be interesting to study words avoiding patterns
which have a different shape, that is, not just patterns consisting
of a sequence of rise and fall steps.

Another interesting field of study consists of the determination
of a sort of invariant class of avoiding patterns that is the
paths $\pat_1, \pat_2, \ldots , \pat_l$ such that
$|F^{[\pat_1]}|=|F^{[\pat_2]}|= \cdots =|F^{[\pat_l]}|$ with
consequent bijective problems.

One could also consider a forbidden pattern on an arbitrary
alphabet and investigate words avoiding that pattern, or study
words avoiding more than one pattern and the related combinatorial
objects, considering various parameters.


\begin{thebibliography}{99}

\bibitem{genfun} C. Banderier, M. Bousquet-M\'elou,
A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps,
Generating functions for generating trees, \textit{Discrete Math.}
\textbf{246} (2002), 29--55.

\bibitem{BDPP99} E. Barcucci, A. Del Lungo, E. Pergola, and R.
Pinzani,  ECO: a methodology for the enumeration of combinatorial
objects,  \textit{J. Difference Equ. Appl}. \textbf{5} (1999),
435--490.

\bibitem{BGPP12}S. Bilotta, E. Grazzini, E. Pergola and R. Pinzani,
Generation of binary words avoiding alternating patterns,
preprint, 2012.  Available
at \url{http://arxiv.org/abs/1210.7620}.


\bibitem{BMPP11} S. Bilotta, D. Merlini, E. Pergola, and R. Pinzani,
Pattern $1^{j+1}0^j$ avoiding binary words, \textit{Fund. Inform.}
\textbf{177} (2012), 35--55.


\bibitem{CORTE00} S. Corteel, S\'{e}ries g\'{e}n\'{e}ratrices exponentielles
pour les eco-syst\`{e}mes sign\'{e}s, \textit{Proc. of the 12th
International Conference of Formal Power Series and Algebraic
Combinatorics, Moscow}, Springer, 2000, pp.\ 655--666.

\bibitem{FPPR03} L. Ferrari, E. Pergola, R. Pinzani, and S.
Rinaldi, Jumping succession rules and their generating functions,
\textit{Discrete Math.} \textbf{271} (2003), 29--50.

\bibitem{GO80} L. J. Guibas and M. Odlyzko, Long repetitive patterns
in random sequences, \textit{Zeitschrift f\"{u}r
Wahrscheinlichkeitstheorie} \textbf{53} (1980), 241--262.

\bibitem{GO81} L. J. Guibas and M. Odlyzko, String overlaps, pattern
matching, and nontransitive games, \textit{J. Combin. Theory Ser.
A} \textbf{30} (1981), 183--208.

\bibitem{SF95} R. Sedgewick and P. Flajolet, \textit{An Introduction to the
Analysis of Algorithms}, Chapman-Hall, 1995.


\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } Binary words, generating functions,
pattern avoidance.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A225034}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 27 2012;
revised version received May 3 2013.
Published in {\it Journal of Integer Sequences},
May 8 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}

                                                                                


.