Problem with injective functions on an explanation of the Birthday problem

Question

The Wikipedia article on the Birthday problem gives an "abstract proof" of the problem, in which the birthday function

$$ b:\mathcal{S} \mapsto \mathcal{B} $$

where $\mathcal{S}$ is the set of $\mathcal{N}$ people and $\mathcal{B}$ the set of dates in the year.

Since $|\mathcal{S}| = N$ and $|\mathcal{B}|=366$, it follows that there are $366^N$ possible functions, and $\dfrac{366!}{(366-N)!}$ possible injective functions

Firstly, I am having trouble understanding why $|\mathcal{B}|=366$ instead of 365, unless it is including some date that's only present on a leap year, in which case I'm just stupid.

Secondly, I do not know how $\dfrac{366!}{(366-N)!}$ was obtained, as I have read that to find the number of injective functions of $f:\mathcal{X} \mapsto \mathcal{Y}$, one does something like $x(x-1)\cdots(x-n+1)$ where $n$ is $|\mathcal{S}|$. Does this arise through the expansion of the progression, or is there something I'm missing?

The article then goes on to say that

P(A) is the fraction of injective functions out of all possible functions (i.e., the probability of the birthday function being one that assigns only one person to each birthdate), which gives $P(A) = \dfrac{366!}{366^N(366-N)!}$.

I can't think of how the $366^N$ arrived on the bottom.

If this question does get answered, please forgive my mathematical naivete; I only happened to learn about injective functions as I was looking into how the Birthday problem is proven.

As an alternative to answering the question, I'd also be happy if someone could show me a different proof of the same problem, as I haven't found many that I can understand in the way of using search engines.

Thank you.

Answer 1

1) They are using 366 instead of 365 to take February 29th into account.

2) $\displaystyle\frac{366!}{(366-N)!}$ does correspond to what you have for the number of injective functions, since

$\;\;\displaystyle\frac{366!}{(366-N)!}=\frac{366\cdot365\cdot364\cdots(366-N+1)(366-N)(366-N-1)\cdots3\cdot2\cdot1}{(366-N)(366-N-1)\cdots3\cdot2\cdot1}$

$\hspace{.8 in}=366\cdot365\cdot364\cdots(366-N+1)$

3) They are using $\displaystyle\frac{\frac{366!}{(366-N)!}}{366^N}=\frac{366!}{366^N(366-N)!}$

Answer 2

The Wiki article would get a 0 on a probability course.You cannot compute odds by dividing the number of favorable cases by the total number of cases UNLESS (1) No two of the cases can occur at once AND (2) Each case has equal probability. In the Birthday Problem, (1) is true but (2) is false. The solution in the article may be approximate ( depending on how much accuracy you want) but is not exact. For instance with N=2, the formula gives odds of 1/366 but the correct value is $ \frac {1} {365 \frac {1} {4}}$......BTW your Q about "how the $366^N$ arrived on the bottom" is that they divided the number of injective functions by the number $366^N$ of all functions. As I said, this is a wrong method anyway because (2) is false.