1

So, we have 3 types of items (a,b,c) in a collection and the number of items available is unlimited.

If every time we choose 3 random items from the above collection.

What is the number of possible distinct outcomes - if we are not interested in the order of the items that we are pulling out of the collection e.g. aab is the same as pulling baa or aba.

Also what is a general aproach for n item types?

Thanks.

PKey
  • 113
  • 1
    Stars and bars. Put 2 sticks in 5 spots. Fill all the space to the left of the first stick (if any) with a's. Fill all the spaces between the sticks (if any) with b's. Fill all the remaining spaces (if any) with c's. There are exactly as many ways to choose 3 items as the are to place sticks. That is $5\choose 2=10$.aaa||,aa|b|,aa||c,a|bb|,a|b|c,a||cc,|bbb|,|bb|c,|b|cc,||ccc. In general ${n+(k-1)\choose (k-1)} $. – fleablood Jul 03 '17 at 06:34
  • @fleablood Thanks for a nice explanation ... – PKey Jul 03 '17 at 06:42

1 Answers1

2

Think of this graphically: If we had three items, we could view them as the * symbol. Then we can divide them in three groups using two of the | symbol; each grouping can be thought of as a type.

For example, "aab/aba", etc, would look like **|*|, and "abc" looks like *|*|*, and "ccc" looks like ||***.

Now, the problem becomes "ordering three like characters and two different like characters". Using the "Bookkeeper Rule", we know this is $$\frac{5!}{3!\cdot2!}$$

The general solution for choosing $n$ items of $k$ types is $$\frac{(n + k - 1)!}{n!\cdot(k-1)!}$$

Larry B.
  • 3,384