0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – anir123 Oct 26 '14 at 18:04

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.