0
$\begingroup$

Assume that you have a bowl containing hard candies:

  • 50 cherry
  • 50 strawberry
  • 40 orange
  • 70 lemon
  • 40 pineapple

Assuming that the pieces of each flavor are identical,

  • How many handfuls of 15 are possible?
  • How many handfuls of 15 are possible with at least one piece of each flavor?
  • How many handfuls of 15 are possible with at least two pieces of each flavor?
  • How many handfuls of 15 are possible with at least three pieces of each flavor?

Btw this is not homework, I found these questions while preparing for an upcoming exam in a problem set online and I am struggling with the concepts. The answers are available at that source, but not the explanation.

$\endgroup$
6
$\begingroup$

Suppose that someone offers you the cherry candies one at a time. You say "yes, yes, yes,..." until you have enough, then you say "no". Then they start offering you the strawberries, and so on. With the pineapple, you will have to say "yes" until you get the right number, so you don't need to say "no".

So overall, you are going to say "yes" $15$ times and "no" $4$ times. The only question is the order in which you say these words, and they can be arranged in $C(19,4)$ ways. So this is the number of different handfuls you could get.

For the second problem you start off with one of every flavour and then go through the same procedure, except now you will only say "yes" $10$ times. See if you can finish this, and the other questions, from here.

$\endgroup$
  • 2
    $\begingroup$ Nice exposition of Stars and Bars. $\endgroup$ – André Nicolas Jul 21 '15 at 1:20
  • $\begingroup$ Would it make a difference if the number of available candies were not given and they only said there are 5 types of candies (more than 15 of each)? I think that is where my confusion came in. $\endgroup$ – Julia Jul 21 '15 at 1:22
  • 2
    $\begingroup$ @Julia No difference at all. As you are only taking $15$, the number available is irrelevant, so long as there are at least $15$ of each kind. $\endgroup$ – David Jul 21 '15 at 1:31
0
$\begingroup$

Use generating functions. First, as the 15 candies are less than each flavor, you might as well assume there is an infinite supply of each. So each flavor is represented by $(1 - z)^{-1}$, as there are 5 flavors, in all $(1 - z)^{-5}$. Now you want:

  • 15 in all, no other restricions: $$[z^{15}] (1 - z)^{-5} = \binom{-5}{15} = (-1)^{15} \binom{5 + 15 - 1}{15} = 3876$$
  • 15 in all, at least $k$ of each flavor: This means that you are taking $5 k$ of fixed flavors, and $15 - 5 k$ afterwards: $$[z^{15 - 5 k}] (1 - z)^{-5} = \binom{-5}{15 - 5 k} = (-1)^{15 - 5 k} \binom{5 + 15 - 5 k - 1}{5 - 1} = \binom{19 - 5 k}{4}$$
$\endgroup$

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.