How many boxes so that there is $k$ of same of color from $n$ different colors? Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than $\frac{1}{2}$?
If $k = \Theta(n^{c})$, then what is $m$ if $c < 1$, $c > 1$? Is $m = \Omega(n^{c+1})$ in general?
I was trying to generalize birthday paradox problem. By Pigeon hole I can get only $m=\Omega(n^{2})$ if $k=O(n)$ for 'certainty'. Using pigeon hole I cannot give a probabilistic argument here. Was curious for general sizes of $m$, $n$ and $k$ and what would replace pigeon hole?
http://www.math.ucsd.edu/~tkemp/180A/180A.LectureNotes.pdf says answer for $n=365$ and general $k$ was not known till $1995$ but does not provide reference. 
In this problem, there are two cases: $k < n$ and $k > n$.
 A: Googling on "birthday problem 1995" turns up references to a paper by L. Holst, the abstract to which reads

The general birthday problem with unlike birth probabilities and the
  waiting time N until c people with the same birthday have been
  obtained is studied in this article. It is shown that N is
  stochastically largest when the birth probabilities are equal. By
  embedding in Poisson processes it is shown how the moments of N can be
  expressed in moments of the minimum of gamma random variables.

The Holst paper doesn't appear to be available online, but a later paper by Camarri and Pitman may be worth a look.
A: Edit: This answer was for $k$ fixed, rather than $k = \Theta (n)$ as specified in the original question.
You should be able to use (for example) Talagrand's concentration inequality to show that the number of k-sets which are all the same colour is tightly concentrated.  So the critical value for $m$ should satisfy $\binom m k / n^{k-1} \approx 1$, i.e. $m \approx n^{1-1/k}$, which happily agrees with the answer for the birthday problem.
There are lots of details to check here if you want to make sure this argument holds water.
