2019/08/11 by Bloom, Jonathan, McNew, Nathan
#05A17 11P72 11P82 05A15 #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.1908.03953
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.