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 -