Finite State Machines and Bounded Permutations

Eric Redmon
Graduate Student
Marquette University

We define a k-bounded permutation π of length n to be a permutation such that for each pair of adjacent entries $\pi$ and $\pi(i + 1)$ for $i = 1, 2, 3, . . . , n − 1$ we have $|\pi(i) − \pi(i + 1)| \leq k$. Previous work has shown that the generating function for this family of permutations is rational, and has computed generating functions for small values of $k$. In this talk, we will discuss the nature of finite state machines and how we can leverage the insertion encoding devised by Albert, Linton, and Ruškuc to build a finite state machine that we can use to find generating functions for larger values of $k$.