Coupon collecting and transversals of hypergraphs
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
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.
coupon collector, transversal
IdentifiersURN: urn:nbn:se:uu:diva-212434ISI: 000327033900019OAI: oai:DiVA.org:uu-212434DiVA: diva2:677836