Probability of collecting all 5 buying 7 chocolates

The flaw in your solution is that the $330$ cases you enumerated are not equally likely to appear. For instance, there is only one way for all seven chocolate bars to show the first label. However, if we list the stickers in the order in which we look at the chocolate bars we collect, there are $\binom{7}{2}\binom{5}{2}3!$ ways to obtain a collection with two stickers of the first type, two stickers of the second type, and one of each of the other types.

There are five possible stickers for each of the seven chocolate bars, so there are $5^7$ ways to distribute stickers to chocolate bars.

For the favorable cases, we must subtract those distributions in which not all five kinds of stickers appear in the collection of purchased chocolate bars.

There are $\binom{5}{k}$ ways to exclude $k$ of the $5$ stickers and $(5 - k)^7$ ways to distribute stickers of the remaining $5 - k$ kinds to the chocolate bars. Hence, by the Inclusion-Exclusion Principle, the number of ways the stickers may be distributed to the seven chocolate bars so that all five kinds of stickers appear is $$\sum_{k = 0}^{5} (-1)^k\binom{5}{k}(5 - k)^7 = 5^7 - \binom{5}{1}4^7 + \binom{5}{2}3^7 - \binom{5}{3}2^7 + \binom{5}{4}1^7 - \binom{5}{5}0^7$$ Thus, the probability that all five kinds of stickers appear on the collection of seven chocolate bars is $$\frac{1}{5^7}\left[5^7 - \binom{5}{1}4^7 + \binom{5}{2}3^7 - \binom{5}{3}2^7 + \binom{5}{4}1^7 - \binom{5}{5}0^7\right]$$


This is rather long, but correct solution. Your sample space are 7 chocolate bars with stickers attached to them. Probability of an elementary sequence is $(1/5)^7$. Let's count favorable sequences. If you have 5 different bars, you may have the following possibilities: 3 kinds of a specific sticker and 4 remaining unique stickers, or 2 kinds of 2 stickers plus 3 remaining unique stickers. Let's now count! There are 5 different stickers, ${7 \choose 3}$ ways to select positions for a sticker of the same kind, and 4! ways to arrange remaining unique stickers in alternative orders (remember that we are working with elementary sequences), giving the first summand: $$5{7 \choose 3}4! = 4200$$ There are also ${7 \choose 2}$ ways to select positions for a first 2-repeats sticker and ${5 \choose 2}$ ways to select positions for a second 2-repeats sticker. Now, once positions are selected, we have ${5 \choose 2}$ ways to select two stickers to fill these 2-repeat positions, and 3! ways to arrange remaining unique stickers. The second summand, therefore, is: $${7 \choose 2}{5 \choose 2}{5 \choose 2}3! = 12600$$ Finally, together we have: $$(1/5)^7(12600 + 4200) = 0.21504$$


I could not remember any of my combinatorial mathematics, so I did a brute force method. My apologies to the real mathematicians out there.

Let's name the stickers with lower case letters: a, b, c, d, e.

Each element in our sample set of equally likely outcomes is a 7-tuple of these letters.

  • Example: [abcdeab]

Order matters! [aaaaaab] is different than, but equally likely as, [baaaaaa] even though they contain the same number of each type of sticker. So there are five options for the first chocolate bar, five options for the second chocolate bar, etc.

That means there are 5*5*5*5*5*5*5 = 78125 equally likely outcomes.

How many of these outcomes contain all five stickers? Let's take one of each sticker and find out how many ways we can place them on five different chocolate bars.

  • I have seven options of where to place A.
  • I have six remaining options of where to place B.
  • I have five remaining options of where to place C.
  • I have four remaining options of where to place D.
  • I have three remaining options of where to place E.

That gives me 7*6*5*4*3 = 2520 combinations for placing 5 stickers. Let's call each option a "template".

  • Template Example: [dXcbaYe] where X and Y have not yet been given stickers.

I can put any sticker I want on X or Y, and as there are 5 sticker choices, I have 5*5 or 25 variants for each template.

At this point, I might be tempted to say that we have 2520 possible templates each with 25 variants for a total of 2520*25 = 63,000 favorable outcomes. But that would be wrong, because I am counting outcomes multiple times.

  • Example: These two templates, [abcdeXY] and [XXcdeab], can both produce the same variant [abcdeab].

So let's calculate duplication and eliminate it.

If X and Y get assigned the same sticker, then the outcome will appear as a variant of three separate templates. For example, the outcome [abcdeaa] is a variant of the following three templates:

  • [abcdeXX]
  • [XbcdeaX]
  • [XbcdeXa]

If X and Y get assigned different stickers, then the outcome will appear as a variant of four separate templates. For example, the outcome [abcdeab] is a variant of the following four templates:

  • [abcdeXY]
  • [XbcdeaY]
  • [aXcdeYb]
  • [XYcdeab]

So, I have 2520 possible templates. For each template, I have 25 variants, of which 5 (the XX variants - aa, bb, cc, dd, ee) will be counted three times each and the other 20 (the XY variants) will be counted four times each. So the total number of options is:

  • XX variant count - (2520 * 5 / 3) = 4200
  • XY variant count - (2520 * 20 / 4) = 12600
  • All variants = 4200 + 12600 = 16800

So the probability is 16800 / 78125 = 21.504%

Tags:

Combinatorics

Probability

Related

Show that $\sum_{n=0}^\infty \frac{1}{n+1} \binom{2n}{n} \frac{1}{2^{2n+1}} = 1.$ Prove $f (1)<\frac32$ given $f (0)=0$, $f'(0) = 1$, $f(x)+1=\frac1{f''(x)}$ Why is the definition of inner product the way it is? Do most numbers have exactly $3$ prime factors? Estimate $n$ such that $\log(n^C)<n$ Nonexistence of a simple group of order 576 Hausdorff-dimension of non measurable sets? What is the behaviour of the first $n$ digits of ${\underbrace{99\dots99}_{n\text{ nines}}}^{\overbrace{99\dots99}^{n\text{ nines}}}$ as $n\to\infty$ Dictionary Meaning of "Modus Ponens" and "Modus Tollens" Formula for angle between faces based on angles of corners Finding: $\gcd\left(2^{200}-2^{100},2^{200}+2^{101}\right)$ and $\gcd\left(3^{202}-3^{101},3^{202}+3^{102}\right)$ Partial order on Grothendieck group of an abelian category

Recent Posts