# Tag Info

Let $B_j$ be the number of balls in the $j$'th bin. Then $$\mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right] = \sum_{i_1 < \cdots < i_k} \Pr[h(i_1) = \cdots = h(i_k)] = \frac{\binom{n}{k}}{n^{k-1}} \leq \frac{n}{k!}.$$ Let $C_j = B_j - (k-1)$. Then  \mathbb{E}\left[\sum_{j=1}^n C_j^k\right] \leq k! \mathbb{E}\left[\sum_{j=1}^n \binom{B_j}{k}\right]...