Enumeration of Gap-Bounded Set Partitions

We count set partitions in which the gaps between adjacent elements in a block are bounded from above by an integer m > 0, also known as m-gap-bounded partitions. This problem is harder than known cases in which lower bounds of the gaps are fixed. Our main results rely on the techniques of finite automata theory. First we obtain a general construct for the generating function for the number of m-gap-bounded partitions of {1, 2,..., n} and show that it is rational in its variable. This is followed with a sequence of explicit generating function formulas for certain values of m. Finally, we extend our results to partitions with a given number of blocks.