In how many ways can a given process occur

Question

An auditorium has two rows of seats, with 50 seats in each row. 100 indistinguishable people sit in the seats one at a time, such that each person, except for the first person to sit in each row, must sit to the left or right of an occupied seat, and no two people can sit in the same seat. In how many ways can this process occur?

If the first person sits at one of the ends of the first row, then there is clearly just one possibility. But if the first person sits at position k in the first row, where positions increase from left to right, I'm not sure how many ways the remaining people can be arranged.

According to an online source, the answer to this question is ${100\choose 50}2^{98}$ and there are $2^{49}$ ways a single row can be filled, because each of the 49 people after the first in a row must sit to the left or right of the current group of people in the row. But I don't understand this, since if for example the first person sits in position 2, and the second in position 1, isn't there just one possibility for the remaining 48 people? It's possible I'm confused by the wording of the question.

Answer 1

There are $\binom{100}{50}$ ways to choose which $50$ people go in the first row. We just need to show that there are $2^{49}$ ways to place those $50$ people in the first row.

The key idea is to consider how many choices each person has when their seats are chosen in reverse order. That is, we choose the seat for the last person to sit down first, then the second-to-last person, and so on.

The last person to sit down must sit in either the leftmost seat, or the rightmost seat, so there are two choices.

Assuming the last person's seat has been chosen, the second-to-last person must sit in either the leftmost remaining seat, or the rightmost remaining seat. Again, there are two choices.

Continuing in this fashion, there are two choices for every person, except for the first person, who must take the only seat not occupied by the $49$ subsequent people. Therefore, there are $2^{49}$ ways these people can sit down.

Answer 2

For a direct argument for why there are $2^{49}$ ways to seat the first row people into that first row, break into cases based on the position of the first sitter in the row.

In the event the first sitter sat in the $k$'th seat, the remaining $49$ people designated to sit in the row must have $50-k$ of them sitting to the right and $k-1$ of them sitting to the left of the first sitter. This gives a total of:

$$\sum\limits_{k=1}^{50}\binom{49}{k-1}$$

This can be simplified by the binomial theorem and a slight change of variable, becoming $2^{49}$. The overall result then follows.