Main Data History
Show Index Toggle 0 comments
  •  Quick Edit
  • Multichoose

    Wolfram Alpha defines multichoose as follows, “The number of multisets of length \(k\) on \(n\) symbols is sometimes termed \(n\) multichoose \(k\), denoted \(\left(\binom{n}{k}\right)\) by analogy with the binomial coefficient \(\binom{n}{k}\) \(n\) multichoose \(k\) is given by the simple formula \(\left(\binom{n}{k}\right)=\binom{n+k-1}{k}=\left(n-1,k\right)!\), where \((n-1,k)\) is a multinomial coefficient” (Wolfram).

    What is so special about multichoosing is that it can be used for counting problems where order does not matter and repetition is allowed.

    Another term one might often hear used in place of a multichoose problem is a “stars and bars” problem. In fact, if you’re ever in a pinch you should be able to come up with the multichoose formula just from the stars and bars method.

    It works something like this. Say we are given 3 distinct candies


    How many ways can we place 7 candies in a bowl where order does not matter and repetition is allowed?

    Begin by creating 3 separate spaces with the bars; to make 3 spaces we use 2 bars.
        |     |     
    Here the first space can be for blue candies, second for red, and third for green.

    (blues)  |  (reds)  |  (greens)

    For the first way, say we pick all blue candy. The stars represent candy and this is denoted...
    \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\)|  |
    For the second way, say we pick all red candy. Denoted...
     |\(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\) \(\bigstar\)|  
    For the third way, say we pick 2 blues, 2 reds and 3 green candies. Denoted...
    \(\bigstar\) \(\bigstar\)|\(\bigstar\) \(\bigstar\)|\(\bigstar\) \(\bigstar\) \(\bigstar\)
    Notice any scenario will result in 9 slots, 2 for the bars, and 7 for the stars(candies).
    _  _  _  _  _  _  _  _  _
    Simply put all we are deciding in each case is where to put the bars. Therefore we have 9 slots choose 2 slots to place the bars or \(\binom {9}{2}\). Equivelantly, we also have 9 slots choose 7 slots to place the stars or \(\binom {9}{7}\). Feel free to verify that those are indeed the same.
    To finish the problem \(\binom{9}{2}= \frac{9!}{2!(9-2)!}=36\) different ways to place the candies.