combinations
Combinations
Suppose we have five distinct items and wish to pick and place three of them into a box. In this scenario, it does not matter in what order we pick the items as we're only concerned about what's in the box. This is called a combination.
To find how many ways we can fill this box, we first consider the amount of permutations possible. That's \[P(5,3)=60\] possible permutations. However, we can disregard in what sequence we placed them in the box, as we are only concerned about what's in the box at the end. Thus picking the items in the order "125", "152", "215", "251", "512" and "521" will all still end up with items 1, 2 and 5 in the box, therefore we can categorise all these orders as just one single unique combination. Notice that the sequences we listed above is all the possible permutations of "1", "2" and "5". Thus, the total possible combinations would be \[\frac{P(5,3)}{P(3,3)}\]. We can also rewrite the result as, \[\frac{P(5,3)}{P(3,3)}=P(5,3)\cdot\frac{1}{3!}=\frac{5!}{(5-3)!\cdot3!}\].
As a general rule, when we have \[n\] distinct items and wish to select \[k\] of them to create a combination, the total number of possible combinations is \[C(n,k)=\frac{n!}{(n-k)!\cdot k!}\].
Example 1
Suppose we have twelve items and wish to chose seven of them. However, there is an additional constraint where item 1 and 2 are either both chosen or not chosen, i.e. we can not only pick either item alone. We are tasked to find the total possible combinations.
The approach here is to consider the total combinations of when both are picked, or when both are not picked. When both are picked, we are now left with five items to be picked from a total of ten remaining items. Thus there are \[C(10,5)\] possible ways to pick them. Logically, since combining the five remaining items with item 1 and 2 are essentially the same pick, i.e. "34567" and "1234567" are the "same" combination, it is indeed that there are only \[C(10,5)\] possible ways to pick these seven items since the order is irrelevant.
On the other hand, if both are not picked, we can essentially ignore both of them and pick seven items out of the ten remaining items. That would be a total of \[C(10,7)\] possible ways.
Thus, the total number of possibilities is then \[C(10,5)+C(10,7)=372\].
Combinations with repeated indistinguishable elements
Suppose we want to buy seven cans of soda. A store sells three types of soda, each of infinite quantity. How many possible combinations are there?
The approach to developing this formula is rather interesting. Imagine each soda as an object, call it "X" and a divider signifying a "divider" for how many sodas per type. So, say a possible combination might be "XX|XXX|XX" (2x type 1 soda, 3x type 2 soda and 2x type 3 soda) or maybe "|XXX|XXXX" (0x type 1 soda, 3x type 2 soda and 4x type 3 soda).
The trick here is to regard the dividers as also an "object", and since the dividers need order to actually mean something, we will also treat the problem as a permutation of repeated objects rather than a combination. Thus it becomes trying to permute nine objects with repeats, i.e. the total possible permutations is \[\frac{9!}{7!\cdot2!}\]. Notice that \[\frac{9!}{7!\cdot2!}=\frac{9!}{(9-7)!\cdot7!}=C(9,7)\].
Example 2
Now suppose we want to buy twenty cans of soda and ten cans of juice. A store sells three different types of soda and four types of juice, each in infinite quantity. How many possible combinations are there?
First, we have twenty cans of soda with two dividers, thus \[\frac{22!}{20!\cdot2!}=C(22,20)\] total combinations. Next, tens cans of juice with three dividers, thus \[\frac{13!}{10!\cdot3!}=C(13,10)\] total combinations. Now combine both to get \[C(22,20)\cdot C(13,10)=66066\] total possible combinations.