At a cafeteria, there are $10$ seats in a row, and $10$ people are lined up to walk into the cafeteria. The first person can sit anywhere, but any future person will only sit in a seat next to someone who is already sitting down. If the first person sits in the $5$th seat, how many total ways are there for the rest of the people to sit down?

  • 2
    $\begingroup$ Well, you know the order in which seats 1-4 will be filled, and likewise with 6-10, so how many ways are there to intersperse the two? Put another way, each person sitting down just needs to decide whether to sit to the right of the first person, or the left, assuming there's room. After that, their seat is determined. Four people can choose "left", and the other five will choose "right", so with nine people, how many ways can we choose four to go left? $\endgroup$ – Gabriel Burns Oct 18 '16 at 16:43

Since we have a restriction that the next person will only sit in a seat next to someone who is already sitting down and there's only one person seated initially then at any moment the persons already seated will be seated in a contiguous sequence of chairs.

Given this, we can think about the state at a given point to be defined by the chair closest to the left that have a person seated, L, and the chair closest to the right that also have a person seated, R, forming a pair (L,R).

We start with the state (5,5). From here we have two restrictions: L must be positive and R must be at most 10. So, if we see how the people seat sequentially and set a '0' if a person seats at the left and set a '1' if a person seats at the right, the resulting binary string must have size 9 and be composed with exactly 4 zeroes and 5 ones.

The number of such binary strings is: (9C4)=126.


WRONG APPROACH: There are always only two possible seats for each except last after first person. So for 9 (first being already seated at 5th seat) persons $2^8$. There will be only one seat left for the last one, so no choice for him.

EDIT: It can be solved using following formula $$ P(m, n)= \begin{cases} 1 + P(m - 1, n) + P(m, n - 1)& \text{if } m \neq 0\ \text{and}\ n \neq 0\\ 1 & \text{if } m = 0\ \text{or}\ n = 0\\ 0 & \text{if } m = n = 0\\ \end{cases} $$ where $m \text{ and } n\ are$ seats remaining to left and right after first person seated. Answer for m = 5, n = 4 is 251.

How to solve two variable recurrence relation: Solving recurrence relation in 2 variables

  • $\begingroup$ I don't see this. If the next four people sit in seats $4, 3, 2, 1$, then succeeding people only have one place to sit. Gabriel Burns's comment to the OP gives the proper approach. $\endgroup$ – Brian Tung Oct 18 '16 at 17:32
  • $\begingroup$ @BrianTung Ya. I missed that. $\endgroup$ – Majeed Siddiqui Oct 18 '16 at 17:56

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.