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

Nathaniel Shar, Doron Zeilberger

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)387-396
Number of pages10
JournalAnnals of Combinatorics
Volume20
Issue number2
DOIs
StatePublished - Jun 1 2016

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Keywords

  • algebraic generating functions
  • pattern avoidance
  • words

Fingerprint Dive into the research topics of 'The (Ordinary) Generating Functions Enumerating 123-Avoiding Words with r Occurrences of Each of 1, 2,.. , n Are Always Algebraic'. Together they form a unique fingerprint.

  • Cite this