Probability in ball coloring You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ball can be given a color $i$ with probability $\frac{1}{n^2}$ (uniform probability of assignment of colors). You pick $n^{b}$ balls without replacement. What is the probability that atleast $n^{a}$ balls are of the same color with $0 < a < b \leq 2$? Floor any real numbers to get integers - in any case - I am looking for asymptotic bounds.
 A: Presumably you are drawing with replacement.  We assume you want exactly $n^a$ that match, with the rest non-matching.  If you just want at least $n^a$, you have to sum over $n^a$ up to $n^b$.  If $2n^a \gt n^b$ it is easier, as you can't get two sets of the same color.  There are $(n^2)^{(n^b)}$ ordered draws.  To get $n^a$ that match, you can choose the positions of the matching ones in ${n^b \choose n^a}$ ways, the color in $n^2$ ways, and the remaining colors in $(n^2-1)^{(n^b-n^a)}$ ways.  So we have a probability of $$\frac {{n^b \choose n^a}n^2(n^2-1)^{(n^b-n^a)}}{(n^2)^{(n^b)}}$$
This will overcount if $2n^a \le n^b$ because times you get two groups of $n^a$ are counted twice and so on.  There is no magic in making everything powers of $n$-you could as easily use $a,b,n$ for the numbers.  It should be clear how to modify the expression to do that.
A: Note that you don't have to account for initially choosing the $n^b$ balls out of $n^2$. In particular, we could start with just $n^b$ balls and ask what is the probability that at least $n^a$ have the same color. Let $X$ denote the number of sets of $n^a$ balls of the same color, so we wish to bound the probability that $X$ is at least 1. So
\begin{align*}
P(X \geq 1) \leq E[X] &= \sum_{A : |A|=n^a} P(\text{the balls of }A\text{ are mono colored})
\end{align*}
For any specific such set of balls $A$, note that this probability is exactly 
$$\left( \frac{1}{n^2} \right)^{|A|-1},$$
since the first ball can be any color, but each of the following balls of $A$ must be the same as the first one.
Hence
\begin{align*}
P(X \geq 1) &\leq {n^b \choose n^a} \left( \frac{1}{n^2} \right)^{n^a-1} \leq \left( \frac{e n^b}{n^a} \right)^{n^a} \left( \frac{1}{n^2} \right)^{n^a-1} \\& \leq n^2 \left( \frac{e n^b}{n^a n^2} \right)^{n^a}=\exp \left( -n^a(2-b+a)\ln n+o(n^a \ln n)\right).
\end{align*}
