Birthday Problem. This is the famous 'birthday problem' or, because some people find the
answer surprising 'birthday paradox'. There are lots of links to it on
this site and elsewhere on the Internet, so I will get right to the point, and just
try to answer your specific question.
Often when sampling is 'with replacement' it is more convenient to
look at ordered outcomes. The birthday problem clearly involves sampling with
replacement because it is possible for a birthday to be selected more
than once.
There are many problems that can be answered with either ordered or
unordered samples. The important thing is that if you are using
ordered samples in the denominator (to count outcomes in the whole
sample space), you must also use ordered samples in the the numerator
(to count 'favorable' outcomes). In the birthday problem it
is especially easy to use a sample space with $365^n$ ordered samples in the denominator,
so it is natural to start with that and, accordingly, to use ordered
samples in the numerator.
Urn Problem. Here is a problem in which you can use either ordered or unordered
outcomes: I have an urn containing 5 balls, 3 red and 2 green. I withdraw
two balls without replacement. What is the probability I get two balls
of the same color:
Ordered (permutations).
Count all ordered outcomes in denominator: $5(4) = 20.$
Numerator. Ways with two red: $3(2) = 6.$ Ways with two green: 2(1) = 2.
Answer. $(6+2)/20 = 2/5$
Unordered (combinations).
Denominator: ${5 \choose 2} = 10.$
Numerator: Both red: ${3 \choose 2}{2 \choose 0} = 3.$
Both green: ${2 \choose 2}{3 \choose 0} = 1.$
Answer: $(3 + 1)/10 = 2/5.$
However, suppose my task to find the probability that I choose a red ball
and then a green ball. This new problem involves order, and I have no choice
but to use ordered outcomes throughout: $6/20 = 3/10.$