##
**
Algebraic Generating Functions for Languages Avoiding Riordan Patterns
**

###
Donatella Merlini and Massimo Nocentini

Dipartimento di Statistica, Informatica, Applicazioni Università di Firenze

viale Morgagni 65

50134 Firenze

Italia

**Abstract:**

We study the languages 𝔏^{𝔭} ⊂ {0,1}^{*} of
binary words *w* avoiding a given pattern
𝔭 such that |*w*|_{0} ≤ |*w*|_{1}
for every *w* ∈ 𝔏^{𝔭}, 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 𝔭 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
𝔭, and also give explicit formulas for the coefficients of some
particular patterns, algebraically and combinatorially.

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequences
A000225
A001477
A001700
A001792
A008619
A025566
A027306
A052551
A064189
A079284
A225034
A261058.)

Received January 20 2017; revised versions received January 24 2017; September 22 2017; November 7 2017; December 22 2017.
Published in *Journal of Integer Sequences*, January 21 2018.

Return to
**Journal of Integer Sequences home page**