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 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 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, if f, g are two monic polynomials of the same degree over the field GF(q), then the probability that f, g are relatively prime is 1 - 1/q. We give explicit involutions for the pentagonal sieve theorem, generalizing earlier mappings found by Bressoud and Zeilberger. (C) 1998 Academic Press. [References: 5]
展开▼
