Enumeration of words with forbidden patterns

Abstract

For any $j\\in{\\rm I\\!N},$ define $\\lbrack j\\rbrack$ to be a totally ordered set $\\{1,2,\\...,j\\}.$ A word $\\sigma\\in\\lbrack k\\rbrack\\sp{n}$ (i.e. an n-letter word over a totally ordered k-letter alphabet) avoids a word $\\tau\\in\\lbrack\\ell\\rbrack\\sp{m}$ iff there is no $1\\leq i\\sb1<\\...