# Ways of filling seats

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, . . . , 100$, enters the hall after $(n-1)$-th person is seated. He sits 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 have seen this question before but I wanted to know if there is a solution that uses permutation cycles?

• Can you please help me out in finding the length of that permutation cycle that would give the answer.I came to know that it is $2^{n-2}$. But I could not find a proof for that. – user362405 Apr 13 '17 at 2:26
• There can be any length of cycle from $0$ to $99$. I would claim the number of seatings is $2^{98}$. If person 1 sits in seat 1 everybody sits right. If person 1 sits somewhere else, you can have any nonempty subset of people from 2 through 99 participate. – Ross Millikan Apr 13 '17 at 2:32