TY - JOUR
TI - An experimental walk in patterns, partitions, and words
DO - https://doi.org/doi:10.7282/t3-d9z1-aw94
PY - 2020
AB - Experimental mathematics, broadly speaking, is the philosophy that computers are a valuable tool that should be used extensively in mathematical research. This thesis explores topics related to partitions, patterns and words, incorporating the spirit of experimental math. There are four main projects in this thesis, and we will take a walk from the least experimental to the most experimental.
In the first project, we extend Shar and Zeilberger's work on generating functions enumerating 123-avoiding words (with r-occurrences of each letter) to words (with r-occurrences of each letter) having exactly one 123 pattern. After a system of equations has been established (by human means), we use computer to find the defining algebraic equation for generating functions for words with r occurrences of each letter and with exactly one 123 pattern, and derive relevant recurrences.
Next, we move on to explore consecutive pattern avoidance, in particular, words that avoid the increasing consecutive pattern 12...r for any r >= 2. We use computer to conjecture the corresponding generating function and then tweak the Goulden--Jackson cluster method to prove the result by human means. We also treat the more general case of counting words with a specified number of the pattern of interest.
After these, we dive into the world of partitions. More precisely, we introduce the combinatorial object which we call "relaxed partitions''. A relaxed partition of a positive integer n is a finite sequence of positive integers λ_1, λ_2, ..., λ_k (λ_i-λ_{i+1}>=r) whose sum is equal to n, where r is allowed to be negative (note that if we only allow r to be non-negative, then we get traditional partitions). We use computer to conjecture and prove the formula for the number of r-partitions (r<0) with fixed first part and number of parts. We also use computer to explore corresponding generating functions.
Last but not least, we go back to traditional partitions and design an efficient algorithm to count restricted partitions. We start out with a more basic algorithm and then generalize it to account for more complicated partitions, like in the Kanade-Russell conjectures. We then make use of Frank Garvan's qseries Maple package and Amarel cluster computing to search for new partition identities. Many new identities have been discovered and (at least) one of them generalizes to an infinite family.
KW - Experimental math
KW - Mathematics
LA - English
ER -