# Understanding problem of Combination with repetitions allowed

I was reading topic on "Combinations with repetition" from the book Discrete Mathematics and Its Application by Kenneth Rosen.

I understood the first problem and the formula. But I did not understood how the solution to the second problem follows the same analogy.

It gives following example:

Problem 1 : How many ways are there to select five bills from a cash box containing \$1 bills, \$2 bills, \$5 bills, \$10 bills, \$20 bills, \$50 bills, and \$100 bills. Assume there are at least five bills of each type. Solution (understood) : • The solution uses star and bars technique. Consider there are 7 buckets holding bills of each type. These seven buckets are represented by spaces created by 6 bars |: \$1 bill bucket |\$2 bill bucket |\$5 bill bucket |\$10 bill bucket |\$20 bill bucket |\$50 bill bucket |\$100 bill bucket

• We have to select bills from these buckets. Each selected bill can be represented by a star * at the corresponding bucket space. For example selecting three \$1 bills and two \$2 bills can be represented by

***|**| | | | |

• The number of ways to select five bills corresponds to the number of ways to arrange six bars and five stars in a row with a total of 11 positions. Consequently, the number of ways to select the five bills is

• the number of ways to select the positions of the five stars from the 11 positions $^{11}C_5$ which is equal to
• the number of ways to select the positions of the six bars from the 11 positions $^{11}C_6$

Forumula (understood)

Thus there are C(n+r-1,r) = C(n+r-1,n-1) r-combinations from a set with n elements when repitition of elements is allowed.

Problem 2 (one in which I have doubt): How many solutions does the equation $x_1+x_2+x_3=11$ have, where $x_1, x_2$ and $x_3$ are non negative integers.

Solution (given in a book which I didnt understood) : To count the number of solutions, we note that a solution corresponds to a way of selecting 11 items from a set with three elements so that $x_1$ items of type one, $x_2$ items of type two, and $x_3$ items of type three are chosen. Hence, the number of solutions is equal to the number of 11-combinations with repetition allowed from a set with three elements. From Theorem 2 it follows that there are

 C(3+11-1,11) = C(13,11) = 78


solutions.

I am not able to understand this above solution since I am not able to comprehend it in terms of stars and bars and thus not able to figure out how n is 11 and r is 3. Can anyone please put this solution in terms of stars and bars, so that I can get it?

There are three buckets, corresponding to $x_1$, $x_2$, and $x_3$, respectively. We have to pick eleven items from these buckets and if we do, we would have $x_1 + x_2 + x_3 = 11$.

• Yeah thanks a lot, I think I understand it now. Its like placing 11 stars into 3 baskets. Baskets can be thought of as spaces created by two bars {1|2|3}. So any solution will contain 11 stars and 2 bars. Thus it can be thought of as selecting two positions to place two bars out of 11+2 = 13 positions of bars and stars which will be $^{13}C_2$ or selecting eleven positions to place eleven stars out of 11+2 = 13 positions of bars and stars which will be $^{13}C_{11}$. Thus the solution is $^{13}C_2$ = $^{13}C_{11}$ – anir123 Oct 26 '14 at 18:04