Words over a finite alphabet avoiding 1243 (Q6618737)

In this paper, the author establishes a system of recurrence relations for the generating function \(A_k(x)\) for the number of words over the alphabet \(\{1,2,\dots,k\}\) of length \(n\) that avoid the pattern \(1243\). It is shown how these recurrence relations can be derived in a systematic manner, and solved using the kernel method, to give an algorithm to compute \(A_k(x)\) for arbitrary \(k\). In particular, explicit values of these generating functions are presented for \(k\le 10\).