Consider $n$ people who are attending a party. We assume that every person has an equal probability of being born on any day during the year, independently of everyone else, and ignore the additional complication presented by leap years (i.e., nobody is born on February $29$). What is the probability that each person has a distinct birthday?
The solution to this problem is $\frac{365 \cdot 364 \cdot \ldots \cdot (365 – n + 1)}{365^n}$.
I was wondering why the sample space contains birthday lists like $b_1b_2\ldots b_n$. Why don't we choose $n$ places out of $365$ instead? I am not sure but to me it seems like the order shouldn't matter here.
Best Answer
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.$