How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?

By Doron Zeilberger

Exclusive for the Personal Journal of Ekhad and Zeilberger

Written: July 5, 2001

Last update of this page (but not article): May 8, 2012 (thanks to Holger DAMBECK)

.tex    .ps    .pdf

I just came from a visit to that Mecca of Classical Combinatorics called Strasbourg, where I had interesting discussions with Dominique Foata and his two disciples, Guo-Niu Han and Bodo Lass. They told me about a charming new result, about the classical (from Feller!) coupon collector problem, that they found, and that surprisingly seems to be new. They found (at least) three insightful proofs, as well as generalizations. Here I offer a 1-page proof of their original result, that I believe to be even shorter than their shortest proof.

Added May 8, 2012: Inspired by Der Spiegel mathematics correspondent Holger DAMBECK's Email message, I wrote a Maple program that implements the Foata-Han-Lass formula. In particular, to answer his specific question, the
input file     yields the following output file.

Added May 15, 2012: See Bodo Lass's Email message    who pointed out that one of their trois preuves is at least as short as mine.
Added May 31, 2012: Read Holger Dambeck's engaging article (in Deutsch)
Added April 7, 2014: Holger Dambeck asked me what are the analogous numbers for the forthcoming Soccer, World Cup when there are 640 coupons.
input file     yields the following output file.
The Personal Journal of Ekhad and Zeilberger

Doron Zeilberger's List of Other Papers

Doron Zeilberger's Home Page