Consider $n$ numbers randomly generated by independent generators that can produce integers from $0$ to $n$. How many of these integers will be missing on average for large $n$? If $p_{k,n}$ is the probability that $k$ is generated by a given generator then the probability that it is missing from all $n$ is $(1-p_{k,n})^n$, so $E_n=\sum_{k=0}^n(1-p_{k,n})^n$ is the expected number of misses. If all $k$-s were equally likely, i.e. $p_{k,n}=\frac1{n+1}$, it is easy to estimate: $E_n=\sum_{k=0}^n(1-\frac1{n+1})^n\sim\frac{n+1}e+\frac12+O(\frac1n)$, i.e. just over a third of integers will be missing.

I am interested in the case when the numbers are generated binomially: there are $n$ heaps of objects with $n$ in each heap, and each one is kept or discarded with probability $\frac12$. The resulting number of objects in a heap is then $k\leq n$ with probability $p_{k,n}=\frac{C_n^k}{2^n}$. For this distribution we expect the counts to cluster symmetrically around $k=\frac{n}2$, so using the Stirling formula or the local limit theorem $p_{k,n}\sim\frac1{\sqrt{\pi n/2}}e^{-\frac{(k-n/2)^2}{\pi n/2}}$, and after shifting and rescaling $E_n\sim2S_{\frac{n}2}$, where $$S_n=\sum_{k=0}^n\Big(1-\frac1{\sqrt{\pi n}}e^{-\frac{k^2}{\sqrt{\pi n}}}\Big)^{2n}.$$ If not for the $2n$-th power there are standard methods using Mellin transforms or the Euler-Maclaurin formula to find asymptotics of such sums, but as is...

Using the binomial formula on the inside looks like a bad idea, it produces terms with positive powers of $n$ and alternating signs, so there must be massive cancellations since obviously $S_n\leq n+1$. There are thresholds for terms' behavior at large $n$. Let $$k_{n,\varepsilon}^2:=(\frac12+\varepsilon)\pi n\ln n+\frac12\pi\!\ln\pi\,n,$$ then the summands are exponentially close to zero if $k\leq k_{n,-\varepsilon}$ and inverse power close to $1$ if $k\geq k_{n,\varepsilon}$. So $$\big(n+1-k_{n,\varepsilon}\big)\big(1-O(n^{-\varepsilon})\big)\lesssim S_n\lesssim n+1-k_{n,-\varepsilon}.$$ This does imply that the fraction of missing integers approaches 1 for large $n$, but it is not exactly sharp, and I do not see how to make it so (one can improve on it slightly by noticing that for $k^2\gtrsim n^{1+\varepsilon}$ the terms are exponentially close to $1$). There is an intermediate range with $k^2:=\frac12\pi n\ln n+\frac12\pi\!\ln\pi\,n+O(1)$, which corresponds to summands $(1-\frac{c}n)^{2n}\sim e^{-2c}$, with $c$ from $O(1)$. It almost seems like one has to sum or integrate over "ranges" with orders of growth in place of numbers and then add the results. But I do not know what that can mean exactly for the intermediate range, and I have not seen anything of this sort done. Perhaps, one should "change variables" to transform the range somehow.

Any advice/ideas/references are appreciated. It is entirely possible that I am on the wrong track, this seems like a reasonable probabilistic/combinatorial question and there might be standard methods for asymptotics of such sums that I missed. This example is representative of a type I am interested in, with sums of $n$-th powers of terms close to $1$.