Hi!
This is probably a very simple question to answer but with the formula below, I'm not entirely sure why you have to divide by r!. I think it's in order to avoid repeats, but how does dividing by r! do this?
Thanks so much!
You should try and give more context when asking questions like this - it can often be confusing pulling out equations out of nowhere like this. However, I think you're talking about comparing permutations to combinations? In which case, the formula for the number of permutations of r objects in a set of n would be:
Whereas the the formula for the number of r COMBINATIONS in a set of n would be:
And you want to know why combinations require dividing by r! - is that right?
In this instance, you need to ask not just what's different between the equations, but between the actual situation. A combination is easier to understand because we can put it in terms of real world understanding. For example - let's say you're making a 3 veggie salad out of lettuce, cucumber, carrot, and red onion. Well, if you were to make the salad by adding lettuce, then cucumber, then carrot, that would be the same as the salad made by adding cucumber, then lettuce, then carrot - the ingredients are the same, after all! However, a permutation is a bit trickier to think about - but you can think of it as the recipe. Although the final salad is the same, the actual recipe is different - the order that things are added is important. I think this is a point you might already understand, so I won't dwell on it more than this.
Okay, so what does this have to do with the formulas? Well, we know from the formula for permutations, there are a total of:
different recipes. But we don't have nearly that many salads, do we? Well, if you trace out all the combinations by writing them out, you'd find there are only 4 different salads we could make - why is there so many different ways to make them?? Well, let's consider the lettuce, carrot, cucumber recipe. We could make it in the following orders:
Lettuce, carrot, cucumber
Lettuce, cucumber, carrot
Cucumber, lettuce, carrot
Cucumber, carrot, lettuce
Carrot, lettuce, cucumber
Carrot, cucumber, lettuce
6 ways in total. Okay, but we only want one of these to be preserved, so we should subtract 6 from first equation! ... But if we did that, we'd lose ALL of the combinations. Okay, so maybe instead we subtract 5. But we need to do this for all the other permutations, too - which would require knowing how many combinations there are to begin with! But, here's a thought. What if we were making this salad, and our list never included red onion? Well, we'd have 6 different recipes we could follow, but now there's only possible salad - because we're choosing 3 ingredients from a list of 3 ingredients - every time, we're just going to choose all of them. In this case, how can we get from 6 permutations to 1 combination? We could subtract 5, of course - but we could also divide by 6, which is just the total number of permutations of the full list. Think about it - if we divide each of our permutations from the set into groups of ALL POSSIBLE permutations, then all that's going to be left is one group of permutations.
Okay, so let's go back to our 4 ingredient for 3 veggie salad problem. In this case, there are 24 different recipes we could follow. We know that the total amount of possible permutations for a recipe of 3 ingredients is going to be 3!. So, if we take all 24 different recipes, and divide them into 3! (6) groups, one of these groups should have just one final combination of recipes. Firstly, here's all 24 different recipes:
Spoiler
Lettuce, carrot, cucumber
Lettuce, cucumber, carrot
Cucumber, lettuce, carrot
Cucumber, carrot, lettuce
Carrot, lettuce, cucumber
Carrot, cucumber, lettuce
Red onion, carrot, cucumber
Red onion, cucumber, carrot
Cucumber, red onion, carrot
Cucumber, carrot, red onion
Carrot, red onion, cucumber
Carrot, cucumber, red onion
Red onion, lettuce, cucumber
Red onion, cucumber, lettuce
Cucumber, red onion, lettuce
Cucumber, lettuce, red onion
Lettuce, red onion, cucumber
Lettuce, cucumber, red onion
Red onion, lettuce, carrot
Red onion, carrot, lettuce
Carrot, red onion, lettuce
Carrot, lettuce, red onion
Lettuce, red onion, carrot
Lettuce, carrot, red onion
Now, if we divide them into six groups... That's the equivalent of just taking the first set from each group of permutations, which gives us 4 possible salads in total.
Hopefully that makes a bit more sense - the idea is if we divide by r!, well r! is the number of permutations we could be having, so it's like dividing every permutation into their own combination groups, and just picking out one of the combinations from each permutation group. It's hard to think about abstractly, but hopefully makes more sense now that you've seen it as an example.