There are 100 people in a queue waiting to enter a hall. The hall has exactly 100 seats numbered from 1 to 100. The first person in the queue... There are $100$ people in a queue waiting to enter a hall. The hall has exactly $100$ seats numbered from $1$ to $100$. The first person in the queue enters the hall, chooses any seat and sits there. The $n$-th person in the queue where $n$ can be $2,\ldots,100$, enters the hall after $(n-1)$-th person is seated. He sists in seat number $n$ if he finds it vacant; otherwise he takes any unoccupied seat. Find the total number of ways in which $100$ seats can be filled up, provided the $100$-th person occupies seat number $100$.  
I could not realise how this chaotic behaviour will end. I think the solution lies in finding that. Please help.
 A: Let $s_r$ be the number of the seat taken by the $r^{th}$ person.
Suppose $s_1=k_1$, then person $k_1$ is the first to find their seat already filled. Either person $k_1$ takes seat $1$, when the remainder of the passengers take their own seat, or $s_{k_1}=k_2\gt k_1$. Person $k_2$ is the second person to find their seat occupied (repeat the argument).
So you need to count the number of increasing sequences $2\leq k_1\lt \dots \lt k_r\le 99$ where $k_r$ indexes the people who find their seat occupied and have to occupy a seat other than their own.

 To compute the count note that any number between $2$ and $99$ inclusive can either be in the sequence or out of it. So that comes to $2^{98}$.

The normal question about this situation is to find the probability that the $100^{th}$ person sits in their own seat. If this is part of your method for solving that, it is not the easiest way of getting an answer.
A: Note Mark's comment: This counts the number of ways without the final condition that person 100 sits in seat 100. The correct answer is $2^{98}$; assign seat 100 to person 100 first, then proceed as I describe below. When you get to seat $99$, there will be 1, not 2 possibilities.
I might be missing something, but I think the following argument shows that there are $2^{99}$ ways to do this.
First, note that where $k>1$, seat $k$ must be occupied by one of the first $k$ people. Now enumerate the seat assignment possibilities by going through the seats from seat $2$ to seat $100$ first. (All we need to do here is count the number of arrangements, so as long as we find them all, it doesn't matter if we generate them by a different process than the one in the problem.) There are two ways to fill seat $2$ (person $1$ or person $2$). No matter who fills seat $2$, there are then $2$ ways to fill seat $3$, since it must be filled by one of the first three people not in seat $2$. And so on, so there are $2^{99}$ ways to fill seats $2$ through $100$. The remaining person sits in seat $1$, so there is only one choice for the final seat assignment.
A: I think I have a sketch, but I haven't worked out all the details, and so I am not 100% sure. Some hints below.
Hint:


*

*For your decision it's not important who took your seat, only that it is taken and how many are left.

*In turn $k$ seats $2,3,\ldots (k-1)$ are taken (by whoever sits there).

*The additional taken seat is random.

*If the 100th person occupies seat number 100, then nobody ever had picked this place. In other words this seat could have been nonexistent at all.


I hope this helps $\ddot\smile$
A: Let $T_n$ be the number of ways that $n$ seats can be filled by this process (ignoring the restriction on the final person's seat for the moment).  The first person sits in seat $j$, with $1\le j \le n$.  The next $j-1$ people sit in seats $1,2,3,\ldots, j-1$.  The remaining $n-j$ people are faced with the initial situation, with $n-j$ seats left to fill, and the next person free to choose their seat.  So $T_n=\sum_{j=1}^{n}T_{n-j}=\sum_{j=0}^{n-1}T_j$, with the initial condition $T_0=1$.  This leads immediately to the solution $T_n=2^{n-1}$ for $n\ge 1$.
To enforce the additional constraint that the $n$-th person must sit in seat $n$, we simply eliminate seat $n$ from all earlier choices... the first $n-1$ people can then be seated in $T_{n-1}=2^{n-2}$ ways, after which the final person takes their reserved seat.  With $n=100$, this gives the final result as $2^{98}$.
A: The correct answer is 99!
Check it out for 4 people. 
This is an application of funtions. i.e No.  of one-one functions when co-domain(No. of seats)  and domain(passengers)  are equal. 
