I solved the problem about 2 years ago and it was the Problem 1 of Final exam of EE of THU (see my previous solution here). That time I did not use symbolic method. Not sure why, a symbolic method just comes to my mind and here comes the blog.

The problem (restate in English)

N seats in a bus and N passengers come in order, passenger i holds a ticket for seat i. The first passenger will randomly pick up a seat to sit down because missing the ticket. Then all the rest of passengers either sit on his own seat if not occupied by others, otherwise, also randomly pick an empty seat to sit down. Question is what is the probability that the last passenger sits on the last seat (the seat matches the ticket)?

Solution using symbolic method

The first passenger will form a cycle that represents the disorder of the seats. All other passengers not in that cycle will sit on their own seats. And note, the cycle leading by passenger 1 is not really a cycle because the order is deterministic by the number. So for each length of this cycle, there is only one such element. Thus it is a SET in essence. For other parts are also SET because each single element maps to itself. Thus by symbolic method, this combinatorics are Two SETS production:

C = SET(\circ) SET(\circ) \implies C(z) = e^z e^z = e^{2z} = \sum_{n\ge 0} \frac{2^n}{n!}z^n

To compute a probability, we need to compute two numbers: numerator and denominator.

Denominator is the number of all possible ways (do not care about where the last passenger is on its own seat), that is two sets and with 1 in the first. This number is just (n-1)![z^{n-1}]C(z) = 2^{n-1} and we force 1 to the first set (this will not change numbers but just increase the size by 1).

Numerator is the number of all possible ways with the last passenger is on the second SET, it is just the number (n-2)![z^{n-2}]C(z) = 2^{n-2} (we force 1 \text{ and } N‘s position this just increases size by 2 and not change counting).

So probability is \frac{2^{n-2}}{2^{n-1}} = \frac{1}{2} .

References

• Analytic Combinatorics
• An Introduction to the Analysis of Algorithms