# Set counting problem with a cap on the intersection between the set and a fixed partition

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.

1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there such that $|C|=k$ and $\max_{i}|T_i\cap C| = j$? Call this number $n(m,k,j)$ and call $N(m,k,j)$ the cumulative version where $\max_{i}|T_i\cap C| \le j$.

2) More generally, how many sets of the form $\{C_1,\ldots,C_m\}$ are there such that $C_1,\ldots,C_m$ is a $k$-partition of $[k\cdot m]$ where $\max_{i,\ell} |T_i\cap C_\ell| = j$?

Are asymptotic answers known/obvious for either of these two questions?

Note for the first question, an exact but clunky formula is given by the recursion: $$N(m,k,j) = \begin{cases} 0 & j < k/m \\ \binom{m}{k}k^k & j=1\text{ and }m\ge k\\ \sum_{i=0}^{\left\lfloor\frac{k}{j}\right\rfloor} \binom{m}{i} \binom{k}{j}^i N(m-i,k-ji,j-1) & \text{ otherwise} \end{cases}$$ (Choose the $T_i$'s that get exactly $j$ elements of $C$, then the locations of the $j$ elements in each of the chosen $T_i$'s, then choose the rest.)

In addition, the probability that a (uniformly) random set will have intersection more than the mean $k/m$ can be lower-bounded by choosing each element of $C$ independently, then using Chernoff and union bounds: $P[\max_i(T_i\cap C)-k/m > t] \le k e^{-2t^2/k}$. Then $$N(m,k,j) \ge N(m,k,k)(1-k e^{-2(j-\frac{k}{m})^2/k}).$$ A similar result can be shown for the second problem as well. Is this bound asymptotically tight?

• For the asymptotics that interest you, which parameters remain fixed and which go to infinity? Sep 10 '15 at 1:54
• Just saw this comment. I'm interested in the case when, for $n=mk$, $n$ goes to infinity, $k$ is a function of $n$, say $log(n)$, $m=n/k$, and $j$ is arbitrary. Mar 26 '16 at 20:33

$N(m,k,j)$ equals the coefficient of $x^k$ in $$\left(\sum_{i=0}^j \binom{k}{i} x^i\right)^m.$$