# upper bound on sum of product of binomial coefficients

For positive integers $$\ell < m < n$$, consider a partition of $$[2n]$$ into two $$n$$-element sets $$(X,Y)$$. How many ways are there to choose an $$m$$-subset $$A \subset [2n]$$ such that the size of the intersection $$A \cap X$$ is at least $$\ell$$?

I believe this quantity is given by the following sum: $$S_{\ell,m,n} := \sum_{j=0}^{m-\ell}{n \choose m-j} {n \choose j}.$$

If my reasoning is correct, is there a way to obtain a non-trivial upper bound (i.e. approximation) for $$S_{\ell,m,n}$$?

• I assume you are interested in some asymptotic bounds. If so —- which regime you are in? I.e., what are the relative growth rates of the parameters? Jun 9 at 8:50
• The largest value occurs at $j=m/2$ and close to there it is approximately normal unless $m$ is small or close to $n$. Jun 9 at 13:11

I agree with your formula. You choose $$j \in \{0,\ldots,m-\ell\}$$ (it will be the cardinal of $$A \cap Y$$, and given such a $$j$$ you choose independently $$j$$ elements in $$Y$$ and $$m-j$$ elements in $$X$$.
$$S_{\ell,m,n} \le \sum_{j=0}^{m} {n \choose m-j} {n \choose j} = {2n \choose m}.$$ One obtains the last equality by looking at the coefficient of $$X^m$$ in the product $$(1+X)^n \times (1+X)^n$$. My guess is that this bound is sharp when $$m/2-\ell >> \sqrt{m}$$.
The quotient $$S_{\ell,m,n}/{2n \choose m}$$ is the probability $$\mathbf{P}[X \ge \ell]$$ where $$X$$ is a random hypergeometric random variable with parameters $$2n$$, $$n$$ and $$m$$. The law of $$X$$ is symmetric with regard to $$m/2$$ and is less spread out than the binomial law with parameters $$m$$ and $$1/2$$ (sampling without replacement provides a least dispersion of the number of success).
More precisely, given binomial random variable $$Y$$ with parameters $$m$$ and $$1/2$$, I guess that when $$\ell \ge m/2$$, $$2\mathbb{P}[X \ge \ell] = \mathbb{P}[|X-m/2| \ge \ell-m/2] \le \mathbb{P}[|Y-m/2| \ge \ell-m/2] = 2\mathbb{P}[Y \ge \ell].$$ Does anyone have a reference or a proof of this fact? Then, Cramer-Chernoff inequalities give nice bounds.
• @Ilya Bogdanoiv. You are right. Giving a too simple answer can be a way to get more precisions on the nature of the bound wished (is it wanted for $\ell/m$ close to $0$, close to $1/2$, close to $1$ ?). Anyway, I completed my answer to give a less trivial bound when $\ell \ge m/2$. Jun 9 at 21:32