Paper detail

Counting pattern-avoiding integer partitions

A partition $α$ is said to contain another partition (or pattern) $μ$ if the Ferrers board for $μ$ is attainable from $α$ under removal of rows and columns. We say $α$ avoids $μ$ if it does not contain $μ$. In this paper we count the number of partitions of $n$ avoiding a fixed pattern $μ$, in terms of generating functions and their asymptotic growth rates. We find that the generating function for this count is rational whenever $μ$ is (rook equivalent to) a partition in which any two part sizes differ by at least two. In doing so, we find a surprising connection to metacyclic $p$-groups. We further obtain asymptotics for the number of partitions of $n$ avoiding a pattern $μ$. Using these asymptotics we conclude that the generating function for $μ$ is not algebraic whenever $μ$ is rook equivalent to a partition with distinct parts whose first two parts are positive and differ by 1.