TLDR; I would like to prove that there is an $L \in (0,1)$ such that: $$\sum_{j=0}^{k/2} \frac{3^{k-j} \binom{n/3}{j}\binom{n/3-j}{k-2j}}{\binom{n}{k}} \to L \qquad (k = \lceil n^{2/3} \rceil, n \to \infty)$$


Let $n,k \in \mathbb{N}$. For technical reasons which will become apparent later, we require: $$n \equiv 0 \mod 3 \qquad \text{and} \qquad k \equiv 0 \mod 2$$ Suppose we have the set $[n] := \{1,2,\dots,n\}$, and we select a subset $X \subseteq [n]$ such that $|X| = k$ uniformly at random. I'm interested in the probability that none of the sets $\{1,2,3\}, \{4,5,6\}, \dots, \{n/3-2,n/3-1,n/3\}$ is a subset of $X$.

One can quite easily derive that the probability that none of these sets is a subset of $X$ is given by the following expression: $$\sum_{j=0}^{k/2} \frac{3^{k-j} \binom{n/3}{j}\binom{n/3-j}{k-2j}}{\binom{n}{k}}$$ Numerical experiments now show that if we choose $k = \lceil n^{2/3} \rceil$, then this probability converges to a constant $L \in (0,1)$ when $n \to \infty$. I would like to prove this (or disprove if it were false, of course), but I am having trouble figuring out the correct method. Any help would be greatly appreciated.

My attempts

I tried using known bounds on the binomial coefficients, e.g.: $$\left(\frac{n}{k}\right)^k \leq \binom{n}{k} \leq \left(\frac{ne}{k}\right)^k$$ But whenever I apply these bounds, numerical experiments seem to indicate that they are not tight enough. I also tried to expand the binomial coefficients into factorials and using Stirling's approximation, but the resulting expressions become very cumbersome.

  • $\begingroup$ Writing your sum as $\binom{n}k^{-1}\sum_{j=0}^{k/2}a_j$, the first step should be to find the value of $j$ for which $a_j$ is maximized. Letting $m(k)$ be the value of $a_j$ for this $j$, the sum is bounded between $m(k)$ and $(k/2)m(k)$, which are close bounds since $m(k)$ should be exponential in $k$. Then, you just have to apply stirling's approximation to $m(k)$. Note that you can find where the maximum is by considering $a_{j+1}/a_j$; the maximum occurs when this ratio is close to $1$. $\endgroup$ Commented May 13, 2019 at 21:27


You must log in to answer this question.