total number of ways 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?
 A: 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.
A: 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
