Solving this inequality involving permutation.

Question

How would you solve the following inequality:$$1-\frac{P(365,n)}{365^n}\ge0.5$$ This inequality comes from the birthday problem. I am trying to solve how big a group needs to be in order for the chance to be 50%, I know it's 23 people but I am wondering how you would get that from this equation

Answer 1

The quantity $\frac{P(365,n)}{365^n}$ is the product of terms $$ \frac{365-k}{365}=1-\frac k{365}\tag1 $$ as $k$ ranges from $0$ to $n-1$. The simple approximation $1-t\approx e^{-t}$ works surprisingly well here, since we're dealing with $t=\frac k{365}$ not too far from zero. This gives the approximation $$\frac{P(365,n)}{365^n}\approx\exp \left(- \frac1{365}\left[ 0+1+2+\cdots+(n-1)\right]\right)=\exp\left(-\frac{(n-1)n}{2\cdot 365}\right).\tag2$$ The RHS of (2) equals $0.499998$ when $n=23$, which means the probability $1-\frac{P(365,n)}{365^n}$ just barely exceeds $0.5$ at that value of $n$.

Answer 2

Using the same approach as grand_chat in his/her answer $$a_n=\frac{P(365,n)}{365^n}=\prod_{k=0}^{n-1}\left(1-\frac k{365} \right)$$ $$\log(a_n)=\sum_{k=0}^{n-1}\log\left(1-\frac k{365} \right)$$ Now, assuming that $n \ll 365$ and using Taylor series and then Faulhaber's formulae $$\log(a_n)=-\sum_{k=0}^{n-1}\left[\frac k{365}+\frac 12 \left(\frac k{365} \right)^2+\cdots\right]=-\frac{n(n-1) (2 n+2189)}{1598700}$$ which is a quite accurate approximation.

So, solving for $n$ $$1-\frac{P(365,n)}{365^n}= c\implies \log(a_n)=\log(1-c)\implies \frac{n(n-1) (2 n+2189)}{1598700}=-\log(1-c)$$ and you have a cubic equation to solve (only the positive root is of interest). The expression will be ugly but totally workable for a given value of $c$.

This works fine even for large values of $c$. For example, using $c=0.99$, this would give $n=57$ which is the correct answer.

Edit

If you want a shortcut approximation, you could use as an approximation (I use whole numbers to make it looking "nicer") $$n(n-1) (2 n+2189)\approx \frac{1969836 }{1183}n^{{2626}/{1265}}$$ which would give $$n=\left(-\frac{157605175}{164153}\,\log(1-c)\right)^{\frac{1265}{2626}}$$ which is quite accurate.