New answers tagged

1

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]...


Top 50 recent answers are included