Words over a finite alphabet avoiding 1243

Abstract

In this paper, we establish a system of recurrence relations and an algorithm for finding the generating function A_k(x) for the number of words over alphabet [k] of length n that avoid 1243, for arbitrary k. In particular, we present an explicit formula for the generating function _Ak(x) for 1 ≤ k ≤ 10.