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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics