Why does this intuition for combinations with repetition fail?

Question

When you are learning the difference between combinations and permutations without repetition. The logic for each of them is:

1) Permutation without repetition: Selecting 4 objects from 10, gives $10*9*8*7$ choices.

2) Combinations without repetition: Selecting 4 objects from 10, gives $10*9*8*7/(4*3*2*1)$.

Here you always divide by the number of times you can arrange 4 objects since each of those combinations are the same, order doesn't matter.

3) Permutations with repetition: selecting 4 objects from 10, is $10*10*10*10$

4) Combinations with repetition

Now trying to apply this to combinations with repetition, my reasoning is this. Its similar to how one goes from permutations to combinations in the case of no repetition. There are 10 objects to choose from and you want to select 4. Each selection doesn't diminish the number of choices you have since its replacable. So for each possible selection you have 10 choices, selecting 4 then gives $10^4 / 4!$ since you need to divide by the number of ways 4 objects can be arranged to not overcount.

I know this is wrong, I've seen solutions to this using stars and bars. But my question is basically, for the case of no repetition, combinations can be treated as permutations only if you divide by the number of ways you can arrange your selection, and that makes intuitive sense to me.

When it comes to repetitions, permutations make sense to me. Selecting k objects from n choices is just $n^k$. So why cant I use the same reasoning here and say that the number of combinations is $n^k / k!$?

Answer 1

Good question.

You cannot apply the same reasoning in the case when we have repetitions, because the $4!$ ways you can arrange $4$ objects assume different objects.

Let's look at your example of choosing $4$ objects from $10$ possible objects (with repetition) and say that our $10$ possible choices are letters A to J.

One possible permutation is ABBA, which is different to the permutation BABA. Now think about how many ways do we have to arrange two As and two Bs. It is not $4!$ (we do not have 4 ways to choose the first letter, nor 3 choices for the second letter etc).

In the extreme case where we have say CCCC (this is one permutation), we also have only one combination.

So when you divide by $r!$, you are potentially overestimating the number of ways you can arrange the objects in a permutation, because you might have repeated objects in this permutation. Moreover, it is difficult to calculate the average arrangements because it depends on the permutation we have each time. So instead of trying to solve the problem this way, we attack it differently (stars and bars for example).

This method is not a problem when repetitions are not allowed because you can easily count the possible arrangements for any permutation. They are always the same, independent of the permutation we have.

Answer 2

There are 24 variants of: ABCD, ABDC, ... , DCBA. These are all distinct permutations without repetition, and they all condense to the same combination without repetition. This accounts for the division by $4!$ when there is no repetition.

But consider these permutations with repetition: AABB, ABAB, ABBA, BAAB, BABA, BBAA. For two As and two Bs, that's it. Now six permutations condense to one combination.

And here: AAAB, AABA, ABAA, BAAA. We have four permutations condensing to one combination.

And here: AAAA. Just one permutation condensing to one combination.

And here: ABCC, ACBC, ACCB, BACC, BCAC, BCCA, CABC, CACB, CBAC, CBCA, CCAB, CCBA. We have twelve condensing to one.

So there is no consistent ratio. Depending upon the makeup of the combination, there are somewhere between $1$ and $24$ permutations. It varies over all the combinations with repetition.