About combinations with repetitions

Question

I'm studying the topic of combinations with repetitions and I came across this formula of selecting r objects from N object types $$ \binom{N-r+1}{r} $$ and I am totally fine with it. But there is another approach that I can't stop thinking about is that we can also think of it as first selecting 1 object from $N$ types i.e. $$\binom{N}{1}$$ and doing this process $r$ times to get all $r$ objects. Therefore, $$ \binom{N}{1}^r = N^r $$ Is it wrong and if it is, please tell what is wrong with this approach.

Answer 1

Your approach is wrong because you count many combinations multiple times. For example, the combinations $S_1 ab S_2$ and $S_1 ba S_2$ ($S_1$ and $S_2$ are strings) are actually identical and combinations but appear separately in your method of counting.

On top of that, the formula that you gave should've been ${n+r-1 \choose r}$. It's simple application of stars and bars theorem.

Answer 2

Both your answers are wrong. As the commenter suggests, I think the approach you are thinking of is really ${N \choose 1} ^ r$, or $N^r$. I believe this because this is what you would get if you actually picked $N$ times; I think you just mixed up multiplication and exponentiation in your question.

This would be correct if repetitions where allowed. We can see this with $N=3$ and $r=2$. If no repetitions are allowed, there are only three combinations without repetitions (if you don't believe that, work it out physically counting them). This serves as a counterexample to all three discussed approaches, which would be $2 \times 3=6$ or $3^2 = 9$ or ${2 \choose 1} = 2$.

The issue is that you aren't picking from $N$ objects $r$ times really, as that allows repetitions. Instead you are really picking from $N$ once, then $N-1$ the next time ($N$ minus the one you've already picked), continuing in this pattern until you have picked r. This makes the answer just $N(N-1)\dots(N-r+1) = {N \choose r}$. Your original formula from, but it is incorrect and instead is about combinations with repetition, not without repetition as you initially asked (EDITTED).

For reference

Edit: Now that you fixed your question and noting that it says with repetitions now, $N^r$ is wrong as this would be the number of permutations. Permutations are where order matters, while with combinations, {1,2} and {2, 1} are the same result. Another example would be all alphabetical strings of length 2. "AL" and "LA" would be considered the same string if you are talking combinations, but if you are talking permutations, they'd be different. $N^r$ counts both versions, while the other equation does not.