MathDB

There are

n

passengers in a line, waiting to board a plane with

n

seats. For

1 \le k \le n

, the

k^{th}

passenger in line has a ticket for the

k^{th}

seat. However, the rst passenger ignores his ticket, and decides to sit in a seat at random. Thereafter, each passenger sits as follows: If his/her assigned is empty, then he/she sits in it. Otherwise, he/she sits in an empty seat at random. How many different ways can all

n

passengers be seated?

Problem Statement