A Pentagonal Number Sieve

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., t...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series A 1998-05, Vol.82 (2), p.186-192
Main Authors: Corteel, Sylvie, Savage, Carla D, Wilf, Herbert S, Zeilberger, Doron
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-3165
1096-0899
DOI:10.1006/jcta.1997.2846