\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{mathdots} \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}}} \newcommand{\G}{\mbox{$\mathcal{G}$}} \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 Algebraic Generating Functions for Languages \\ \vskip .05in Avoiding Riordan Patterns} \vskip 1cm Donatella Merlini and Massimo Nocentini\\ Dipartimento di Statistica, Informatica, Applicazioni\\ Universit\`a di Firenze\\ viale Morgagni 65 \\ 50134 Firenze \\ Italia \\ \href{mailto:donatella.merlini@unifi.it}{\tt donatella.merlini@unifi.it}\\ \href{mailto:massimo.nocentini@unifi.it}{\tt massimo.nocentini@unifi.it}\\ \ \\ \end{center} \vskip .2 in \begin{abstract} We study the languages $\mathfrak{L}^{[\mathfrak{p}]}\subset \{0,1\}^*$ of binary words $w$ avoiding a given pattern $\mathfrak{p}$ such that $|w|_0\leq |w|_1$ for every $w\in \mathfrak{L}^{[\mathfrak{p}]},$ where $|w|_0$ and $|w|_1$ correspond to the number of $0$-bits and $1$-bits in the word $w$, respectively. In particular, we concentrate on patterns $\mathfrak{p}$ related to the concept of Riordan arrays. These languages are not regular, but can be enumerated by algebraic generating functions corresponding to many integer sequences that were previously unlisted in the On-Line Encyclopedia of Integer Sequences. We give explicit formulas for these generating functions, expressed in terms of the autocorrelation polynomial of $\mathfrak{p}$, and also give explicit formulas for the coefficients of some particular patterns, algebraically and combinatorially. \end{abstract} \section{Introduction} \label{sec:introduction} In this paper we study the languages $\mathfrak{L}^{[\mathfrak{p}]}\subset \{0,1\}^*$ of binary words avoiding a given binary pattern $\mathfrak{p}$, having the property that $|w|_0\leq |w|_1$ for every word $w\in \mathfrak{L}^{[\mathfrak{p}]},$ where $|w|_0$ and $|w|_1$ correspond to the number of $0$-bits and $1$-bits in the word $w$, respectively. The notion of a pattern can be formalized in several ways. In this paper we consider \textit{factor patterns}, that is, patterns whose letters must appear in exact order and contiguously in the sequence under observation. The set of binary words avoiding a pattern, without the restriction $|w|_0\leq |w|_1$, is defined by a regular language, and can be enumerated in terms of the number of $1$-bits and $0$-bits by using classical results (see, e.g., Guibas and Odlyzko \cite{GO80,GO81} and Sedgewick and Flajolet \cite{SF96}). However, when we consider the additional restriction that the words have no more $0$-bits than $1$-bits, the language is no longer regular and enumerating it is a harder problem. In this paper we are interested in \textit{Riordan patterns}, a concept defined by Sprugnoli and the first author \cite{MS11} in terms of the \textit{autocorrelation polynomial} $C^{[\mathfrak{p}]}(x,y)$ of pattern $\mathfrak{p}=p_{0}\cdots p_{h-1}$. The coefficients of this polynomial are given by the \textit{autocorrelation vector} associated to $\mathfrak{p}$, that is, the vector $c=(c_0,\ldots ,c_{h-1})$ of bits defined in terms of Iverson's bracket notation (for a predicate $P$, the expression $[\![P]\!]$ has value $1$ if $P$ is true and $0$ otherwise) as follows: $$c_i=[\![p_0p_1\cdots p_{h-1-i}=p_{i}p_{i+1}\cdots p_{h-1}]\!];$$ or in words, the bit $c_i$ is determined by shifting $\mathfrak{p}$ to the right by $i$ positions, setting $c_i=1$ if and only if the remaining letters match the original. For example, when $\mathfrak{p}= 10101$ the autocorrelation vector is $c=(1,0,1,0,1)$, as illustrated in Table \ref{auto}, and $C^{[\mathfrak{p}]}(x,y)=1+xy+x^2y^2$, namely we add a term $x^jy^i$ for each tail of the pattern with $j$ $1$-bits and $i$ $0$-bits, where $c_{j+i}=1$. \begin{table}[H] \begin{center} \begin{tabular}{ccccc|ccccccc} $1$ & $0$ & $1$ & $0$& $1$ & \multicolumn{6}{l}{Tails} & $c_{i}$ \\ \hline $1$ & $0$ & $1$ & $0$ & $1$ & & & & & & & $1$ \\ & $1$ & $0$ & $1$ & $0$ & $1$ & & & & & & $0$ \\ & & $1$ & $0$ & $1$ & $0$ & $1$ & & & & & $1$ \\ & & & $1$ & $0$ & $1$ & $0$ & $1$ & & & & $0$ \\ & & & & $1$ & $0$ & $1$ & $0$ & $1$ & & & $1$ \\ \end{tabular} \end{center} \caption{\label{auto}The autocorrelation vector for $\mathfrak{p}= 10101$.} \end{table} For each pattern $\mathfrak{p},$ we can compute the \textit{complement} pattern $\mathfrak{\bar{p}}$ by changing every $1$ to $0$ and every $0$ to $1$; for example, if $\mathfrak{p}= 10101$ then $\mathfrak{\bar{p}}=01010$, therefore $C^{[\mathfrak{p}]}(x,y)=C^{[\mathfrak{\bar{p}}]}(y,x)$. Addition of constraints to the nature of a pattern $\mathfrak{p}$ yields the following definition: \begin{definition}[Riordan pattern] \label{defrp} We say that $\mathfrak{p}=p_0\cdots p_{h-1}$ is a Riordan pattern if and only if \begin{displaymath} C^{[\mathfrak{p}]}(x,y)=C^{[\mathfrak{\bar{p}}]}(y,x)=\sum_{i=0}^{\lfloor(h-1)/2\rfloor}c_{2i}x^iy^i, \quad \mbox{with} \quad |n_1^{[\mathfrak{p}]}-n_0^{[\mathfrak{p}]}|\in \left\{0,1 \right\} \end{displaymath} where $n_1^{[\mathfrak{p}]}$ and $n_0^{[\mathfrak{p}]}$ correspond to the number of $1$-bits and $0$-bits in the pattern, respectively. \end{definition} For example, Table \ref{auto} corresponds to a Riordan pattern and $\mathfrak{p}= 1100110110011000$ is another Riordan pattern having $n_1^{[\mathfrak{p}]}=n_0^{[\mathfrak{p}]}=8$ and $C^{[\mathfrak{p}]}(x,y)=1$. Moreover, in Table \ref{tutti7} we give all the Riordan patterns of length 7 with first bit equal to $1$ and their correlation polynomials, the corresponding complement patterns can be easily determined. \begin{table}[H] $$ {\displaystyle \begin{array}{|c|c|} \hline \mathfrak{p} & C^{[\mathfrak{p}]}(x,y)\\ \hline {\displaystyle {1010100, 1011000 \atop 1011100, 1100010}} & \\ [0.3cm] {\displaystyle {1100100, 1101000 \atop 1101010, 1101100}} & 1\\ [0.3cm] {\displaystyle {1110000, 1110010 \atop 1110100, 1111000}} & \\ [0.3cm] \hline 1001100, 1100110 & 1+x^2y^2 \\ \hline {\displaystyle {1000111, 1001011 \atop 1001101, 1010011 }} & 1+x^3y^3 \\ [0.3cm] {\displaystyle {1011001, 1100101 \atop 1101001, 1110001}} & \\ [0.3cm] \hline 1010101 & 1+xy+x^2y^2+x^3y^3 \\ \hline \end{array} } $$ \caption{\label{tutti7}The Riordan patterns of length 7 with first bit equal to $1$ and their correlation polynomials} \end{table} The name \textit{Riordan} in the above definition is due to the connection with the well-known concept of \textit{Riordan arrays}. We briefly recall that a Riordan array is an infinite lower triangular array $(d_{n,k} )_{n,k \in \mathbb{N}},$ defined by a pair of formal power series $(d(t),h(t)),$ such that $d(0)\neq 0, h(0)=0, h^\prime(0)\neq0$ and the generic element $d_{n,k}$ is the coefficient of monomial $t^{n}$ in the series expansion of $d(t)h(t)^{k}$. Formally, \begin{displaymath} d_{n,k}=[t^n]d(t)h(t)^k, \qquad n,k \geq 0 \end{displaymath} where $d_{n,k}=0$ for $k>n$. These arrays were introduced in 1991 by Shapiro, Getu, Woan and Woodson \cite{SGWW91}, with the aim of defining a class of infinite lower triangular arrays with properties analogous to those of the Pascal triangle. Since then they have attracted, and continue to attract, much attention in the literature. Some of their structural properties were studied by Rogers, Sprugnoli, Verri and the first author \cite{MRSV97}, and additional properties were recently analyzed by Luz\'on, Mor\'on, Sprugnoli and the first author \cite{LMMS14}. In particular, we recall that the bivariate generating function enumerating the sequence $(d_{n,k} )_{n,k \in\mathbb{N}}$ is \begin{equation} \label{bgf} R(t,w) = \sum_{n,k \in\mathbb{N}}{d_{n,k} t^n w^k} = {d(t) \over 1-wh(t)} \end{equation} An important property of Riordan array concerns the computation of combinatorial sums. A first paper in this direction is due to Sprugnoli \cite{Spr94}, while the case dealing with implicit Riordan arrays is treated by Sprugnoli, Verri and the first author \cite{MSV09}. In particular we have the following result: \begin{equation} \label{somme} \sum_{k=0}^n d_{n,k}f_k=[t^n]d(t)f(h(t)) \quad \mbox{or} \quad \left( d(t), h(t)\right) \ast f(t)= d(t) f(h(t)), \end{equation} that is, every combinatorial sum involving a Riordan array can be computed by extracting the coefficient of $t^n$ from the series expansion of $d(t)f(h(t))$, where $f(t)=\G(f_k)=\sum_{k\geq 0}f_kt^k$ is the generating function of the sequence $(f_k)_{k \in\mathbb{N}}$ and the symbol $\G$ denotes the generating function operator. Due to its importance, relation (\ref{somme}) is often called the \textit{fundamental rule} of Riordan arrays. In this paper, the notation $(f_k)_{k}$ will be used as an abbreviation of $(f_k)_{k\in\mathbb{N}}$. Coming back to the languages $\mathfrak{L}^{[\mathfrak{p}]}\subset \{0,1\}^*$ of binary words avoiding a pattern $\mathfrak{p}$, let $R_{n,k}^{[\mathfrak{p}]}$ be the number of words avoiding $\mathfrak{p}$ and having $n$ $1$-bits and $n-k$ $0$-bits; additionally, let $\mathcal{R}^{[\mathfrak{p}]}=\left(R_{n,k}^{[\mathfrak{p}]}\right)_{n,k\in\mathbb{N}}$ the enclosing matrix. The following theorem, which was proved by Sprugnoli and the first author \cite{MS11}, shows the importance of Riordan patterns: \begin{theorem} \label{main} Matrices ${\cal{R}^{[\mathfrak{p}]}}$ and ${\cal{R}^{[\bar{\mathfrak{p}]}}}$ are Riordan arrays if and only if $\mathfrak{p}$ is a Riordan pattern. \end{theorem} By the previous theorem, matrices ${\cal{R}^{[\mathfrak{p}]}}$ and ${\cal{R}^{[\bar{\mathfrak{p}]}}}$ can be defined as $${\cal{R}^{[\mathfrak{p}]}}=(d^{[\mathfrak{p}]}(t),h^{[\mathfrak{p}]}(t)) \text{ and } {\cal{R}^{[\bar{\mathfrak{p}]}}}=(d^{[\bar{\mathfrak{p}}]}(t),h^{[\bar{\mathfrak{p}}]}(t))$$ for the appropriate $d^{[\mathfrak{p}]},$ $h^{[\mathfrak{p}]},$ $d^{[\bar{\mathfrak{p}}]},$ $h^{[\bar{\mathfrak{p}}]},$ given a Riordan pattern $\mathfrak{p}$; moreover, they represent the lower and upper part of the array ${\cal{F}^{[\mathfrak{p}]}}=(F_{n,k}^{[\mathfrak{p}]})_{n,k \in \mathbb{N}}$, where $F_{n,k}^{[\mathfrak{p}]}$ denotes the number of words avoiding pattern $\mathfrak{p}$ and having $n$ $1$-bits and $k$ $0$-bits . For the sake of clarity, Tables \ref{Fprimo}, \ref{Rprimoa} and \ref{Rprimob} illustrate some rows for the matrices ${\cal{F}^{[\mathfrak{p}]}},$ ${\cal{R}^{[\mathfrak{p}]}}$ and ${\cal{R}^{[\bar{\mathfrak{p}]}}}$, where $\mathfrak{p}=10101$. \begin{remark} Riordan patterns are not the only patterns related to Riordan arrays; for example, given the pattern $\mathfrak{p}=0100100$ corresponding to $C^{[\mathfrak{p}]}(x,y)=1+xy^2+x^2y^4$, matrix ${\cal{R}^{[\mathfrak{p}]}}$ is still a Riordan array but ${\cal{R}^{[\bar{\mathfrak{p}}]}}$ is not, as illustrated by Baccherini, Sprugnoli and the first author \cite[Example 5.4]{BMS07a}. However, in these situations it is not easy to find functions $d^{[\mathfrak{p}]}(t)$ and $h^{[\mathfrak{p}]}(t)$, while for Riordan patterns it is always possible, as shown in Theorems \ref{main} and \ref{teo1}. \end{remark} \begin{table}[H] $$ \begin{array}{c|cccccccc} n/k & 0 & 1 & 2 & 3 & 4 &5 &6 &7 \\ \cline{1-9} 0 & 1 & 1 & 1 & 1& 1 & 1 & 1 & 1\\ 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36\\ 3 & 1 & 4 & 9 & 18 & 32 & 52& 79 & 114\\ 4 & 1& 5 & 13 & 30 & 60 & 109& 184 & 293\\ 5 & 1 & 6 & 18 & 46 & 102 & 204 & 377 & 654\\ 6 & 1 & 7 & 24 & 67 & 163 & 354& 708 & 1324\\ 7 & 1 & 8 & 31 & 94 & 248 &580& 1245 &2490\\ \end{array} $$ \caption{\label{Fprimo}The matrix ${\cal{F}^{[\mathfrak{p}]}}$ for $\mathfrak{p}=10101$} \end{table} \begin{table}[H] \hspace{-.5cm} \parbox{.47\textwidth}{ \centering $$ \begin{array}{c|cccccccc} n/k & 0 & 1 & 2 & 3 & 4 &5 &6 &7 \\ \cline{1-9} 0 & 1 & & & & & & &\\ 1 & 2 & 1 & & & & & &\\ 2 & 6& 3 & 1 & & & & &\\ 3 & 18 & 9 & 4 & 1 & & & &\\ 4 & 60 & 30 & 13 & 5 & 1& & & \\ 5 & 204 & 102 & 46 & 18 & 6 &1 & &\\ 6 & 708 & 354 & 163 & 67 & 24 & 7& 1 &\\ 7 & 2490 & 1245 & 580 &248 & 94 & 31 & 8 &1\\ \end{array} $$ \caption{\label{Rprimoa} ${\cal{R}^{[\mathfrak{p}]}}$ for $\mathfrak{p}=10101$} } \hfill \parbox{.47\textwidth}{ \centering $$ \begin{array}{c|cccccccc} n/k & 0 & 1 & 2 & 3 & 4 &5 &6 &7 \\ \cline{1-9} 0 & 1 & & & & & & &\\ 1 & 2 & 1 & & & & & &\\ 2 & 6& 3 & 1 & & & & &\\ 3 & 18 & 10 & 4 & 1 & & & &\\ 4 & 60 & 32 & 15 & 5 & 1& & & \\ 5 & 204 & 109 & 52 & 21 & 6 &1 & &\\ 6 & 708 & 377 & 184 & 79 & 28 & 7& 1 &\\ 7 & 2490 & 1324 & 654 &293 & 114 & 36 & 8 &1\\ \end{array} $$ \caption{\label{Rprimob} ${\cal{R}^{[\bar{\mathfrak{p}]}}}$ for $\mathfrak{p}=10101$} } \end{table} As already observed, the enumeration of the set of binary words avoiding a pattern, without the restriction about the number of $1$-bits and $0$-bits can be done by using classical results and gives the following rational bivariate generating function for the sequence $(F_{n,k}^{[\mathfrak{p}]})_{n,k \in \mathbb{N}}:$ $$F^{[\mathfrak{p}]}(x,y) =\genfrac{}{}{1pt}{0}{C^{[\mathfrak{p}]}(x,y)}{(1-x-y)C^{[\mathfrak{p}]}(x,y) +x^{n_1^{[\mathfrak{p}]}}y^{n_0^{[\mathfrak{p}]}}},$$ where $n_1^{[\mathfrak{p}]}$ and $n_0^{[\mathfrak{p}]}$ correspond to the number of $1$-bits and $0$-bits, respectively, and $C^{[\mathfrak{p}]}(x,y)$ is the autocorrelation polynomial, all relative to pattern $\mathfrak{p}$. Consequently, $F^{[\mathfrak{p}]}(t,1)$ and $F^{[\mathfrak{p}]}(t,t)$ count the words avoiding $\mathfrak{p}$ according to the number of $1$-bits and to length of each word, respectively. Using the theory of Riordan arrays and the results by Sprugnoli and the first author \cite{MS11}, we give explicit algebraic generating functions enumerating the set of binary words avoiding a Riordan pattern with the restriction $|w|_0\leq |w|_1$ according to various parameters, in particular to the number of $1$-bits and to the words length. Most of the corresponding sequences are new to the On-Line Encyclopedia of Integer Sequences (OEIS)\footnote{We attach a label $Axxxxxx$ to a sequence if it appears in the OEIS with that identifier.} \cite{OEIS}; moreover, we also give explicit formulas for the coefficients of some particular patterns by providing algebraic and combinatorial proofs. Finally, our results can be interpreted in the theory of paths and codes in light of the bijection among binary words and paths, which maps a $0$-bit to a south-east step $\diagdown$ and a $1$-bit to a north-east step $\diagup$. From this point of view, a coefficient $R_{n,k}^{[\mathfrak{p}]} \in \mathcal{R}^{[\mathfrak{p}]}$ counts the number of paths containing $n$ steps of $\diagup$ and $n-k$ steps of $\diagdown$, avoiding the subpath corresponding to pattern $\mathfrak{p}$, allowed to cross the $x$-axis but required to end at coordinate $(2n-k, k)$ such that $0 \leq k \leq n$. In particular, $d^{[\mathfrak{p}]}(t)$ is the generating function of paths that avoid $\mathfrak{p}$ and end on the $x$-axis. \section{Riordan arrays for Riordan patterns} We start with a theorem that is a direct consequence of the results by Sprugnoli and the first author \cite[Theorems 2.3 and 3.3]{MS11}. \begin{theorem} \label{teo1} Let $R_{n,k}^{[\mathfrak{p}]}$ be the number of binary words with $n$ $1$-bits and $n-k$ $0$-bits, avoiding a Riordan pattern $\mathfrak{p}$. Then the triangle ${\cal{R}^{[\mathfrak{p}]}}=(R_{n, k}^{[\mathfrak{p}]})$ is a Riordan array ${\cal{R}^{[\mathfrak{p}]}}=(d^{[\mathfrak{p}]}(t),h^{[\mathfrak{p}]}(t))$. In particular, if $n_1^{[\mathfrak{p}]}$ and $n_0^{[\mathfrak{p}]}$ correspond to the number of $1$-bits and $0$-bits in the pattern, $C^{[\mathfrak{p}]}(x,y)$ is the autocorrelation polynomial of $\mathfrak{p}$ and $C^{[\mathfrak{p}]}(t)=C^{[\mathfrak{p}]}(\sqrt{t},\sqrt{t}),$ then \begin{itemize} \item if $n_1^{[\mathfrak{p}]}-n_0^{[\mathfrak{p}]}=1$ we have $$d^{[\mathfrak{p}]}(t)={C^{[\mathfrak{p}]}(t) \over \sqrt{C^{[\mathfrak{p}]}(t)^2-4tC^{[\mathfrak{p}]}(t)(C^{[\mathfrak{p}]}(t)-t^{n_0^{[\mathfrak{p}]}})}}, $$ $$h^{[\mathfrak{p}]}(t)={C^{[\mathfrak{p}]}(t) -\sqrt{C^{[\mathfrak{p}]}(t)^2-4tC^{[\mathfrak{p}]}(t)(C^{[\mathfrak{p}]}(t)-t^{n_0^{[\mathfrak{p}]}})} \over 2 C^{[\mathfrak{p}]}(t)};$$ \item if $n_1^{[\mathfrak{p}]}-n_0^{[\mathfrak{p}]}=0$ we have $$d^{[\mathfrak{p}]}(t)={C^{[\mathfrak{p}]}(t) \over \sqrt{( C^{[\mathfrak{p}]}(t)+t^{n_0^{[\mathfrak{p}]}})^2-4tC^{[\mathfrak{p}]}(t)^2}},$$ $$h^{[\mathfrak{p}]}(t)= {C^{[\mathfrak{p}]}(t)+ t^{n_0^{[\mathfrak{p}]}} - \sqrt{( C^{[\mathfrak{p}]}(t)+t^{n_0^{[\mathfrak{p}]}})^2-4tC^{[\mathfrak{p}]}(t)^2} \over 2 C^{[\mathfrak{p}]}(t)};$$ \item if $n_0^{[\mathfrak{p}]}-n_1^{[\mathfrak{p}]}=1$ we have $$d^{[\mathfrak{p}]}(t)={C^{[\mathfrak{p}]}(t) \over \sqrt{C^{[\mathfrak{p}]}(t)^2-4tC^{[\mathfrak{p}]}(t)(C^{[\mathfrak{p}]}(t)-t^{n_1^{[\mathfrak{p}]}})}},$$ $$h^{[\mathfrak{p}]}(t)={C^{[\mathfrak{p}]}(t) -\sqrt{C^{[\mathfrak{p}]}(t)^2-4tC^{[\mathfrak{p}]}(t)(C^{[\mathfrak{p}]}(t)-t^{n_1^{[\mathfrak{p}]}})} \over 2 (C^{[\mathfrak{p}]}(t)- t^{n_1^{[\mathfrak{p}]}})}.$$ \end{itemize} \end{theorem} If $R^{[\mathfrak{p}]}(t,w)$ denotes the bivariate generating function of the Riordan array ${\cal{R}^{[\mathfrak{p}]}},$ as already mentioned in the Introduction, we have $$R^{[\mathfrak{p}]}(t,w)=\sum_{n,k\in\mathbb{N}} R_{n, k}^{[\mathfrak{p}]}t^n w^k={d^{[\mathfrak{p}]}(t) \over 1-wh^{[\mathfrak{p}]}(t)},$$ and Theorem \ref{teo1} allow us to state the following results. \begin{theorem} \label{teo2} Let $\mathfrak{p}$ be a Riordan pattern and $S^{[\mathfrak{p}]}(t)=\sum_{n\geq 0}S_n^{[\mathfrak{p}]}t^n$ the generating function enumerating the set of binary words $\left\lbrace w\in \lbrace 0,1 \rbrace^{*}: |w|_0\leq |w|_1\right\rbrace$ avoiding a Riordan pattern $\mathfrak{p}$ according to the number of $1$-bits. Then we have \begin{itemize} \item if $n_1^{[\mathfrak{p}]}=n_0^{[\mathfrak{p}]}+1$ $$S^{[\mathfrak{p}]}(t)={2C^{[\mathfrak{p}]}(t) \over \sqrt{Q(t)}\left(\sqrt{C^{[\mathfrak{p}]}(t)}+ \sqrt{Q(t)} \right)}, $$ where $Q(t)={(1-4t)C^{[\mathfrak{p}]}(t)^2+4t^{n_1^{[\mathfrak{p}]}}};$ \item if $n_0^{[\mathfrak{p}]}=n_1^{[\mathfrak{p}]}+1$ $$S^{[\mathfrak{p}]}(t)={2C^{[\mathfrak{p}]}(t)(C^{[\mathfrak{p}]}(t)-t^{n_1^{[\mathfrak{p}]}} ) \over \sqrt{Q(t)} \left(C^{[\mathfrak{p}]}(t)-2t^{n_1^{[\mathfrak{p}]}}+ \sqrt{Q(t)} \right) },$$ where $Q(t)={ (1-4t)C^{[\mathfrak{p}]}(t)^2+4t^{n_0^{[\mathfrak{p}]}}C^{[\mathfrak{p}]}(t)};$ \item if $n_1^{[\mathfrak{p}]}=n_0^{[\mathfrak{p}]}$ $$S^{[\mathfrak{p}]}(t)={2C^{[\mathfrak{p}]}(t)^2 \over \sqrt{Q(t)} \left(C^{[\mathfrak{p}]}(t)-t^{n_0^{[\mathfrak{p}]}}+ \sqrt{Q(t)} \right) },$$ where $Q(t)=(1-4t)C^{[\mathfrak{p}]}(t)^2+2t^{n_0^{[\mathfrak{p}]}}C^{[\mathfrak{p}]}(t)+t^{2n_0^{[\mathfrak{p}]}}$. \end{itemize} \end{theorem} \begin{proof} For the proof we can observe that $S^{[\mathfrak{p}]}(t)=\sum_{n\geq 0}S_n^{[\mathfrak{p}]}t^n=R^{[\mathfrak{p}]}(t,1),$ or, equivalently, that $S_n^{[\mathfrak{p}]}=\sum_{k=0}^nR_{n, k}^{[\mathfrak{p}]}$ and apply the fundamental rule (\ref{somme}) with $f_k=1$. The statement of the theorem can be found after some algebraic simplification. \end{proof} \begin{theorem} \label{teo3} Let $\mathfrak{p}$ be a Riordan pattern and $L^{[\mathfrak{p}]}(t)=\sum_{n\geq 0}L_n^{[\mathfrak{p}]}t^n$ the generating function enumerating the set of binary words $\left\lbrace w\in \lbrace 0,1 \rbrace^{*}: |w|_0\leq |w|_1\right\rbrace$ avoiding a Riordan pattern $\mathfrak{p}$ according to the length. Then we have \begin{itemize} \item if $n_1^{[\mathfrak{p}]}=n_0^{[\mathfrak{p}]}+1$ $$L^{[\mathfrak{p}]}(t)= {2tC^{[\mathfrak{p}]}(t^2)^2 \over \sqrt{Q(t)}\left((2t-1)C(t^2)+ \sqrt{ Q(t) } \right)}, $$ where $Q(t)=C^{[\mathfrak{p}]}(t^2)\left( (1-4t^2)C^{[\mathfrak{p}]}(t^2)+4t^{2n_1^{[\mathfrak{p}]}}\right);$ \item if $n_0^{[\mathfrak{p}]}=n_1^{[\mathfrak{p}]}+1$ $$L^{[\mathfrak{p}]}(t)={2t\sqrt{C^{[\mathfrak{p}]}(t^2)}(t^{2n_1^{[\mathfrak{p}]}}-C^{[\mathfrak{p}]}(t^2)) \over \sqrt{ Q(t) }\left((1-2t)C^{[\mathfrak{p}]}(t^2)+2t^{n_0^{[\mathfrak{p}]} +n_1^{[\mathfrak{p}]}} - \sqrt{C^{[\mathfrak{p}]}(t^2) Q(t) } \right)}, $$ where $Q(t)=(1-4t^2)C^{[\mathfrak{p}]}(t^2)+4t^{2n_0^{[\mathfrak{p}]}};$ \item if $n_1^{[\mathfrak{p}]}=n_0^{[\mathfrak{p}]}$ $$L^{[\mathfrak{p}]}(t)= {2tC^{[\mathfrak{p}]}(t^2)^2 \over \sqrt{ Q(t) }\left((2t-1)C(t^2)-t^{2n_0^{[\mathfrak{p}]}} + \sqrt{ Q(t) } \right)}, $$ where $Q(t)=(1-4t^2)C^{[\mathfrak{p}]}(t^2)^2+2t^{2n_0^{[\mathfrak{p}]}}C^{[\mathfrak{p}]}(t^2)+t^{4n_0^{[\mathfrak{p}]}}$. \end{itemize} \end{theorem} \begin{proof} For the proof we can observe that the application of generating function $R^{[\mathfrak{p}]}(t, w)$ as \begin{displaymath} R^{[\mathfrak{p}]}\left(tw,{1 \over w}\right)=\sum_{n,k\in\mathbb{N}} R_{n, k}^{[\mathfrak{p}]}t^n w^{n-k} \end{displaymath} entails that $[t^{r}w^{s}]R^{[\mathfrak{p}]}\left(tw,{1 \over w}\right)=R_{r, r-s}^{[\mathfrak{p}]}$, which is the number of binary words with $r$ $1$-bits and $s$ $0$-bits. To enumerate according to the length let $t=w$, therefore $L^{[\mathfrak{p}]}(t)=\sum_{n\geq 0}L_n^{[\mathfrak{p}]}t^n=R^{[\mathfrak{p}]}(t^2,1/t)$. The statement of the theorem can be found after some algebraic simplification. \end{proof} Theorems \ref{teo2} and \ref{teo3} allow us to find the generating functions $S^{[\mathfrak{p}]}(t)$ and $L^{[\mathfrak{p}]}(t)$ in terms of the autocorrelation polynomial for every Riordan pattern $\mathfrak{p}$. In what follows, we study some special classes of patterns characterized by an autocorrelation polynomial that can be easily computed, as in the case $C^{[\mathfrak{p}]}(x,y)=1$. For such particular patterns, Theorem \ref{teo1} can be simplified as follows: \begin{corollary} \label{corodh} Let ${\cal{R}^{[\mathfrak{p}]}}=(R_{n, k}^{[\mathfrak{p}]})_{n,k\in\mathbb{N}}=(d^{[\mathfrak{p}]}(t),h^{[\mathfrak{p}]}(t))$ be the Riordan array corresponding to the number of binary words with $n$ $1$-bits and $n-k$ $0$-bits that avoid the Riordan pattern $\mathfrak{p}$. Then we have the following particular cases: \begin{itemize} \item for $\mathfrak{p}=1^{j+1}0^j$ we have the Riordan array $$ d^{[\mathfrak{p}]}(t)={1 \over \sqrt{1-4t+4t^{j+1}}}, \quad h^{[\mathfrak{p}]}(t)={1 -\sqrt{1-4t+4t^{j+1}} \over 2 };$$ \item $\mathfrak{p}=0^{j+1}1^j$ we have the Riordan array $$ d^{[\mathfrak{p}]}(t)={1 \over \sqrt{1-4t+4t^{j+1}}}, \quad h^{[\mathfrak{p}]}(t)={1 -\sqrt{1-4t+4t^{j+1}} \over 2(1-t^j) };$$ \item $\mathfrak{p}=1^{j}0^j$ and $\mathfrak{p}=0^{j}1^j$ we have the Riordan array $$ d^{[\mathfrak{p}]}(t)={1 \over \sqrt{1-4t+2t^j+t^{2j}}}, \quad h^{[\mathfrak{p}]}(t)={{1+t^j -\sqrt{1-4t+2t^j+t^{2j}} } \over 2 };$$ \item $\mathfrak{p}=(10)^j1$ we have the Riordan array \begin{displaymath} \begin{split} d^{[\mathfrak{p}]}(t) &= { \sum_{i=0}^j t^i \over \sqrt{1-2\sum_{i=1}^jt^i-3 \left( \sum_{i=1}^j t^i \right)^2}},\\ h^{[\mathfrak{p}]}(t) &= {\sum_{i=0}^jt^i -\sqrt{1-2\sum_{i=1}^jt^i-3\left( \sum_{i=1}^j t^i \right)^2} \over 2 \sum_{i=0}^jt^i}; \end{split} \end{displaymath} \item $\mathfrak{p}=(01)^j0$ we have the Riordan array \begin{displaymath} \begin{split} d^{[\mathfrak{p}]}(t) &= { \sum_{i=0}^j t^i \over \sqrt{1-2\sum_{i=1}^jt^i-3 \left( \sum_{i=1}^j t^i \right)^2}},\\ h^{[\mathfrak{p}]}(t) &= {\sum_{i=0}^jt^i -\sqrt{1-2\sum_{i=1}^jt^i-3\left( \sum_{i=1}^j t^i \right)^2} \over 2 \sum_{i=0}^{j-1}t^i}. \end{split} \end{displaymath} \end{itemize} \end{corollary} As a peculiar instance, observe that when we instantiate a pattern from family $\mathfrak{p}=1^{j}0^{j}$ with $j=1$ we get a Riordan array ${\mathcal{R}^{[10]}} = \left(d^{[10]}(t), h^{[10]}(t)\right)$ such that \begin{displaymath} d^{[10]}(t)=\frac{1}{1-t} \quad \text{and} \quad h^{[10]}(t) = t, \end{displaymath} so the number $R_{n, 0}^{[10]}$ of words containing $n$ $1$-bits and $n$ $0$-bits, avoiding pattern $\mathfrak{p}=10$, is $[t^{n}] d^{[10]}(t) = 1$ for $n\in\mathbb{N}$. If we consider the combinatorial interpretation of $R_{n,0}^{[\mathfrak{p}]}$ as lattice paths as illustrated in the last paragraph of the Introduction, this corresponds to the fact that there is exactly one \emph{valley}-shaped path having $n$ steps of both kinds $\diagup$ and $\diagdown$, avoiding $\mathfrak{p}=10$ and terminating at coordinate $(2n, 0)$ for each $n\in\mathbb{N}$, formally the path $0^{n}1^{n}$. By applying Theorem \ref{teo2} to the same patterns as before, we get the following corollary. \begin{corollary} \label{coroS} Let $S^{[\mathfrak{p}]}(t)=\sum_{n\geq 0}S_n^{[\mathfrak{p}]}t^n$ the generating function enumerating the set of binary words $\left\lbrace w\in \lbrace 0,1 \rbrace^{*}: |w|_0\leq |w|_1\right\rbrace$ avoiding a Riordan pattern $\mathfrak{p}$ according to the number of $1$-bits. We have the following particular cases: \begin{itemize} \item for $\mathfrak{p}=1^{j+1}0^j$ we have $$ S^{[\mathfrak{p}]}(t)={2 \over \sqrt{1-4t+4t^{j+1}}\left(1+ \sqrt{1-4t+4t^{j+1}}\right) };$$ \item for $\mathfrak{p}=0^{j+1}1^j$ we have $$ S^{[\mathfrak{p}]}(t)={2(1-t^j) \over \sqrt{1-4t+4t^{j+1}} \left(1-2t^j+ \sqrt{1-4t+4t^{j+1}}\right)};$$ \item for $\mathfrak{p}=1^{j}0^j$ and $\mathfrak{p}=0^{j}1^j$ we have $$ S^{[\mathfrak{p}]}(t)={2 \over \sqrt{1-4t+2t^j+t^{2j}} \left(1-t^j+\sqrt{1-4t+2t^j+t^{2j}} \right)};$$ \item for $\mathfrak{p}=(10)^j1$ we have $$ S^{[\mathfrak{p}]}(t)={2 (1-t^{j+1})\over 1-4t+3t^{j+1}+\sqrt{1-4t+2t^{j+1}+4t^{j+2}-3t^{2j+2}}};$$ \item for $\mathfrak{p}=(01)^j0$ we have $$ S^{[\mathfrak{p}]}(t)={2 (1-t^j-t^{j+1}+t^{2j+1})\over \sqrt{Q(t)} \left(1-2t^j+t^{j+1}+\sqrt{Q(t)} \right)},$$ where $Q(t)={1-4t+2t^{j+1}+4t^{j+2}-3t^{2j+2}}$. \end{itemize} \end{corollary} We observe that the case $\mathfrak{p}=(10)^j1$ in Corollary \ref{coroS} corresponds to the sequence studied by Bilotta, Grazzini and Pergola \cite{BGP13}; moreover, in Table \ref{tbl:S1_j1:0_j}, Table \ref{tbl:S0_j1:1_j}, Table \ref{tbl:S0_j:1_j}, Table \ref{tbl:S10_j:1} and Table \ref{tbl:S01_j:0} we report some expansions and some set of words related to the $S^{[\mathfrak{p}]}(t)$ functions just defined, respectively. \begin{table}[H] \begin{equation*}\begin{array}{c|cccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 1 & 3 & 7 & 15 & 31 & 63 & 127 & 255 & 511 & 1023 & 2047 & 4095\\2 & 1 & 3 & 10 & 32 & 106 & 357 & 1222 & 4230 & 14770 & 51918 & 183472 & 651191\\3 & 1 & 3 & 10 & 35 & 123 & 442 & 1611 & 5931 & 22010 & 82187 & 308427 & 1162218\\4 & 1 & 3 & 10 & 35 & 126 & 459 & 1696 & 6330 & 23806 & 90068 & 342430 & 1307138\\5 & 1 & 3 & 10 & 35 & 126 & 462 & 1713 & 6415 & 24205 & 91874 & 350406 & 1341782\\6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6432 & 24290 & 92273 & 352212 & 1349768\\7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24307 & 92358 & 352611 & 1351574\\8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92375 & 352696 & 1351973\end{array}\end{equation*} \begin{displaymath} \begin{split} [t^{3}]S^{[110]}(t) &= \big|\lbrace 111, 0111, 1011, 00111, 01011, 10011, 10101, 000111, \\ & 001011, 010011, 010101, 100011, 100101, 101001, 101010\rbrace\big| = 15 \end{split} \end{displaymath} \caption{Some expansions for $S^{[1^{j+1}0^j]}(t)$ and the set of words with $n=3$ $1$-bits, avoiding pattern $\mathfrak{p}=110$, so $j=1$ in the family; moreover, for $j=1$ the sequence corresponds to \seqnum{A000225}, for $j=2$ the sequence corresponds to \seqnum{A261058}.} \label{tbl:S1_j1:0_j} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|cccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\1 & 1 & 3 & 8 & 20 & 48 & 112 & 256 & 576 & 1280 & 2816 & 6144 & 13312\\2 & 1 & 3 & 10 & 33 & 111 & 378 & 1302 & 4525 & 15841 & 55783 & 197389 & 701286\\3 & 1 & 3 & 10 & 35 & 124 & 447 & 1632 & 6015 & 22336 & 83439 & 313216 & 1180511\\4 & 1 & 3 & 10 & 35 & 126 & 460 & 1701 & 6351 & 23890 & 90398 & 343713 & 1312108\\5 & 1 & 3 & 10 & 35 & 126 & 462 & 1714 & 6420 & 24226 & 91958 & 350736 & 1343069\\6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6433 & 24295 & 92294 & 352296 & 1350098\\7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24308 & 92363 & 352632 & 1351658\\8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92376 & 352701 & 1351994\end{array}\end{equation*} \begin{displaymath} \hspace{-1.5cm} \begin{split} [t^{3}]S^{[001]}(t) &= \big|\lbrace 111, 0111, 1011, 1101, 1110, 01011, 01101, 01110, 10101, 10110, 11010, 11100,\\ & 010101, 010110, 011010, 011100, 101010, 101100, 110100, 111000\rbrace\big| = 20 \end{split} \end{displaymath} \caption{Some expansions for $S^{[0^{j+1}1^j]}(t)$ and the set of words with $n=3$ $1$-bits, avoiding pattern $\mathfrak{p}=001$, so $j=1$ in the family; moreover, for $j=1$ the sequence corresponds to \seqnum{A001792}.} \label{tbl:S0_j1:1_j} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|cccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline0 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92378 & 352716 & 1352078\\1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\2 & 1 & 3 & 9 & 27 & 82 & 253 & 791 & 2499 & 7960 & 25520 & 82248 & 266221\\3 & 1 & 3 & 10 & 34 & 118 & 417 & 1493 & 5400 & 19684 & 72196 & 266122 & 985003\\4 & 1 & 3 & 10 & 35 & 125 & 454 & 1671 & 6211 & 23261 & 87641 & 331821 & 1261398\\5 & 1 & 3 & 10 & 35 & 126 & 461 & 1708 & 6390 & 24086 & 91328 & 347965 & 1331072\\6 & 1 & 3 & 10 & 35 & 126 & 462 & 1715 & 6427 & 24265 & 92154 & 351666 & 1347326\\7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6434 & 24302 & 92333 & 352492 & 1351028\\8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24309 & 92370 & 352671 & 1351854\end{array}\end{equation*} \begin{displaymath} \hspace{-1.5cm} \begin{split} [t^{8}]S^{[01]}(t) &= \big|\lbrace 11111111, 111111110, 1111111100, 11111111000, 111111110000,\\ & 1111111100000, 11111111000000, 111111110000000, 1111111100000000\rbrace\big| = 9 \end{split} \end{displaymath} \caption{Some expansions for $S^{[0^{j}1^j]}(t)$ (or, equivalently, $S^{[1^{j}0^{j}]}(t)$) and the set of words with $n=8$ $1$-bits, avoiding pattern $\mathfrak{p}=01$ (or, equivalently, $\mathfrak{p}=10$), so $j=1$ in the family; moreover, for $j=0$ the sequence corresponds to \seqnum{A001700}, for $j=1$ the sequence corresponds to \seqnum{A001477}.} \label{tbl:S0_j:1_j} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|cccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 1 & 3 & 7 & 18 & 48 & 131 & 363 & 1017 & 2873 & 8169 & 23349 & 67024\\2 & 1 & 3 & 10 & 32 & 109 & 377 & 1324 & 4697 & 16795 & 60425 & 218485 & 793259\\3 & 1 & 3 & 10 & 35 & 123 & 445 & 1631 & 6036 & 22511 & 84460 & 318438 & 1205457\\4 & 1 & 3 & 10 & 35 & 126 & 459 & 1699 & 6350 & 23911 & 90572 & 344737 & 1317397\\5 & 1 & 3 & 10 & 35 & 126 & 462 & 1713 & 6418 & 24225 & 91979 & 350910 & 1344092\\6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6432 & 24293 & 92293 & 352317 & 1350272\\7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24307 & 92361 & 352631 & 1351679\\8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92375 & 352699 & 1351993\end{array}\end{equation*} \begin{displaymath} \hspace{-1.5cm} \begin{split} [t^{3}]S^{[101]}(t) &= \big|\lbrace 111, 0111, 1110, 00111, 01110, 10011, 11001, 11100, 000111, 001110,\\ & 010011, 011001, 011100, 100011, 100110, 110001, 110010, 111000 \rbrace\big| = 18 \end{split} \end{displaymath} \caption{Some expansions for $S^{[(10)^{j}1]}(t)$ and the set of words with $n=3$ $1$-bits, avoiding pattern $\mathfrak{p}=101$, so $j=1$ in the family; moreover, for $j=1$ the sequence corresponds to \seqnum{A225034}.} \label{tbl:S10_j:1} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|cccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\\hline0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\1 & 1 & 3 & 8 & 22 & 61 & 171 & 483 & 1373 & 3923 & 11257 & 32418 & 93644\\2 & 1 & 3 & 10 & 33 & 113 & 393 & 1384 & 4920 & 17618 & 63456 & 229642 & 834342\\3 & 1 & 3 & 10 & 35 & 124 & 449 & 1647 & 6099 & 22754 & 85394 & 322022 & 1219205\\4 & 1 & 3 & 10 & 35 & 126 & 460 & 1703 & 6366 & 23974 & 90818 & 345691 & 1321092\\5 & 1 & 3 & 10 & 35 & 126 & 462 & 1714 & 6422 & 24241 & 92042 & 351156 & 1345049\\6 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6433 & 24297 & 92309 & 352380 & 1350518\\7 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24308 & 92365 & 352647 & 1351742\\8 & 1 & 3 & 10 & 35 & 126 & 462 & 1716 & 6435 & 24310 & 92376 & 352703 & 1352009\end{array}\end{equation*} \begin{displaymath} \hspace{-1.5cm} \begin{split} [t^{3}]S^{[010]}(t) &= \big|\lbrace 111, 0111, 1011, 1101, 1110, 00111, 01101, 01110, \\ & 10011, 10110, 11001, 11100, 000111, 001101, 001110, 011001, \\ & 011100, 100011, 100110, 101100, 110001, 111000 \rbrace\big| = 22 \end{split} \end{displaymath} \caption{Some expansions for $S^{[(01)^{j}0]}(t)$ and the set of words with $n=3$ $1$-bits, avoiding pattern $\mathfrak{p}=010$, so $j=1$ in the family; moreover, for $j=1$ the sequence corresponds to \seqnum{A025566}.} \label{tbl:S01_j:0} \end{table} Finally, by applying Theorem \ref{teo3} to the pattern families already examined, we find the following result. \begin{corollary} \label{coroL} Let $L^{[\mathfrak{p}]}(t)=\sum_{n\geq 0}L_n^{[\mathfrak{p}]}t^n$ the generating function enumerating the set of binary words $\left\lbrace w\in \lbrace 0,1 \rbrace^{*}: |w|_0\leq |w|_1\right\rbrace$ avoiding a Riordan pattern $\mathfrak{p}$ according to the length. We have the following particular cases: \begin{itemize} \item for $\mathfrak{p}=1^{j+1}0^j$ we have $$ L^{[\mathfrak{p}]}(t)={2t \over \sqrt{1-4t^2+4t^{2(j+1)}}\left(2t-1+ \sqrt{1-4t^2+4t^{2(j+1)}}\right) };$$ \item for $\mathfrak{p}=0^{j+1}1^j$ we have $$ L^{[\mathfrak{p}]}(t)={2t(t^{2j}-1) \over \sqrt{1-4t^2+4t^{2(j+1)}} \left(1-2t+2t^{2j+1} -\sqrt{1-4t^2+4t^{2(j+1)}}\right)};$$ \item for $\mathfrak{p}=1^{j}0^j$ and $\mathfrak{p}=0^{j}1^j$ we have: $$ L^{[\mathfrak{p}]}(t)={2 t \over \sqrt{1-4t^2+2t^{2j}+t^{4j}} \left(-1+2t-t^{2j}+\sqrt{1-4t^{2}+2t^{2j}+t^{4j}} \right)};$$ \item for $\mathfrak{p}=(10)^j1$ we have $$ L^{[\mathfrak{p}]}(t)={2 t (t^{2j+2}-1)\over 1-4t^2+3t^{2j+2}+(2t-1)\sqrt{Q(t)} };$$ \item for $\mathfrak{p}=(01)^j0$ we have $$ L^{[\mathfrak{p}]}(t)={2 t (t^{2j+2}-1)(t^{2j}-1)\over \sqrt{Q(t)} (t^{2j+2}-2t^{2j+1}+2t-1+ \sqrt{Q(t)}) },$$ \end{itemize} where $Q(t)={1-4t^2+2t^{2j+2}+4t^{2j+4}-3t^{4j+4}}$. \end{corollary} In Table \ref{tbl:L1_j1:0_j}, Table \ref{tbl:L0_j1:1_j}, Table \ref{tbl:L0_j:1_j}, Table \ref{tbl:L10_j:1} and Table \ref{tbl:L01_j:0} we report some expansions related to the $L^{[\mathfrak{p}]}(t)$ functions just defined, respectively. \begin{table}[H] \begin{equation*}\begin{array}{c|ccccccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 1 & 1 & 3 & 3 & 7 & 7 & 15 & 15 & 31 & 31 & 63 & 63 & 127 & 127 & 255\\2 & 1 & 1 & 3 & 4 & 11 & 15 & 38 & 55 & 135 & 201 & 483 & 736 & 1742 & 2699 & 6313\\3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 63 & 159 & 247 & 610 & 969 & 2354 & 3802 & 9117\\4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 255 & 634 & 1015 & 2482 & 4041 & 9752\\5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1023 & 2506 & 4087 & 9880\\6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4095 & 9904\\7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908\end{array}\end{equation*} \caption{Some expansions for $L^{[1^{j+1}0^j]}(t)$; moreover, for $j=1$ the sequence corresponds to \seqnum{A052551}.} \label{tbl:L1_j1:0_j} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|ccccccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\1 & 1 & 1 & 3 & 4 & 9 & 13 & 26 & 39 & 73 & 112 & 201 & 313 & 546 & 859 & 1469\\2 & 1 & 1 & 3 & 4 & 11 & 16 & 40 & 61 & 147 & 231 & 542 & 870 & 2004 & 3269 & 7423\\3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 161 & 253 & 622 & 999 & 2414 & 3942 & 9396\\4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 636 & 1021 & 2494 & 4071 & 9812\\5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2508 & 4093 & 9892\\6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9906\\7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908\end{array}\end{equation*} \caption{Some expansions for $L^{[0^{j+1}1^j]}(t)$; moreover, for $j=1$ the sequence corresponds to \seqnum{A079284}.} \label{tbl:L0_j1:1_j} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|ccccccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline0 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908\\1 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 & 6 & 7 & 7 & 8\\2 & 1 & 1 & 3 & 4 & 10 & 14 & 33 & 48 & 109 & 163 & 362 & 552 & 1207 & 1868 & 4036\\3 & 1 & 1 & 3 & 4 & 11 & 16 & 41 & 62 & 154 & 240 & 583 & 928 & 2217 & 3587 & 8459\\4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 162 & 254 & 629 & 1008 & 2455 & 4000 & 9614\\5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 637 & 1022 & 2501 & 4080 & 9853\\6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2509 & 4094 & 9899\\7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9907\end{array}\end{equation*} \caption{Some expansions for $L^{[0^{j}1^j]}(t)$ (or, equivalently, $L^{[1^{j}0^j]}(t)$); moreover, for $j=0$ the sequence corresponds to \seqnum{A027306}, for $j=1$ the sequence corresponds to \seqnum{A008619}.} \label{tbl:L0_j:1_j} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|ccccccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 1 & 1 & 3 & 3 & 7 & 8 & 19 & 23 & 53 & 66 & 150 & 191 & 429 & 555 & 1235\\2 & 1 & 1 & 3 & 4 & 11 & 15 & 38 & 56 & 139 & 210 & 511 & 790 & 1892 & 2973 & 7034\\3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 63 & 159 & 248 & 614 & 978 & 2382 & 3857 & 9273\\4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 255 & 634 & 1016 & 2486 & 4050 & 9780\\5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1023 & 2506 & 4088 & 9884\\6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4095 & 9904\\7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908\end{array}\end{equation*} \caption{Some expansions for $L^{[(10)^{j}1]}(t)$; moreover, no sequence is known in the literature, except for $j=0$.} \label{tbl:L10_j:1} \end{table} \begin{table}[H] \begin{equation*}\begin{array}{c|ccccccccccccccc}j/n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\\hline0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\1 & 1 & 1 & 3 & 4 & 9 & 13 & 28 & 42 & 87 & 134 & 271 & 425 & 844 & 1342 & 2628\\2 & 1 & 1 & 3 & 4 & 11 & 16 & 40 & 61 & 149 & 234 & 558 & 895 & 2098 & 3420 & 7909\\3 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 161 & 253 & 624 & 1002 & 2430 & 3967 & 9492\\4 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 636 & 1021 & 2496 & 4074 & 9828\\5 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2508 & 4093 & 9894\\6 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9906\\7 & 1 & 1 & 3 & 4 & 11 & 16 & 42 & 64 & 163 & 256 & 638 & 1024 & 2510 & 4096 & 9908\end{array}\end{equation*} \caption{Some expansions for $L^{[(01)^{j}0]}(t)$; moreover, no sequence is known in literature, except for $j=0$.} \label{tbl:L01_j:0} \end{table} \section{Some combinatorial interpretations} In the previous section we proved results about the enumeration of words avoiding patterns from an algebraic point of view. The aim of this section is to analyze in more details some particular cases of the various pattern families. We approach these problems either combinatorially by providing an interpretation, or algebraically by computing the coefficients of the involved generating functions explicitly. \subsection{Enumeration with respect to the number of $1$-bits} \begin{corollary} \label{coro:1_j1_0_j} Consider pattern $\mathfrak{p}=1^{j+1}0^{j}$. There is only one word in $\mathfrak{L}^{[\mathfrak{p}]}$ for $j=0$; on the other hand, there are $S_{n}^{[\mathfrak{p}]} = 2^{n+1}-1$ words for $j=1$. \end{corollary} \begin{proof} When $j=0$ the pattern to avoid is $\mathfrak{p}=1$, therefore only words $w$ in $ \lbrace \varepsilon \rbrace\cup\lbrace 0 \rbrace^{+}$ are suitable choices; however, the constraint $|w|_{0} \leq |w|_{1}$ makes $w = \varepsilon$ the only one. When $j=1$ the pattern to avoid is $\mathfrak{p}=110$ and we observe that the generic binomial ${{ {r}\choose{k}}}$ can be interpreted as the number of binary words with $r$ $0$-bits containing $k$ occurrences of the substring $10$, which we call an \emph{inversion} with respect to pattern $\mathfrak{p}=110$. In order to build a word in the language we start from the substring $0^{r}$ for $r\in\lbrace 0,\ldots,n\rbrace$ and select $k\in \lbrace 0, \ldots,r \rbrace$ $0$-bits, transforming each one using the mapping $0 \mapsto 10$, while preventing the transformation of the $0$-bit in the $10$ just introduced. This maneuver introduces $k$ inversions and the selection can be done in ${{ {r}\choose{k}}}$ ways; finally, we pad on the right with a strip $1^{n-k}$, because it is mandatory for a word to have $n$ $1$-bits. Hence there is one padding for each set of inversions and there is no other way to avoid $\mathfrak{p}$. Therefore \begin{displaymath} \sum_{r=0}^{n}{\sum_{k=0}^{r}{{ {r}\choose{k}}}} = 2^{n+1}-1 = S_{n}^{[\mathfrak{p}]}, \end{displaymath} as can be verified algebraically by extracting the coefficient of the generating function $$S^{[\mathfrak{p}]}(t)={1 \over 1-3t+2t^2}={2 \over 1-2t}-{1 \over 1-t},$$ as required. \end{proof} The same argument can be rewritten in term of sets, which allows us to give a constructive approach. Let $\mathcal{S}_{n, k, i}$ be the set of binary words containing $n$ and $k$ occurrences of $1$-bits and $0$-bits, respectively, with $i$ inversions, namely an occurrence of the subsequence $10$. By union with respect to $i$ and $k$, we get the sets $\mathcal{S}_{n, k}^{[\mathfrak{p}]}$ and $\mathcal{S}_{n}^{[\mathfrak{p}]}$, formally \begin{displaymath} \mathcal{S}_{n}^{[\mathfrak{p}]} = \bigcup_{k\in \lbrace 0,\ldots,n \rbrace} {\mathcal{S}_{n, k}^{[\mathfrak{p}]}} = \bigcup_{i\in \lbrace 0,\ldots,k \rbrace} {\mathcal{S}_{n, k, i}^{[\mathfrak{p}]}} = {\left(\bigcup_{i\in \lbrace 0,\ldots,k \rbrace}{ \mathcal{S}_{k, k, i}^{[\mathfrak{p}]}}\right)\times \left\lbrace 1^{n-k} \right\rbrace} . \end{displaymath} For the sake of clarity, we enumerate all binary words avoiding $\mathfrak{p}=110$ containing $n=3$ $1$-bits, formally we partition $\mathcal{S}_{3}^{[\mathfrak{p}]}$ as follows: \begin{displaymath} \begin{split} \mathcal{S}_{3}^{[\mathfrak{p}]} &= \mathcal{S}_{0, 0, 0}^{[\mathfrak{p}]}\times\lbrace 111 \rbrace\\ &\cup{\left(\mathcal{S}_{1, 1, 0}^{[\mathfrak{p}]}\cup\mathcal{S}_{1, 1, 1}^{[\mathfrak{p}]}\right)\times \lbrace 11 \rbrace}\\ &\cup{\left(\mathcal{S}_{2, 2, 0}^{[\mathfrak{p}]}\cup\mathcal{S}_{2, 2, 1}^{[\mathfrak{p}]}\cup\mathcal{S}_{2, 2, 2}^{[\mathfrak{p}]}\right)\times \lbrace 1 \rbrace}\\ &\cup{\left(\mathcal{S}_{3, 3, 0}^{[\mathfrak{p}]}\cup\mathcal{S}_{3, 3, 1}^{[\mathfrak{p}]}\cup\mathcal{S}_{3, 3, 2}^{[\mathfrak{p}]}\cup\mathcal{S}_{3, 3, 3}^{[\mathfrak{p}]}\right)\times \lbrace \varepsilon \rbrace}\\ \end{split} \end{displaymath} where \begin{displaymath} \begin{split} \mathcal{S}_{3, 0}^{[\mathfrak{p}]}=\mathcal{S}_{0, 0, 0}^{[\mathfrak{p}]}\times\lbrace 111 \rbrace &= \lbrace \varepsilon \rbrace\times\lbrace 111 \rbrace= \{111\}\\ \mathcal{S}_{3, 1}^{[\mathfrak{p}]}={\left(\mathcal{S}_{1, 1, 0}^{[\mathfrak{p}]}\cup\mathcal{S}_{1, 1, 1}^{[\mathfrak{p}]}\right)\times \lbrace 11 \rbrace} &= \{0111\}\cup\{1011\}\\ \mathcal{S}_{3, 2}^{[\mathfrak{p}]}={\left(\mathcal{S}_{2, 2, 0}^{[\mathfrak{p}]}\cup\mathcal{S}_{2, 2, 1}^{[\mathfrak{p}]}\cup\mathcal{S}_{2, 2, 2}^{[\mathfrak{p}]}\right)\times \lbrace 1 \rbrace} &=\{00111\}\cup\{10011, 01011\}\cup\{10101\}\\ \mathcal{S}_{3, 3}^{[\mathfrak{p}]}={\left(\mathcal{S}_{3, 3, 0}^{[\mathfrak{p}]}\cup\mathcal{S}_{3, 3, 1}^{[\mathfrak{p}]}\cup\mathcal{S}_{3, 3, 2}^{[\mathfrak{p}]}\cup\mathcal{S}_{3, 3, 3}^{[\mathfrak{p}]}\right)\times \lbrace \varepsilon \rbrace} &= \{000111\}\cup\{001011, 100011, 010011\} \\ &\cup\{101001, 100101, 010101\}\cup\{101010\}, \end{split} \end{displaymath} the same set of words shown in Table \ref{tbl:S1_j1:0_j}. \begin{corollary} \label{coro:0_j1_1_j} Consider pattern $\mathfrak{p}=0^{j+1}1^{j}$. There is one word $S_{n}^{[\mathfrak{p}]} = 1$ for each $n\in\mathbb{N}$ in $\mathfrak{L}^{[\mathfrak{p}]}$ when $j=0$; on the other hand, there are $(n+2)2^{n-1}$ words for $j=1$. \end{corollary} \begin{proof} When $j=0$ the pattern to avoid is $\mathfrak{p}=0$, therefore only words $w = 1^{n}$ are suitable. Hence there is one of them for each $n\in\mathbb{N}$. When $j=1$ the pattern to avoid is $\mathfrak{p}=001$, therefore we extract the $n$-th coefficient after instantiation of the corresponding generating function: \begin{displaymath} [t^{n}] S_{n}^{[\mathfrak{p}]}(t) = [t^{n}]\frac{1-t}{(1-2t)^{2}} = (n+2)2^{n-1}, \end{displaymath} as required. We also provide a combinatorial interpretation of the theorem; first of all, we observe that sequence $S_{n}^{[\mathfrak{p}]}$ is the binomial transform of the sequence of the positive integers $(n+1)_{n\in\mathbb{N}}$, formally \begin{displaymath} S_{n}^{[\mathfrak{p}]} =(n+2)2^{n-1}= \sum_{k=0}^{n}{{ {n}\choose{k}}(k+1)}, \end{displaymath} where the generic summand ${{ {n}\choose{k}}(k+1)}$ can be interpreted as the number of binary words with $n$ $1$-bits containing $n-k$ occurrences of the substring $01$, which we call an \emph{inversion} respect to the pattern $\mathfrak{p}=001$. We construct the set of words avoiding $\mathfrak{p}$ to show the bijection with the previous assertion as follows: if in a word $w$ there are $n-k$ occurrences of the substring $01$ then $w$ contains $2n-2k$ bits in total, $n-k$ of both kinds. Since it is mandatory that the number of $1$ is $n$, we add $k$ $1$-bits to it, resulting in a new word $w'$ of length $2n-k$, which can be augmented with at most $k$ additional $0$-bits, according to the constraint $|w'|_{0}\leq |w'|_{1}$. In order to build a word with the structure of $w'$, we start from the substring $1^{n}$ and select $n-k$ $1$-bits, transforming each one using the mapping $1 \mapsto 01$, simultaneously to prevent transforming $1$-bit in $01$ just introduced. This maneuver introduces $n-k$ inversions and the selection can be done in ${{ {n}\choose{k}}}$ ways; moreover, we are free to pad on the right with $0^{i}$ strips, for $i\in\lbrace 0,\ldots,k\rbrace,$ hence there are $k+1$ paddings for each set of inversions. Therefore, since there can be up to $n$ inversions, \begin{displaymath} \sum_{k=0}^{n}{{ {n}\choose{n-k}}(k+1)} = (n+2)2^{n-1} \end{displaymath} concludes the proof by symmetry of binomial coefficients. \end{proof} \begin{corollary} Consider pattern $\mathfrak{p}=0^{j}1^{j}$ (or, equivalently, $\mathfrak{p}=1^{j}0^{j}$). There are \begin{displaymath} S_{n}^{[\mathfrak{p}]}=\sum_{k=0}^{n}{{{n+k}\choose{k}}}={{2n+1}\choose{n}} \end{displaymath} words in $\mathfrak{L}^{[\mathfrak{p}]}$ for $j=0$; on the other hand, there are $S_{n}^{[\mathfrak{p}]} = n+1$ words for $j=1$. \end{corollary} \begin{proof} When $j=0$ there is no pattern to avoid and this situation corresponds to the enumeration of binary words $\left\lbrace w\in \lbrace 0,1 \rbrace^{*}: |w|_{0} \leq |w|_{1}=n\right\rbrace$. After instantiating the generating function $S^{[\mathfrak{p}]}(t)$, we extract the $n$-th coefficient, as follows: \begin{displaymath} [t^{n}] S_{n}^{[\mathfrak{p}]}(t) =[t^{n}]\frac{1-\sqrt{1-4t}}{2t\sqrt{1-4t}} = \frac{1}{2}{{2(n+1)}\choose{n+1}} = {{2n+1}\choose{n+1}} = {{2n+1}\choose{n}}, \end{displaymath} which can be simplified by using the identity \begin{displaymath} {{r+s+1}\choose{s}} = \sum_{q=0}^{s}{{{r+q}\choose{q}}}, \end{displaymath} as desired. It is possible to state the following combinatorial interpretation: since the maximum number of $0$-bits is $n$, we reserve $n$ boxes for them. To the left of each box reserve one more box and, finally, another one to the right of the very last box. In this way we have reserved $2n+1$ boxes where we can put $n$ $1$-bits in ${{2n+1}\choose{n}}$ ways, as required. When $j=1$ the pattern to avoid is $\mathfrak{p}=01$ (or, equivalently, $\mathfrak{p}=10$), therefore only words $w \in \lbrace 1^{n} \rbrace\times\bigcup_{s\in \lbrace 0,\ldots,n \rbrace}\lbrace 0^{s} \rbrace$ are suitable, which are $n+1$, one for each value that $s$ can take. \end{proof} Last two patterns $\mathfrak{p}=(10)^{j}1$ and $\mathfrak{p}=(01)^{j}0$ are harder to study: for $j=0$ there are $S_{n}^{[\mathfrak{p}]}=[\![n=0]\!]$ and $S_{n}^{[\mathfrak{p}]}=1$ words, respectively. On the other hand, when $j=1$ we report only the instantiated generating functions \begin{displaymath} \begin{split} S^{[\mathfrak{101}]}(t) &=\frac{(1+t)\left(1-3t-\sqrt{1-2t-3t^{2}}\right)}{2t(3t-1)}, \\ S^{[\mathfrak{010}]}(t) &=\frac{1-2t-3t^{2}-(1-t)\sqrt{1-2t-3t^{2}}}{2t^{2}(3t-1)}. \end{split} \end{displaymath} As pointed out by an anonymous referee, the previous functions can be rewritten as \begin{displaymath} \begin{split} S^{[\mathfrak{101}]}(t) &=\frac{(1+t)(1- t M(t))}{1-3t},\\ S^{[\mathfrak{010}]}(t) &=\frac{(1+t M(t))(1-t M(t))}{1-3t}, \end{split} \end{displaymath} where $M(t)=\frac{1 - t - \sqrt{1-2t-3t^{2}} }{2t^{2}}$ is the Motzkin numbers' generating function. Such rewriting shows a relation among Motzkin numbers and powers of $3$, which is not easy to state bijectively, to the best of our knowledge. However, for their generating functions, we have the following identity \begin{equation} \label{powers3} {1 \over 1-3t}={M(t) \over (1-tM(t))^2}, \end{equation} and thus, by using the fundamental rule of Riordan arrays (\ref{somme}), we can express the functions $S^{[\mathfrak{101}]}(t)$ and $S^{[\mathfrak{010}]}(t)$ in terms of the Motzkin triangle and the sequence $(1,2,2,2,\ldots)$ \begin{displaymath} \begin{split} S^{[\mathfrak{101}]}(t) &=\frac{(1+t)M(t)}{1- t M(t)}=\frac{(1+tM(t))^2}{1- t M(t)}=\left(1+tM(t),tM(t) \right) \ast {1+t \over 1-t},\\ S^{[\mathfrak{010}]}(t) &=\frac{(1+tM(t))M(t)}{1- t M(t)}= \left( M(t),tM(t)\right) \ast {1+t \over 1-t}, \end{split} \end{displaymath} as illustrated in Table \ref{Motzkin}. \begin{table}[H] $$ \begin{array}{c|cccccccc} n/k & 0 & 1 & 2 & 3 & 4 &5 &6 &7 \\ \cline{1-9} 0 & 1 & & & & & & &\\ 1 & 1 & 1 & & & & & &\\ 2 & 2& 2 & 1 & & & & &\\ 3 & 4 & 5 & 3 & 1 & & & &\\ 4 & 9 & 12 & 9 & 4 & 1& & & \\ 5 & 21 & 30 & 25 & 14 & 5 &1 & &\\ 6 & 51 & 76 & 69 & 44 & 20 & 6& 1 &\\ 7 & 127 & 196 & 189 & 133 & 70 & 27& 7 &1\\ \end{array} $$ \caption{\label{Motzkin}The Motzkin triangle corresponding to the Riordan array $\left(M(t),tM(t)\right)$ and to sequence \seqnum{A064189}. Multiplying the matrix by the column vector $(1,2,2,2,2,\ldots )$ we get the sequence $S_{n}^{[\mathfrak{010}]}=(1,3,8,22,61, \cdots)$. Similarly, with matrix $\left(1+tM(t),tM(t)\right)$ we get the sequence $S_{n}^{[\mathfrak{101}]}=(1, 3, 7, 18, 48, \cdots)$. } \end{table} Identity (\ref{powers3}) has a combinatorial interpretation in terms of compact-rooted directed animals or domino towers (see Ardila \cite[Example 21, pp.~21--22]{Ardila} and the references therein); Motzkin triangle corresponds to sequence \seqnum{A064189} and has several combinatorial interpretations. \subsection{Enumeration with respect to the length} \begin{corollary} Consider pattern $\mathfrak{p}=1^{j+1}0^{j}$. There is one word in $\mathfrak{L}^{[\mathfrak{p}]}$ for $j=0$; on the other hand, there are $2^{m+1}-1$ words, where $n=2m + [\![\text{n is odd}]\!]$, for $j=1$. \end{corollary} \begin{proof} When $j=0$ the pattern to avoid is $\mathfrak{p}=1$, therefore instantiating the generating function we have $L^{[\mathfrak{p}]}(t) = 1$, as required. When $j=1$ the pattern to avoid is $\mathfrak{p}=110$, therefore we instantiate and extract the $n$-th coefficient \begin{displaymath} L_{n}^{[\mathfrak{p}]} = [t^{n}]\frac{2}{1-2t^{2}} + [t^{n-1}]\frac{2}{1-2t^{2}} - [t^{n}]\frac{1}{1-t} \end{displaymath} and proceed by cases on the parity of $n$. If $n=2m$ then the second term in the rhs disappears, otherwise if $n=2m+1$ the first term disappears; in both cases it is required to perform $[u^{m}]\frac{2}{1-2u} = 2^{m+1}$ where $u=t^{2}$, as required. It is possible to state a combinatorial interpretation using an argument similar to the one given in the proof of Corollary \ref{coro:1_j1_0_j}. Let $n=2m$, therefore a word $w$ needs to have $m+j$ $1$-bits, where $j\in \lbrace 0,\ldots,m \rbrace$; conversely, $w$ needs to have $n-m-j=m-j$ $0$-bits. Fixing $j$ in the given range, from the substring $0^{m-j}$ we select $i\in \lbrace 0,\ldots,m-j \rbrace$ $0$-bits to introduce $i$ inversions, namely $i$ occurrences of $10$, applying the mapping $0\mapsto 10$ simultaneously. This maneuver keeps the original $0$-bits and introduces at most $m-j$ $1$-bits, so we pad with $1$-bits on the right in order to have the required $m+j$ $1$-bits in the entire word; finally, selections can be done in \begin{displaymath} \sum_{j=0}^{m}{\sum_{i=0}^{m-j}{ {{m-j}\choose{i}}} } = \sum_{j=0}^{m}{2^{m-j}} = 2^{m+1}-1 \end{displaymath} ways, because padding can be done in only one way, completing the case for $n$ even. Let $n=2m+1$, therefore a word $w$ needs to have $m+1+j$ $1$-bits, where $j\in \lbrace 0,\ldots,m \rbrace$; conversely, $w$ needs to have $n-m-1-j=m-j$ $0$-bits. Fixing $j$ in the given range, from the substring $0^{m-j}$ we select $i\in \lbrace 0,\ldots,m-j \rbrace$ $0$-bits to introduce $i$ inversions as done in the even case, introducing at most $m-j$ $1$-bits, and padding as necessary to have $m+1+j$ $1$-bits, the total number of selections %\begin{displaymath} %\sum_{j=0}^{m}{\sum_{i=0}^{m-j}{ {{m-j}\choose{i}}} } = %\sum_{j=0}^{m}{2^{m-j}} = %2^{m+1}-1 %\end{displaymath} equals the one given for the even case, completing the case for $n$ odd. \end{proof} \begin{corollary} Consider pattern $\mathfrak{p}=0^{j+1}1^{j}$. There is one word $L_{n}^{[\mathfrak{p}]} = 1$ for each $n\in\mathbb{N}$ in $\mathfrak{L}^{[\mathfrak{p}]}$ when $j=0$; on the other hand, there are $L_{n}^{[\mathfrak{p}]} = F_{n+3}-2^{m}$ words if $n=2m$ else $L_{n}^{[\mathfrak{p}]} = F_{n+3}-2^{m+1}$ words if $n=2m+1$, for $j=1$, where $F_{n}$ is the $n$-th Fibonacci number. \end{corollary} \begin{proof} When $j=0$ the pattern to avoid is $\mathfrak{p}=0$, therefore suitable words of length $n$ are of the form $w=1^{n}$. Hence $L_{n}^{[\mathfrak{p}]} = 1$ for each $n\in\mathbb{N}$. When $j=1$ the pattern to avoid is $\mathfrak{p}=001$, therefore we instantiate and extract the $n$-th coefficient \begin{displaymath} L_{n}^{[\mathfrak{p}]} = 2[t^{n+1}]\frac{t}{1-t-t^{2}} + [t^{n}]\frac{t}{1-t-t^{2}} - [t^{n}]\frac{1}{1-2t^{2}} - 2[t^{n-1}]\frac{1}{1-2t^{2}} \end{displaymath} in order to have $L_{n}^{[\mathfrak{p}]} = 2F_{n+1} + F_{n} - a_{n} = F_{n+3} - a_{n}$, where $a_{2m}=2^{m}$ and $a_{2m+1}=2^{m+1}$. It is possible to state a combinatorial interpretation using an argument similar to the one given in the proof of Corollary \ref{coro:0_j1_1_j}. Let $n=2m$, therefore a word $w$ needs to have $m+j$ $1$-bits, where $j\in \lbrace 0,\ldots,m \rbrace$; conversely, $w$ needs to have $n-m-j=m-j$ $0$-bits. Fixing $j$ in the given range, from the substring $1^{m+j}$ we select $i\in \lbrace 0,\ldots,m-j \rbrace$ $1$-bits to introduce $i$ inversions, namely $i$ occurrences of $01$, applying the mapping $1\mapsto 01$ simultaneously. This maneuver keeps the original $1$-bits and introduces at most $m-j$ $0$-bits; finally, selections can be done in $\sum_{j=0}^{m}{\sum_{i=0}^{m-j}{ {{m+j}\choose{i}}} } $ ways. In order to find a closed form for the double summation, we inspect the region of the Pascal triangle taken into account; marking with $\circ$ the involved binomials \begin{displaymath} \begin{array}{c|cccccccccc} n/j & 0 & 1 & \ldots & m-1 & m & m+1 & \ldots & 2m-1 & 2m & \ldots\\ \hline 0 & \\ \vdots & \\ m-1 & \\ m & \circ & \circ & \ldots & \circ & \circ \\ m+1 & \circ & \circ & \ldots & \circ \\ \vdots & \vdots & \vdots & \iddots \\ 2m-1 & \circ & \circ \\ 2m & \circ \\ 2m+1 & \\ \vdots & \\ \end{array} \end{displaymath} and using the identity ${ {r+1}\choose{k+1} }-{ {s}\choose{k+1} } = \sum_{i=s}^{r}{{ {i}\choose{k} }}$ for rearranging the summation and identities $2^{n}=\sum_{i=0}^{n}{{ {n}\choose{i} }}$ and $F_{n+1}=\sum_{i=0}^{n}{{ {n-i}\choose{i} }}$ to collect terms, we obtain \begin{displaymath} \sum_{j=0}^{m}{\sum_{i=0}^{m-j}{ {{m+j}\choose{i}}} } = \sum_{k=0}^{m}{{ {2m+1-k}\choose{k+1} }-{ {m}\choose{k+1} }} = F_{2m+3}-2^{m} = L_{2m}^{[\mathfrak{p}]}, \end{displaymath} completing the case for $n$ even. Let $n=2m+1$, therefore a word $w$ needs to have $m+1+j$ $1$-bits, where $j\in \lbrace 0,\ldots,m \rbrace$; conversely, $w$ needs to have $n-m-1-j=m-j$ $0$-bits. Fixing $j$ in the given range, from the substring $1^{m+1+j}$ select $i\in \lbrace 0,\ldots,m-j \rbrace$ $1$-bits to introduce $i$ inversions as done for the even case; in parallel, selections can be done in $ \sum_{j=0}^{m}{\sum_{i=0}^{m-j}{ {{m+1+j}\choose{i}}} } $ ways. The involved region in the Pascal triangle has the same shape as the one shown for the even case translated one row to the bottom, so binomials lying on row $m$ are excluded and binomials ${ {2m+1-k}\choose{k} }$ are included, for $k\in \lbrace 0, \ldots, m \rbrace$. Therefore we rewrite \begin{displaymath} \sum_{j=0}^{m}{\sum_{i=0}^{m-j}{ {{m+1+j}\choose{i}}} } = \sum_{k=0}^{m}{{ {2m+2-k}\choose{k+1} }-{ {m+1}\choose{k+1} }} = F_{2m+4}-2^{m+1} = L_{2m+1}^{[\mathfrak{p}]}, \end{displaymath} completing the case for $n$ odd. \end{proof} \begin{corollary} Consider pattern $\mathfrak{p}=0^{j}1^{j}$ (or, equivalently, $\mathfrak{p}=1^{j}0^{j}$). There are $2^{n-1}$ words in $\mathfrak{L}^{[\mathfrak{p}]}$ if $n$ is odd else $2^{n-1} +\frac{1}{2}{{2m}\choose{m}}$ where $n=2m$, for $j=0$; on the other hand, there are $L_{n}^{[\mathfrak{p}]} = m+1$ words, where $n=2m + [\![\text{n is odd}]\!]$, for $j=1$. \end{corollary} \begin{proof} When $j=0$ the pattern to avoid is $\mathfrak{p}=\varepsilon $, namely the empty word, therefore instantiating the generating function we have \begin{displaymath} L^{[\mathfrak{p}]}(t) =\frac{1}{2(1-2t)} +\frac{1}{2\sqrt{1-4t^{2}}} \end{displaymath} we extract the coefficient $L_{n}^{[\mathfrak{p}]} = 2^{n-1} + \frac{a_{n}}{2}$, where $a_{2m+1}=0$ and $a_{2m}={{2m}\choose{m}}$, as required. We observe that these values correspond to the summation $\sum_{i=0}^m {n \choose i}$ for $n=2m,2m+1,\ldots,$ where the binomial coefficient computes the number of ways to choose $i$ $0$-bits among $n$ bits, and this gives the combinatorial interpretation. When $j=1$ the pattern to avoid is $\mathfrak{p}=01$ (or, equivalently, $\mathfrak{p}=10$), therefore after instantiation \begin{displaymath} L^{[\mathfrak{p}]}(t) =\frac{1}{4(1-t)} + \frac{1}{2(1-t)^{2}} +\frac{1}{4(1+t)} \end{displaymath} we extract the $n$-th coefficient $L_{n}^{[\mathfrak{p}]} = \frac{1}{4} + \frac{(-1)^{n}}{4} +\frac{n+1}{2} $, so either $n=2m$ or $n=2m+1$ entails $L_{n}^{[\mathfrak{p}]} = m+1$, as required. A combinatorial interpretation can be given as follows: if $n=2m$ then suitable words have structure $1^{m}1^{j}0^{m-j}$ for $j\in \lbrace 0, \ldots,m \rbrace$, and there are $m+1$ of them. On the contrary, if $n=2m+1$ holds then suitable words have structure $1^{m+1}1^{j}0^{m-j}$ for $j\in \lbrace 0, \ldots,m \rbrace$, they are $m+1$ in number again, as required. \end{proof} As before, last two patterns $\mathfrak{p}=(01)^{j}0$ and $\mathfrak{p}=(10)^{j}1$ are harder to study and we avoid to report formulas about $L^{[\mathfrak{p}]}(t)$ functions because we have not a meaningful combinatorial interpretation: we only point out that these functions can be expressed in terms of $M(t^{2})$, where $M(t)$ is the generating function of Motzkin numbers, similarly to the corresponding $S^{[\mathfrak{p}]}(t)$ functions. \section{Conclusions} As a final remark, we observe a structural properties of matrices $\mathcal{R}^{[\mathfrak{p}]}$ against the studied families of patterns. As it is well-known (see, e.g., Shapiro, Getu, Woan, and Woodson \cite{SGWW91}), Riordan arrays constitute a group with respect to the usual row-by-column product between matrices, and the product of two Riordan arrays $D_1$ and $D_2$ is defined as follows: $$ D_1 \ast D_2 = (d_1(t),\ h_1(t)) \ast (d_2(t),\ h_2(t)) =(d_1(t)d_2(h_1(t)),\ h_2(h_1(t))). $$ Moreover, the Riordan array $I = (1,\ t)$ acts as the identity and the inverse of $D =(d(t), h(t))$ is the Riordan array: $$ D^{-1} = \left( \frac{1}{d(\overline{h}(t))}, \overline{h}(t) \right) $$ where $\overline{h}(t)$ is the compositional inverse of $h(t)$. The Pascal triangle and its inverse correspond to the Riordan arrays $$P =\left(\frac{1}{1-t},\frac{t}{1-t}\right) \quad\quad P^{-1}=\left(\frac{1}{1+t},\frac{t}{1+t}\right)$$ respectively. Therefore, for every Riordan array $\mathcal{R}^{[\mathfrak{p}]}$ we can compute $B^{[\mathfrak{p}]}= P^{-1} \ast \mathcal{R}^{[\mathfrak{p}]},$, which is equivalent to saying that $\mathcal{R}^{[\mathfrak{p}]}$ is the binomial transform of $B^{[\mathfrak{p}]},$ or $\mathcal{R}^{[\mathfrak{p}]}=P \ast B^{[\mathfrak{p}]}$. For the sake of clarity, consider the pattern family $\mathfrak{p}=1^{j+1}0^{j}$, so for $j=1$ we have the minor \begin{displaymath} \mathcal{R}^{[110]} = \left[\begin{array}{ccccccccccc}1 & & & & & & & & & & \\2 & 1 & & & & & & & & & \\4 & 2 & 1 & & & & & & & & \\8 & 4 & 2 & 1 & & & & & & & \\16 & 8 & 4 & 2 & 1 & & & & & & \\32 & 16 & 8 & 4 & 2 & 1 & & & & & \\64 & 32 & 16 & 8 & 4 & 2 & 1 & & & & \\128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 & & & \\256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 & & \\512 & 256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 & \\1024 & 512 & 256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1\end{array}\right], \end{displaymath} which corresponds to \begin{displaymath} B^{[110]} = \left[\begin{array}{ccccccccccc} 1 & & & & & & & & & & \\ 1 & 1 & & & & & & & & & \\ 1 & 0 & 1 & & & & & & & & \\ 1 & 1 & -1 & 1 & & & & & & & \\ 1 & 0 & 2 & -2 & 1 & & & & & & \\ 1 & 1 & -2 & 4 & -3 & 1 & & & & & \\ 1 & 0 & 3 & -6 & 7 & -4 & 1 & & & & \\ 1 & 1 & -3 & 9 & -13 & 11 & -5 & 1 & & & \\ 1 & 0 & 4 & -12 & 22 & -24 & 16 & -6 & 1 & & \\ 1 & 1 & -4 & 16 & -34 & 46 & -40 & 22 & -7 & 1 & \\ 1 & 0 & 5 & -20 & 50 & -80 & 86 & -62 & 29 & -8 & 1\end{array}\right] \end{displaymath} defined by functions $d^{[110]}(t)=\frac{1}{1-t}$ and $h^{[110]}(t)=\frac{t}{1+t}$, which expands to $h^{[110]}(t) = t - t^{2} + t^{3} - t^{4} + t^{5} - t^{6} + t^{7} - t^{8} + t^{9} - t^{10} + \mathcal{O}\left(t^{11}\right)$. On the other hand, the Riordan array $\mathcal{R}^{[11100]}$, that is $j=2$ in the family, is the binomial transform of \begin{displaymath} B^{[11100]} =\left[\begin{array}{ccccccccccc}1 & & & & & & & & & & \\1 & 1 & & & & & & & & & \\3 & 1 & 1 & & & & & & & & \\5 & 3 & 1 & 1 & & & & & & & \\15 & 7 & 3 & 1 & 1 & & & & & & \\31 & 16 & 9 & 3 & 1 & 1 & & & & & \\87 & 43 & 17 & 11 & 3 & 1 & 1 & & & & \\201 & 101 & 55 & 18 & 13 & 3 & 1 & 1 & & & \\543 & 271 & 119 & 67 & 19 & 15 & 3 & 1 & 1 & & \\1331 & 666 & 341 & 141 & 79 & 20 & 17 & 3 & 1 & 1 & \\3533 & 1766 & 826 & 411 & 167 & 91 & 21 & 19 & 3 & 1 & 1\end{array}\right] \end{displaymath} defined by functions $d^{[11100]}(t)=\sqrt\frac{1+t}{1-t-5t^{2}+t^{3}}$ and $h^{[11100]}(t)=\frac{1+2t+t^{2}-\sqrt{(1-t-5t^{2}+t^{3})(1+t)}}{2(1+t)^{2}}$, which expands to $h^{[11100]}(t)=t + 2 t^{4} - t^{5} + 7 t^{6} + 24 t^{8} + 17 t^{9} + 98 t^{10} + \mathcal{O}\left(t^{11}\right)$. \iffalse Furthermore, the Riordan array $\mathcal{R}^{[1111000]}$, that is $j=3$ in the family, is the binomial transform of \begin{displaymath} B^{[1111000]} =\left[\begin{array}{ccccccccccc}1 & & & & & & & & & & \\1 & 1 & & & & & & & & & \\3 & 1 & 1 & & & & & & & & \\7 & 4 & 1 & 1 & & & & & & & \\17 & 8 & 5 & 1 & 1 & & & & & & \\49 & 25 & 9 & 6 & 1 & 1 & & & & & \\123 & 61 & 34 & 10 & 7 & 1 & 1 & & & & \\351 & 176 & 74 & 44 & 11 & 8 & 1 & 1 & & & \\945 & 472 & 242 & 88 & 55 & 12 & 9 & 1 & 1 & & \\2641 & 1321 & 610 & 322 & 103 & 67 & 13 & 10 & 1 & 1 & \\7363 & 3681 & 1811 & 766 & 417 & 119 & 80 & 14 & 11 & 1 & 1\end{array}\right] \end{displaymath} \fi Riordan arrays $B^{[\mathfrak{p}]}$ can be completely defined by using the results of Theorem \ref{teo1} and the product rule of the Riordan group. Doing so, for each pattern family studied in this work with $j>1$, the Riordan array $\mathcal{R}^{[\mathfrak{p}]}$ appears to be the binomial transform of another Riordan array $B^{[\mathfrak{p}]}$ with non-negative integer coefficients, although it is not easy to spot this property looking at the corresponding $h$ functions because their series expansions might contain negative coefficients, as shown for matrices $B^{[110]}$ and $B^{[11100]}$. This fact could be further investigated from an algebraic and combinatorial point of view and possibly yield interesting combinatorial interpretations also in the case $j>1$. \section{Acknowledgements} We wish to thank the editor-in-chief and the referee(s) for the thoughtful and helpful comments and suggestions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{thebibliography}{10} \bibitem{Ardila} F. Ardila. Algebraic and geometric methods in enumerative combinatorics, in M. B\'{o}na, eds., {\em Handbook of Enumerative Combinatorics}, Chapman and Hall/CRC, 2015, pp.~3--172. \bibitem{BMS07a} D.~Baccherini, D.~Merlini, and R.~Sprugnoli, Binary words excluding a pattern and proper {R}iordan arrays, {\em Discrete Math.} {\bf 307} (2007), 1021--1037. \bibitem{BGP13} S.~Bilotta, E.~Grazzini, and E.~Pergola, Counting binary words avoiding alternating patterns, {\em J. Integer Seq.} {\bf 16} (2013), \href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Grazzini/grazzini2.html}{Article 13.4.8}. \bibitem{GO80} L.~J. Guibas and M.~Odlyzko, Long repetitive patterns in random sequences, {\em Zeitschrift f\"{u}r Wahrscheinlichkeitstheorie} {\bf 53} (1980), 241--262. \bibitem{GO81} L.~J. Guibas and M.~Odlyzko, String overlaps, pattern matching, and nontransitive games, {\em J. Combin. Theory Ser. A} {\bf 30} (1981), 183--208. \bibitem{OEIS} OEIS~Foundation Inc., The {O}n-line {E}ncyclopedia of {I}nteger {S}equences, \url{https://oeis.org/}. \bibitem{LMMS14} A.~Luz\'on, D.~Merlini, M.~A. Mor\'on, and R.~Sprugnoli, Complementary {R}iordan arrays, {\em Discrete Appl. Math.} {\bf 172} (2014), 75--87. \bibitem{MRSV97} D.~Merlini, D.~G. Rogers, R.~Sprugnoli, and M.~C. Verri, On some alternative characterizations of {R}iordan arrays, {\em Canad. J. Math.} {\bf 49} (1997), 301--320. \bibitem{MS11} D.~Merlini and R.~Sprugnoli, {Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern}, {\em Theoret. Comput. Sci.} {\bf 412} (2011), 2988--3001. \bibitem{MSV09} D.~Merlini, R.~Sprugnoli, and M.~C. Verri, Combinatorial sums and implicit {R}iordan arrays, {\em Discrete Math.} {\bf 309} (2009), 475--486. \bibitem{SF96} R.~Sedgewick and P.~Flajolet, {\em An {I}ntroduction to the {A}nalysis of {A}lgorithms}, Addison-Wesley, Reading, MA, 1996. \bibitem{SGWW91} L.~W. Shapiro, S.~Getu, W.-J. Woan, and L.~Woodson, The {R}iordan group, {\em Discrete Appl. Math.} {\bf 34} (1991), 229--239. \bibitem{Spr94} R.~Sprugnoli, Riordan arrays and combinatorial sums, {\em Discrete Math.} {\bf 132} (1994), 267--290. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A05; Secondary 05A15, 05A19. \noindent {\it Keywords}: Riordan array, language avoiding pattern, generating function. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000225}, \seqnum{A001477}, \seqnum{A001700}, \seqnum{A001792}, \seqnum{A008619}, \seqnum{A025566}, \seqnum{A027306}, \seqnum{A052551}, \seqnum{A064189}, \seqnum{A079284}, \seqnum{A225034}, and \seqnum{A261058}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 20 2017; revised versions received January 24 2017; September 22 2017; November 7 2017; December 22 2017. Published in {\it Journal of Integer Sequences}, January 21 2018. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}