In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425.

My confusion is how to identify the k-collections. A k-collection is defined as: "to be a word that consists of k different letters with the last letter in the word being the only time that letter occurs"

Exercise 8.6 of the book asks to find all the 2-collections and 3-collections in Table 8.1, where that table shows the configurations of 4 balls in 3 urns

If I give it a try, I'd say a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end, but I'm pretty sure I"m wrong.

Can anybody help providing an example of a k-collection (2 or 3-collection) from Table 8.1? Thanks

  • 2
    $\begingroup$ "I'm pretty sure I'm wrong". Can you explain why or how you are sure you are wrong? $\endgroup$ – John L. Mar 17 '19 at 11:43
  • $\begingroup$ @Apass.Jack - I can't, I was getting confused. Thanks for your answer! $\endgroup$ – gnavarro Mar 18 '19 at 16:09

I cannot figure out why you were "pretty sure" you were wrong, because you have given a correct example, "a 3-collection from Table 8.1 is 2213, where the last letter (number 3) occurring just at the end".

Here are 2-collections.
1112, 1113, 2221, 2223, 3331, 3332.

Here are 3-collections.
1123, 1132, 1213, 1223, 1312, 1332,
2113, 2123, 2213, 2231, 2321, 2331,
3112, 3132, 3221, 3231, 3312, 3321.

There is a natural way for you to check whether your understanding is correct without any extra effort, assuming you are required or scheduled to read that section "coupon collector problem" in the book. What you could have done is to try to understand that section as much as possible, assuming whatever interpretation your could have. If you find some inconsistency, then your interpretation is probably wrong. Otherwise, your interpretation is probably correct.

For example, I also doubted my understanding of that definition of $k$-collection.

However, when I have read "if each box of a product contains one of a set of $M$ coupons, how many boxes must one buy, on the average, before getting all the coupons? This value is equivalent to the expected number of balls thrown until all urns have at least one ball or the expected number of keys added until all the chains in a hash table built by Program 9.1 have at least one key", I am confident that I got it correctly. I can imagine each letter in an $M$-collection is a box containing a coupon, where different letters mean different coupons. A ordered collection of letters is an ordered buying sequence of boxes containing coupons. So an $M$-collection means a buying sequence that gets all $M$ coupons right at its last buy. Ditto for chains in a hash table. The more I read, the more confident I become.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.