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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Mathematics
Identifiers
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: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2331/4349

Authority records BETA

Janson, Svante

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 379 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf