[Math] Understanding problem of Combination with repetitions allowed

combinatorics

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?

Best Answer

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

Related Question