I tried to solve the question
How many ways are there to pick $k$ times from a set of $n$ objects with replacement?
in the following way.
First I imagined $k$ fair dice, each with $n$ sides. If the order does not matter the number of different outcomes from the experiment is $\frac{n^k}{k!}$. This is wrong and I fail to recognize error in my thinking.
If I instead think of the problem in terms of putting $k$ balls into $n$ urns and then use the famous method of representing the balls as stars and bars as urns I arrive at the correct answer $\binom{n+k-1}{k}$.
However, to me these formulations seems to be analogous because the number of times the dice show the same side in a given experiment could represent the number of balls in a specific urn. Where is the error?
Best Answer
In your "$k$ fair $n$-sided dice" setup, imagine $n=k=2$ for simplicity: you're flipping two coins, each of which can come up either heads or tails. There are three possible outcomes if order doesn't matter, namely HH, HT, TT, while your formula would give $2^2/2! = 2$.
The problem is that among the "ordered" outcomes HH, HT, TH, TT, the outcomes HH and TT are only coming up once, hence dividing by $2!$ to fix the "overcount" of those outcomes (which is correct for HT/TH) is actually causing an undercount.