uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Coupon collecting and transversals of hypergraphs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2013 (English)In: Discrete Mathematics & Theoretical Computer Science, ISSN 1462-7264, E-ISSN 1365-8050, Vol. 15, no 2, 259-270 p.Article in journal (Refereed) Published
Abstract [en]

The classic Coupon-Collector Problem (CCP) is generalized to a setting where coupons can serve more than one purpose. We show how the expected number of coupons that needs to be drawn can be determined by means of enumerating transversals of hypergraphs, where coupons can be drawn either with or without replacement. Only basic probability theory is needed for this purpose. The transversal counting can be done efficiently by a recently introduced algorithm that encodes all possible transversals in an efficient way. Our results are illustrated by applications to, amongst others, chess and roulette.

Place, publisher, year, edition, pages
2013. Vol. 15, no 2, 259-270 p.
Keyword [en]
coupon collector, transversal
National Category
URN: urn:nbn:se:uu:diva-212434ISI: 000327033900019OAI: oai:DiVA.org:uu-212434DiVA: diva2:677836
Available from: 2013-12-10 Created: 2013-12-10 Last updated: 2013-12-10Bibliographically approved

Open Access in DiVA

No full text

Other links


Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
Discrete Mathematics & Theoretical Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 166 hits
ReferencesLink to record
Permanent link

Direct link