Derivation of birthday paradox probability I am trying to come up with an explanation of the probability of birthday collision. 

$P$(no collision among t people) = $(1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365})$


  For one person, the probability of no collision is 1, which is trivial
  since a single birthday cannot collide with anyone else’s. For the
  second person, the probability of no collision is 364 over 365, since
  there is only one day, the birthday of the first person, to collide
  with:
  
  $P$(no collision among 2 people) = $(1− \frac{1}{365})$
  
  If a third person joins the party, he or she can collide with both of
  the people already there, hence:
  
  $P$(no collision among 2 people) = $(1− \frac{1}{365})·(1−\frac{2}{365})$


While it is clear how we get the probability of collision for 2 people, it is not intuitive to me that how we get the probability of collision between 3 people. I'd expect the probability would be $(1−\frac{2}{365})$. For example, when you roll the dice, the probability of $6$ is $\frac{1}{6}$, and the probability for 5 or 6 is $\frac{2}{6}$. It is not $\frac{1}{6}$·$\frac{2}{6}$ which seems to be the case in birthday collisions.

I'd appreciate an answer with an intuitive explanation.
The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room.

Before the first person enters, there's no collision/coincidence of birth-date, thus probability of no collision is $P_0=1$.

When the first person enters, there can't be a collision/coincidence of birthdate, probability of no collision is $P_1=1$.

When the second person enters, there is one chance in $365$ that his/her birthday is the same as the first person's birthdate, thus the probability of no collision is $P_2=1-\frac1{365}$.

When the third person enters, either
- there was a collision at the previous stage, and then the probability of no collision is $0$;
- or there was no collision at the previous stage, thus there was $2$ persons with different birth-dates in the room, and the probability that the third person has one of their birth-dates is $2$ in $365$, thus the probability of no collision is $1-\frac2{365}$.
The total probability of no collision after the third person enters is obtained by adding these two probabilities weighted by the probability conditioning them. We thus have $P_3=(1-P_2)\,0+P_2\,\bigl(1-\frac2{365}\bigr)$, thus $P_3=\bigl(1-\frac1{365}\bigr)\bigl(1-\frac2{365}\bigr)$

The same reasoning gives $P_{i+1}=(1-P_i)\,0+P_i\bigl(1-\frac i{365}\bigr)$, that is $P_{i+1}=P_i\bigl(1-\frac i{365}\bigr)$.

From which it comes $P_t=\displaystyle\prod_{i=0}^{t-1}\,\Bigl(1-\frac i{365}\Bigr)$.

For derivation of formulas used in a cryptographic context where the numbers are huge, see my Birthday problem for cryptographic hashing, 101.
Note: $P$, $t$, and $365$ here are $q$, $n$ and $k$ there.