pith. sign in

arxiv: 1712.08662 · v1 · pith:KADWPMG3new · submitted 2017-12-22 · 🧮 math.CO

Enumeration of words that contain the pattern 123 exactly once

classification 🧮 math.CO
keywords wordsexactlypatterncontainenumeratingonceavoidingenumeration
0
0 comments X
read the original abstract

Enumeration problems related to words avoiding patterns as well as permutations that contain the pattern $123$ exactly once have been studied in great detail. However, the problem of enumerating words that contain the pattern $123$ exactly once is new and will be the focus of this paper. Previously, Doron Zeilberger provided a shortened version of Alexander Burstein's combinatorial proof of John Noonan's theorem that the number of permutations with exactly one $321$ pattern is equal to $\frac{3}{n} \binom{2n}{n+3}$. Surprisingly, a similar method can be directly adapted to words. We are able to use this method to find a formula enumerating the words with exactly one $123$ pattern. Further inspired by Nathaniel Shar and Zeilberger's paper on generating functions enumerating 123-avoiding words with $r$ occurrences of each letter, we examine the algebraic equations for generating functions for words with $r$ occurrences of each letter and with exactly one $123$ pattern.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.