0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

You have one permutation cycle that starts with the first person, then the seat he sits in, then the seat that person sits in, and so on. Whenever somebody sits in seat 1, the cycle is closed and each person remaining will find their assigned seat available. The positions in the cycle must be increasing. If person 1 sits in seat 4, people 2 and 3 sit in their seats so person 4 must sit either in 1 and end the cycle or in some seat higher than 4. You get one permutation for each subset of the 99 people. Person 100 cannot participate because he sits in his own seat.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user362405 Apr 13 '17 at 2:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 13 '17 at 2:32
  • $\begingroup$ Thanks for the explanation,I have understood it better now. $\endgroup$ – user362405 Apr 13 '17 at 3:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.