A PENTAGONAL NUMBER SIEVE

We prove a general ''pentagonal sieve'' theorem that has corollaries s uch as the following. First, the number of pairs of partitions of n th at have no parts in common is p(n)(2) - p(n - 1)(2) - p(n - 2)(2) + p( n - 5)(2) + p((n) double over dot - 7)(2) - ... Second, if two unlabel ed 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, if f, g are two monic polynomials of the same degree over the field G F(q), then the probability that f, g are relatively prime is 1 - 1/q. We give explicit involutions for the pentagonal sieve theorem, general izing earlier mappings found by Bressoud and Zeilberger. (C) 1998 Acad emic Press.