The (Ordinary) Generating Functions Enumerating 123-Avoiding Words with r Occurrences of Each of 1, 2,.. , n Are Always Algebraic

The set of 123-avoiding permutations (alias words in {1 , … , n} with exactly 1 occurrence of each letter) is famously enumerated by the ubiquitous Catalan numbers, whose generating function C(x) famously satisfies the algebraic equation C( x) = 1 + xC( x) ². Recently, Bill Chen, Alvin Dai, and Robin Zhou found (and very elegantly proved) an algebraic equation satisfied by the generating function enumerating 123-avoiding words with two occurrences of each of {1 , … , n}. Inspired by the Chen-Dai-Zhou result, we present an algorithm for finding such an algebraic equation for the ordinary generating function enumerating 123- avoiding words with exactly r occurrences of each of { 1 , … , n} for any positive integer r, thereby proving that they are algebraic, and not merely D-finite (a fact that is promised by WZ theory). Our algorithm consists of presenting an algebraic enumeration scheme, combined with the Buchberger algorithm.