original question: A donut shop offers $20$ kinds of donuts. Assuming that there are at least a dozen of each kind as you enter the shop, in how many ways can you select a dozen donuts?

The correct answer is: ${}^{31}C_{19}$

I think we can assume that there are $20$ boxes and $12$ balls so that there are $19$ lines and It means choosing $19$ or $12$ from $31$. Is what I think correct?

In addition, I wonder the original question said 'assuming at least a dozen of each kind as you enter the shop'.


You are actually asked to find the cardinality of the set:$$\left\{(a_1,\dots, a_{20})\in\mathbb Z_{\geq0}^{20}\,\middle|\, \sum_{i=1}^{20}a_i=12\right\}$$ Here $a_i$ stands for the number of selected donuts that are of kind $i\in\{1,\dots,20\}$.

This can be done by application of stars and bars and indeed leads to outcome $\binom{12+19}{19}=\binom{31}{19}$.

It seems that your "lines" agree with "bars" and your "balls" with "stars", and that your thinking about this is correct.

If there would be less than a dozen donuts of some kind, e.g. there are $10$ of kind $5$ then extra condition $a_5\leq10$ would arise (making things more complex).

  • $\begingroup$ Ok, thanks very much for explaining. I have understood the front part. But I still can't understand the meaning of 'there are 10 of kind 5 then extra condition a5≤10 would arise'. Please explain a little bit specifically. Thank you again. $\endgroup$ – An Yan Sep 20 '18 at 10:53
  • $\begingroup$ Let's make it smaller: there are $2$ kind of donuts and at least $3$ of each kind. How many ways are there to select $3$ donuts? Answer: $4=\binom{3+1}{1}$. Now let it be that there are at least $3$ donuts of the first kind but there is $1$ donut of the second. Then we have the possibilities $(3,0)$ and $(2,1)$. This because $(1,2)$ and $(0,3)$ are not possible anymore. Next to $a_1+a_2=3$ we also have the restriction $a_2\leq1$. It's an effort to answer on your wondering about 'assuming at least a dozen of a kind if you enter the shop'. $\endgroup$ – drhab Sep 20 '18 at 11:02
  • $\begingroup$ Perfect answer!!! You solve my problem perfectly. Thank u very much!!! $\endgroup$ – An Yan Sep 23 '18 at 10:32
  • $\begingroup$ You are welcome. $\endgroup$ – drhab Sep 23 '18 at 13:04

It is said to assume that there are at least a dozen donuts of each kind to include the possibility of selecting all 12 donuts of only 1 kind.

Proceeding by the traditional counting method, assume that:
you select a1 donuts of first kind, a2 of second kind,.... a20 of twentieth kind where
ai$\geq0$ for each i from 1 to 20.

Since, in total there are only 12 to be chosen, we have $$a1+a2+...+a20=12$$

Number of integral solutions of a1+a2+...+ar=n is C(n+r-1,r-1)

Now, you have to find out integral solutions of this equation, which will be $$C((12+20-1),(20-1))$$ =$$C(31,19)$$


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.