Generalized birthday paradox Given $n$ random variables $X_1,...,X_n$ chosen uniformly and independently from $\{1,...,n\}$, I wish to prove that for every constant $c$, with probability $1-o(1)$ (when $n$ grows) there will be $c$ random variables with the same value (for $c=2$ it's a birthday problem).
What I tried is to define, for each subset of size $c$ of the variables an indicator $Y_i$ which equals to $1$ iff all the values in the subset are the same. It holds that: $$Pr(Y_i = 1) = \frac{1}{n^{c-1}} $$ Later, I defined $Y = \sum Y_i$, and it can be seen that : $$E[Y] = {n \choose c} \frac{1}{n^{c-1}} $$ which clearly goes above $1$ when $n$ gets large enough.
I believed that the next step would be bounding the probability that $Y$ is far from its expectation (using, for example Chernoff bound). The thing is, the $Y_i$s are dependent on each other (for example, two such indicators with only one variable different between them: knowing that one indicator is $0$ implies that the other one is $0$ as well) - so it is a problem to use that type of bounds. Any idea about how to proceed? 
 A: This can be done using Chebyshev: bound the variance and show that it is not too much larger than the mean. Then $P(Y=0)\leq\text{Var}(Y)/E(Y)^2$.
Now when a variable counts the number of events in some set $A$ which occur, like this one, you can express the variance as
$$\text{Var}(Y)=\sum_{a,b\in A}(P(a,b)-P(a)P(b)).$$
Here all the terms where $a$ and $b$ involve disjoint $c$-tuples (or pairs that overlap in exactly one place) are independent events and contribute $0$ to this sum. If they overlap in $d$ places, where $2\leq d\leq c$ then the event that $a$ and $b$ occur is the event that some $2c-d$ of the $X_i$ are equal. Each group of $2c-d$ is counted $\binom{2c-d}{d}\binom{2c-2d}{c-d}$ times (the number of ways to choose the overlap and then split the rest into two equal groups) - it doesn't matter what this number is, since it doesn't depend on $n$. So the contribution from these pairs is $$\binom{2c-d}{d}\binom{2c-2d}{c-d}\binom{n}{2c-d}\bigg(\frac1{n^{2c-d-1}}-\frac1{n^{2c-2}}\bigg).$$
This is of order $n$ for every $d$. For fixed $c$ there are a constant number of choices for $d$, and so the variance is $\Theta(n)$. Since the mean is also $\Theta(n)$, this is sufficient.
