
Statistics Kingdom

Number of combinations without repetitions  = ^{n}C_{r}  
 
Number of permutations without repetitions  = ^{n}P_{r}  
 
Number of combinations with repetitions 
 
Number of permutations with repetitions  = n^{r} 
The difference is whether we care about the order. With combinations, the order does not matter. For example, we could be cutting salad and it would not matter if we add the tomatoes first and then the cucumbers or the other way around  our salad would taste pretty much the same. If we do care about the order then we are choosing a permutation. Let's say we baked some bread to eat with our salad. Now it is important that we add the water to the flour before we put it in the oven rather than heating the flour with the yeast and adding the water later. Therefore a bread recipe is a permutation.
How many ways are there to order 5 balls?
bag:
Well we have 5 choices in our first selection, then 4 choices for the second selection, then 3, 2 and 1. So overall we have 5 * 4 * 3 * 2 * 1 different options. Since this is a bit long to write out, we can write it out as 5! instead (read as 5 factorial). Using factorial just means that we multiply all the numbers from 1 to our number, which is 5 in this case. What if we only wanted to choose three out of the five balls? How many ways do we have to do that? Well we could just think about it as 5 choices in the first selection, 4 in the second, 3 in the third and that's it. So there are 5 * 4 * 3 ways which is very similar to 5! except we have to cancel out the last two terms. We can do this by dividing by 2 * 1, giving (5 * 4 * 3 * 2 * 1) / (2 * 1) = 5! / 2! = 5! / (53)! permutations. It turns out that this strategy works for more items too. If we had 12 items and we wanted to choose 4 we would get 12 * 11 * 10 * 9 = 12! / (124)! permutations. If we had 17 items and wished to choose 5 items out of 8 we would get 8 * 7 * 6 * 5 * 4 = 8! / (85)! and in general, if we have n balls and we want to select r balls without repetition we would have ^{n}P_{r} options = n! / (nr)!.
How many ways are there to choose 4 balls (out of our 5 balls from before) if we can repeat ourselves?
Well in our first selection we would still have 5 options. In our second selection, we would again have five option because we have replaced our last choice, so any of the 5 balls can come next. The same would apply to the third and fourth selections. Therefore we have 5 * 5 * 5 * 5 options, or 5^{4} permutations. If we now had to choose 3 balls instead, it would be 5^{3} permutations. In general, if we have n balls and we want to choose r balls with repetitions we have n^{r} different permutations.
How many ways are there to choose 3 balls (out of our 5 balls from before) if we can't repeat ourselves and we don't care about the order?
We can start off by seeing that the problem is similar to counting permutations without repetitions. Let's take a specific combination, say the balls 1, 2 and 3. How many times does the combination appear in our permutation list? and so on
Well 6 times. That's because there are 3! = 6 different ways to order our 3 balls and therefore each of our combinations will appear 6 times on this list. So if we choose 3 balls out of 5 with no repetitions, we have 5!/((53!)3!) different combinations. In general when we choose r balls out of n, we have ^{n}C_{r} different combinations = n!/((nr)!r!).
How many ways are there to choose 8 balls out of the 5 balls if we can repeat ourselves?
This is a bit more difficult to think about but we can do reasonably well with an online order form which lets us choose how many of each color we need. For example, we would represent getting 2 red balls, 2 green balls, 1 blue ball and 3 yellow balls as:
red: 2
green: 2
blue: 1
yellow: 3
grey: 0
If we wanted 2 red balls and 6 grey balls we would order:
red: 2
green: 0
blue: 0
yellow: 0
grey: 6
Now this is still a bit hard to deal with mathematically, but we are nearly there. Let's convert each color label to an L and the quantity to an appropriate number of B's.
So the first example can be represented as LBBLBBLBLBBBL and the last example would be LBBLLLBBBBBB. How many ways are there to fill out order forms like this?
Let's look at the locations of the L's in this list. The first L must be in position number 1. The other (51) L's can be in any position from 2 to 13 (8+5) except they must have different positions.
So we have to choose (51) numbers from (131) positions to put them in  that's ^{12}C_{4}=12!/((124)!4!).
In general, we can choose r balls out of n with repetitions in (n+r1)!/((n1)!r!) = ^{n+r1}C_{r}