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?

  • 3
    $\begingroup$ For the asymptotics that interest you, which parameters remain fixed and which go to infinity? $\endgroup$ Sep 10, 2015 at 1:54
  • $\begingroup$ 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. $\endgroup$
    – chirpchirp
    Mar 26, 2016 at 20:33

1 Answer 1


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

  • 2
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$ Jul 9, 2015 at 7:27
  • 10
    $\begingroup$ @MarcoGolla: This is neither critique, nor request for clarification. While it's not a complete answer either, it provides an insight into one of the quantities defined by the author. Comments do not format complex formulae nicely. $\endgroup$ Jul 9, 2015 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.