Birthday-paradox for big numbers and more than one person: Computing the approximate probability of $k$ hash collisions for $n$ hashes Given a cryptographic hashing function, with say a $256$  bit-length, I want to calculate the probability that out of $n$ hashes we have at least $k$ hashes that collide in the first $32$-bit (assuming the $n$ hashes are uniformly distributed over all $2^{32}$ possible prefixes). Assume $k$ and $n$ are very high, something like $k=2^{32},n=2^{64}$. This reminds me of the birthday paradox but for more than $2$ people. I found this post, which suggest using an poisson approximation which from my understanding would result in the formula:

$$ P(\text{at least $k$ hashes in $n$ trials share the same prefix}) =$$
$$ 1 - \exp \left (-{n \choose k}/(2^{32})^{(k-1)} \right )$$

because if we would check every combination of $k$ hashes in the set $n$ hashes, we would on average have $\lambda = {n \choose k}/(2^{32})^{(k-1)}$ combinations that share the same $32$ bit prefix.

The problem with that that formula is that the calculations take too long. For example, calculating the number $(2^{32})^{2^{32}-1}$ is simply too complex. Is there any other way I can approximate this probability while remaining in the computationally feasible area?
For large $k$ growing with $n$ the binomial coefficient needs to be approximated. 

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have
$$
\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}
$$
where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $k$.

This result appears, e.g., in Bob Gallager's book Information Theory and Reliable Communications.

This will give a good approximation if you use the upper bound. 

So, you have
$$
1-\exp\left[-\frac{\sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}}{\exp\{(k-1)\ln 2^{32}\}}\right]
$$
and can further take differences of the exponential function arguments inside and simplify for $n=2^{64},k=2^{32},$ to
$$
1-\exp\left[-\sqrt{\frac{n}{2\pi k(n-k)}}\exp\left(nh(k/n)-(k-1)\ln 2^{32}\right)\right]\approx$$
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(nh(1/k)-(k-1)\ln 2^{32}\right)\right]
$$
or
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(nh(2^{-32})-2^{32}\ln 2^{32}\right)\right]
$$
and since for large $k$, $h(1/k)\approx \ln k,$
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(n \ln 2^{32})-2^{32}\ln 2^{32}\right)\right]
$$
$$
\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left((2^{64}-2^{32}) \ln 2^{32}\right)\right]\approx
$$
$$
\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(2^{64} \times 32 \ln 2 \right)\right]
$$