Suppose that I am buying cakes for a party. There are k different types and I intend to buy a total of n cakes. How many different combinations of cakes could I possibly bring to the party?

Question

Suppose that I am buying cakes for a party. There are   k different types and I intend to buy a total of   n cakes. How many different combinations of cakes could I possibly bring to the party?

minnegodks · Accepted Answer

Using a method that&#039;s often called &quot;stars and bars&quot;:We draw n stars in a row to represent the cakes, and   k  −  1 bars to divide them up. All of the stars to the left of the first bar are cakes of the first type; stars between the first two bars are of the second type;  ∗  ∗      |    ∗  ∗  ∗      |        |    ∗      |  Here&#039;s an example with   n  =  6 and   k  =  5. We&#039;re getting   2 of the first type,   3 of the second type,   0 of the third type,   1 of the fourth type, and 0 of the fifth type.In order to solve the problem, we just need to reorder the stars and bars by choosing the   k  −  1 spots for the bars out of the   n  +  k  −  1total spots, so our answer is:

cyfwelestoi · Accepted Answer

Let&#039;s assume you have   n items and   k bins. You need   k  −  1 separators to get the   n items into the   k bins. There are   (  n  +  k  −  1  )  ! permutations of ordering   n items and   (  k  −  1  ) separators. The permutations of the n items don&#039;t matter, and the permutations of the   (  k  −  1  ) separators don&#039;t matter, so you&#039;ll need to divide by   n  ! and   (  k  −  1  )  !Thus you have            (      n      +      k      −      1      )      !              n      !      (      k      −      1      )      !        =                (                      n        +        k        −        1                    k        −        1                        )

Suppose that I am buying cakes for a party. There

Answered question

Answer & Explanation

New Questions in Precalculus