Question

How many ways are there to choose a dozen donuts from 20 varieties

1. if all donuts are of the same variety?
2. if there are at least two varieties among the dozen donuts chosen? 
3. if there must be at least six blueberry-filled donuts? 
4. if there can be no more than six blueberry-filled donuts?

Answer 1

a) Here a dozen items must come from a single variety. And we have 20 varieties possible. Hence the no of ways of selecting a dozen of same variety donut = 20.

b) For this part lets find out no of ways in which the 12 donuts can be chosen from 20 varieties

$$x_1 + x_2 + \dots +x_{20}=12$$

No ways of solving this is ${}^{(20+12-1)}C_{19} =141,120,525$ (Explained at end). In the question they have asked that there are at least 2 varieties of donuts. Hence we need to negate the ans of part a(i.e, the no of ways in which the same variety can be chosen ) from the total no of ways of choosing the donuts $= 141,120,525-20=141,120,505$

c) It is given that at least 6 donuts of blueberry variety should be there. Here we can assume that 6 donuts are already chosen. Hence now the solution is ${}^{(20+6-1)}C_{19}($ ie., no ways of solving $x_1+x_2+ \dots+x_{20}=6) =177,100$.

d) Here the condition is no more than 6 blue berry are selected. To solve this find the no of ways in which at least 7 blue berry will be chosen an in part c which is ${}^{(20+5-1)}C_{19}=42505$. Now negate this from total no of possibilities to get the required ans $= 141,120,525 - 42,505 = 141,078,021$.

---

We have $x_1 + x_2 + \dots + x_{20} = 12$.

So, this problem is equivalent to dividing 12 identical balls into 20 distinct bins without any further restrictions. So, lets use | for the separation between bins and $0$ for the balls. For example the below configuration shows all 12 balls in the first bin. 

0 0 0 0 0 0 0 0 0 0 0 0 | | | | | | | | | | | | | | | | | | | 

So, now our required answer will be all possible permutations of the above. We have 12 balls and (20-1) separations. Further 12 balls are identical and 19 separations are also identical (bins are distinct but separations are identical as two separations together means a bin in empty and their order doesn't matter). So, no. of possible permutations 

$ = \frac{ (12+ 19)!}{12!19!} = {}^{31}C_{19}$.

This can be extended for $n$ bins and $k$ balls as ${}^{n+k-1}C_{n-1}$

Ref: http://www.cse.iitm.ac.in/~theory/tcslab/mfcs98page/mfcshtml/notes1/thperset.html

Comments

Hi @Mani : Please pardon my ignorance. But , in the question (a) , it says choose 12 ( a dozen ) from 20 same variety donuts. I agree that as all donuts are of same variety  each of donut can be chosen in 20 ways.

Also , I could not understand the ^(n+r-1) C _{( n-1)} in (b) ,
 Please explain .

Thanks in advance.

---

Explained at end. Also see the reference link for more types of counting problems.

---

could'nt understand part (a)..

we have to choose 12 donuts..how the number of ways are 20??

should'nt it be 20 C₁₂  ??

---

also ould'nt understand part B.

I had gone through the link,could'nt find question of this type having formula ^(n+r-1) C _{( n-1)}

infact,i found only this :

The number of ways r identical balls can be thrown into n distinct bins with the constraint that a bin can contain any number of balls is given by,

(n+r-1)Cr.