TY - JOUR

T1 - A Pentagonal Number Sieve

AU - Corteel, Sylvie

AU - Savage, Carla D.

AU - Wilf, Herbert S.

AU - Zeilberger, Doron

N1 - Funding Information:
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. 1998 Academic Press * Supported in part by NSF grant DMS9302505. -Supported in part by NSF grant DMS9622772. Supported in part by the Office of Naval Research. 9Supported in part by the National Science Foundation.

PY - 1998/5

Y1 - 1998/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0040088627&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0040088627&partnerID=8YFLogxK

U2 - 10.1006/jcta.1997.2846

DO - 10.1006/jcta.1997.2846

M3 - Article

AN - SCOPUS:0040088627

SN - 0097-3165

VL - 82

SP - 186

EP - 192

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 2

ER -