Birthday square-root scale ($n\asymp \sqrt{m}$)

The union bound gives $P_{n,m}\le \min (1,n(n-1)/(2m))$. Using $1-x\le e^{-x}$ on the distinct-label product givesThe lower bound reaches at least one half when $n(n-1)/(2m)\ge \log 2$. The simple approximation $n\approx \sqrt{2m\log 2}$ predicts a group size near 23 for $m=365$. It is the quadratic number of pairs that makes the square root appear.

For a precise limiting statement, let $m\to \infty$ and $n/\sqrt{m}\to c\ge 0$. Expanding the logarithm of the complement yieldsOn this scale the remainder tends to zero. Thus a fixed substantial collision probability appears after order $\sqrt{m}$ draws. For $m=2^b$ uniform output labels, the corresponding scale is order $2^{b/2}$; matching one specified birthday instead involves a number of draws of order $m$.