Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3

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


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