I have the following exact sum for the expectation of an event


$$\sum\_{m=0}^{nk} \sum\_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}$$


which is exactly correct but I want to give an upper bounding approximation that is easier to interpret. In particular, I want to see the expectations dependence on the parameter $k$. In simulation, it appears that as $k \rightarrow \infty$ we have that the sum tends towards $n \log n$. However, I am unsure how to show such a result analytically. My attempt has been to use some form of a stirling approximation on the binomial coefficients like
$$\binom{n}{k} \leq \frac{n^k}{k!}$$
which can reduce the summation in the following way
$$\sum\_{m=0}^{nk} \sum\_{j=1}^n (-1)^{j-1}\binom{n}{j} \frac{((n-j)k)^m}{m!} \cdot \frac{m!}{(nk)^m} = \sum\_{m=0}^{nk} \sum\_{j=1}^n (-1)^{j-1}\binom{n}{j} \left(1-\frac{j}{n}\right)^m$$
and from here maybe we can upper bound the $(1-j/n)^m$ to simplify further to a sum which depends only on $j$? Again comparing to simulation, it seems that when $k \ll \log n$ the sum will be something like $nk$ and for $k \gg \log n$ we will have the $n \log n$ (thus removing the dependence on $k$) but I can't seem to derive such a result.


Any help or advice would be *greatly* appreciated!



Approximating binomial coefficient sum
Actually we may simply compute this sum (and I guess that your expectation may be computed differently to give the answer in the below simplified form).
We start with $1/{nk\choose m}=(nk+1)\int\_0^1 x^m(1-x)^{nk-m}dx$ by the Beta function $B(a,b)=\Gamma(a)\Gamma(b)/\Gamma(a+b)$ formula. Next, we sum up over $m$ with fixed $j$ to get
$$
\sum\_{m=0}^{nk}\frac{(n-j)k\choose m}{nk\choose m}=(nk+1)\int\_0^1 (1-x)^{jk}\sum{(n-j)k\choose m}x^m(1-x)^{(n-j)k-m}dx\\=(nk+1)\int\_0^1(1-x)^{jk}\left(x+(1-x)\right)^{(n-j)k}dx=(nk+1)\int\_0^1(1-x)^{jk}dx=
(nk+1)\int\_0^1 t^{jk}dt.
$$
Then sum up over $j$ to get
$$
\sum\_{m=0}^{nk} \sum\_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}=(nk+1)\int\_0^1\sum\_{j=1}^n(-1)^{j-1}{n\choose j}(t^k)^jdt\\=(nk+1)\int\_0^1(1-(1-t^k)^n)dt=(nk+1)\left(1-\frac1k\int\_0^1(1-s)^ns^{1/k-1}ds\right)\\=(nk+1)\left(1-\frac{\Gamma(n+1)\Gamma(1/k)}{k\Gamma(n+1/k+1)}\right)=(nk+1)\left(1-\frac{1\cdot 2 \cdot 3\cdot \ldots n}{(1+1/k)(2+1/k)\ldots (n+1/k)}\right).
$$
Now your observation follows, for example, from
$$
\frac{\ell}{\ell+1/k}=\left(\frac{\ell}{\ell+1}\right)^{1/k}\cdot e^{O(1/(\ell^2 k))},
$$
thus multiplying against $\ell=1,\ldots,n$ we get
$$
\frac{1\cdot 2 \cdot 3\cdot \ldots n}{(1+1/k)(2+1/k)\ldots (n+1/k)}=\frac{e^{O(1/k)}}{(n+1)^{1/k}}=\exp\left(-\frac{\log n+O(1)}k\right),
$$
therefore in the $\log n=o(k)$ regime using $1-\exp(-t)\sim t$ for small $t=\frac{\log n+O(1)}k$ we indeed get $n\log n$ asymptotics for your sum.


