### 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 language | English (US) |
---|---|

Pages (from-to) | 387-396 |

Number of pages | 10 |

Journal | Annals of Combinatorics |

Volume | 20 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1 2016 |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics

### Keywords

- algebraic generating functions
- pattern avoidance
- words