If there are $100$ people about to aboard an airplane and the first person has lost his ticket (which means he sits randomly), find the number of possible ways in which the people can sit if the rule is to sit in your own place if it's empty, otherwise sit randomly.
If the first person sits in the $j$ place, then all people from $2$ to $j-1$ will be in their original position. The problem now boils down to a '$101-j$'-person problem. So if for $n$ people, the answer is $f(n)$, we get the following recursion :
$f(n) = \sum \left(f(n+1-j) + 1\right)$ because $j$ will either go to the $1$st position or the problem boils down to the $101-j$ case as mentioned before.
Finally this can be solved using generating functions.
Is this correct? Or am I missing something?
Let $n$ be the total number of people.
$n=1$: $$1\Rightarrow f(1)=1$$
$n=2$: $$12, \color{red}{21}\Rightarrow f(2)=2=1+\color{red}{f(1)}$$
$n=3$: $$123,\color{red}{213,312},\color{blue}{321} \Rightarrow f(3)=4=1+\color{blue}{f(1)}+\color{red}{f(2)}$$
$n=4$: $$1234, \color{red}{2134,3124,4123,4132},\color{blue}{3214,4213},\color{green}{4231} \Rightarrow f(4)=8=1+\color{green}{f(1)}+\color{blue}{f(2)}+\color{red}{f(3)}$$
$n=5$: $$12345,\color{red}{21345,31245,41235,51234,51243,41325,51324,51342},\\ \color{blue}{32145,42135,52134,52143},\color{green}{42315,52314},\color{brown}{52341} \Rightarrow \\ f(5)=16=1+\color{brown}{f(1)}+\color{green}{f(2)}+\color{blue}{f(3)}+\color{red}{f(4)}$$ Do you see the pattern? Answer: