TY - JOUR

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

AU - Shar, Nathaniel

AU - Zeilberger, Doron

N1 - Publisher Copyright:
© 2016, Springer International Publishing.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - 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) 2. 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.

AB - 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) 2. 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.

KW - algebraic generating functions

KW - pattern avoidance

KW - words

UR - http://www.scopus.com/inward/record.url?scp=84961200471&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961200471&partnerID=8YFLogxK

U2 - 10.1007/s00026-016-0308-y

DO - 10.1007/s00026-016-0308-y

M3 - Article

AN - SCOPUS:84961200471

VL - 20

SP - 387

EP - 396

JO - Annals of Combinatorics

JF - Annals of Combinatorics

SN - 0218-0006

IS - 2

ER -