This one is a classic that I believe is found in one of the popular interview books. You start with N pieces of strings that are mixed into a single pile. You start randomly choosing two free ends at a time and joining them together. After N rounds, you will be done as there will be no more free ends left. If the number of closed loops is k, what is F = E[k]?
If you go down the combinatorial path, you will soon see how hopeless it is to try figuring out the many different intermediate states. So perhaps combinatorial is not the right tool here. In fact, this problem can be readily solved with a closed-form solution using induction and recurrence. Before arriving at that, let's get some sense and inspiration by stating with a small N.
N = 1 is trivial and we see that k = 1 surely, so F = 1. Consider N = 2. During the first round of joining, when one free end is picked, it can be joined to any of the remaining 3 free ends. In one out of these three cases, we end up with k = 2 (namely, if the free end is joined to another end of itself); while in the remaining two cases, we end up with k = 1 (namely, if the free end is joined to any end of the other string). So $ F_2 = \frac 1 3 (1+F_1) + \frac 2 3 (F_1)=\frac 4 3 $. More generally, it's easy to show that $ F_N = \frac 1 {2N-1} (1+F_{N-1}) + \frac {2N-2} {2N-1} (F_{N-1})$
This recurring relation can be rearranged to give the difference equation $ F_N = F_{N-1} + \frac 1 {2N-1} $. With the initial condition of $ F_1 = 1$, we can alternatively express it as a finite sum. Note how slow it grows with N (~ log(N)).
