A Pentagonal Number Sieve

Abstract

We prove a general “pentagonal sieve” theorem that has corollaries such as the following. First, the number of pairs of partitions of n that have no parts in common isp(n)2−p(n−1)2−p(n−2)2+p(n−5)2+p(n−7)2−….Second, if two unlabeled rooted forests of the same number of vertices are chosen i.u.a.r., then the probability that they have no common tree is .8705… . Third, iff,gare two monic polynomials of the same degree over the fieldGF(q), then the probability thatf,gare relatively prime is 1−1/q. We give explicit involutions for the pentagonal sieve theorem, generalizing earlier mappings found by Bressoud and Zeilberger.