9 - Random Grouping

There are $N$ students numbered $1, 2, \ldots, N$. Their teacher wants to group them. The teacher is a fan of randomness and uses the following : Let $g$ denote the current number of groups. First the teacher makes one group containing the student $1$. So, initially $g = 1$. Now, for each student $i$ from $2$ to $N$ in this order: - With probability $1 / (g + 1)$, he creates a new group containi