2
$\begingroup$

There are 5 types of candies: Cherry, strawberry, orange, lemon, and pineapple. How many ways are there to choose:

a) $32$ candies

b) $32$ candies with at least a piece of each flavour

c) $32$ candies with at least $1$ cherry and at least $6$ lemon

I figured out the answers looking at similar questions but I am having a hard time seeing exactly how to get there.

For A, I wanted to just take $^{32}C_5$ since there are 32 candies to choose from but I realized this is answering a different question. The answer is $^{36}C_4$.

I think I understand how to go from $5$ to $4$. This is because there are $5$ types of candies so we need $4$ partitions? Why then do we add $4$ to $32$?

$\endgroup$
  • $\begingroup$ where did the question come from ? $\endgroup$ – user451844 Sep 16 '17 at 21:31
2
$\begingroup$

There are five types of candies: cherry, strawberry, orange, lemon, and pineapple. How many ways are there to choose $32$ candies?

Let $c$, $s$, $o$, $l$, and $p$ denote, respectively, the number of cherry, strawberry, orange, lemon, and pineapple candies selected. Then $$c + s + o + l + p = 32 \tag{1}$$ is an equation in the nonnegative integers. A particular solution of equation 1 corresponds to the placement of four addition signs in a row of $32$ ones. For instance, $$1 1 1 1 1 1 1 + 1 1 1 1 1 + 1 1 1 1 1 1 1 1 1 1 1 1 + 1 1 1 1 1 1 1 1 +$$ corresponds to $c = 7$, $s = 5$, $o = 12$, $l = 8$, and $p = 0$. Therefore, the number of solutions of equation 1 is equal to the number of ways we can choose which four of the $36$ positions (for $32$ ones and four addition signs) will be filled with addition signs, which is $$\binom{32 + 4}{4} = \binom{36}{4}$$

More generally, the number of solutions of the equation $$x_1 + x_2 + x_3 + \ldots + x_k = n$$ in the nonnegative integers is $$\binom{n + k - 1}{k - 1}$$ since we must choose which $k - 1$ of the $n + k - 1$ symbols (for $n$ ones and $k - 1$ addition signs) will be filled with addition signs.

I think I understand how to go from $5$ to $4$. This is because, there are $5$ types of candies, so we need $4$ partitions.

Yes.

Why then do we add $4$ to $32$?

Another way of thinking about the problem is that we have $36$ slots for the $32$ candies and $4$ partitions. We choose $4$ of these for the partitions. The number of slots to the left of the first partition is the number of cherry candies selected. The number of slots between the first and second partitions is the number of strawberry candies selected. The number of slots between the second and third partitions is the number of orange candies selected. The number of slots between the third and four partitions is the number of lemon candies selected. The number of slots after the fourth partition is the number of pineapple candies selected. Therefore, choosing in which $4$ of these $36$ slots the partitions will be placed determines the distribution of the candies.

$\endgroup$
2
$\begingroup$

As regards a) we have to enumerate the non-negative integer solutions of the equation $$C+S+O+L+P=32$$ where $C$, $S$, $O$,$L$, $P$ denote the number of candies of type cherry, strawberry, orange, lemon, and pineapple respectively. By stars-and-bars technique this number is $$\binom{32+5-1}{5-1}=\binom{36}{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.