A Pentagonal Number Sieve

Sylvie Corteel, Carla D. Savage, Herbert S. Wilf, Doron Zeilberger

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)186-192
Number of pages7
JournalJournal of Combinatorial Theory. Series A
Issue number2
StatePublished - May 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'A Pentagonal Number Sieve'. Together they form a unique fingerprint.

Cite this