First Written: November 8, 2018; This version: November 8, 2018.

Abstract: We find finite-state recurrences to enumerate the words on the alphabet [n]^r which avoid the patterns 123 and 1k(k-1)...2, and separately, the words which avoid the patterns 1234 and 1k(k-1)...2.

Maple packages

• 123Avoid.txt, a Maple package to enumerate the words avoiding 123 and 1k(k-1)...2

• 1234Avoid.txt, a Maple package to enumerate the words avoiding 1234 and 1k(k-1)...2

• 123Recurrences.txt, a Maple package to use recurrences to rigorously compute generating functions for the enumeration sequences of words on [n]^r avoiding 123 and 1k(k-1)...2,

• Note: In order to guess generating functions in 123Avoid and 1234Avoid, you also need the following package written by Doron Zeilberger: Cfinite. If you don't want to guess these generating functions, you can simply delete the line "read `Cfinite`:" from the beginning of 123Avoid and 1234Avoid instead.

Sample Input and Output

• For the first 8 terms of the enumeration sequence for words on [n]^2 avoiding 1234 and 15432,

  the input file generates the output file.

• For the first 10 terms of the enumeration sequences for words on [n] avoiding 1234 and 1k(k-1)...2 for k=3...10,

  the input file generates the output file.

• For the first 16 terms of the enumeration sequence for words on [n] avoiding 1234 and 15432,

  the input file generates the output file.

• For the generating functions of the enumeration sequences of words on [n]^3 avoiding 123 and 1k(k-1)...2,

  the input file generates the output file.

• For the first 10 terms of the sequences of words on [n]^r avoiding 1234 and 1k(k-1)...2, for r=1,2 and k=3,4,5 (except r=2 and k=5),

  the input file generates the output file.