Number of arrangements possible

Question

There are $m$ persons and $n$ chairs. Each person needs to maintain social distance between themselves and the person they are sitting next to. Therefore, once a person sits, the person who sits next to them sits at a distance that is in multiples of the integer $k$. We have to find the total number of arrangements possible so that all the people can be seated.

Notes:

1.All the people must get a chair to sit on

2.Two arrangements are different either if the state of a chair is different in both cases or if two different people are seated on it. For example, for chairs $n=10$, person $m=2$, and $k=2$, if the first person sits at the 2nd position, then the second person can sit only at the 4th, 6th, 8th, or 10th position.

For example, $n=5,m=2,k=2$ no of arrangements possible are 4. (1,3) (1,5) (2,4) (3,5).

Can anyone suggest some approach to me for this combinatorics problem?

Answer 1

Here is how you might go about solving this problem.

1. One way to do this is to handle the $k$ condition first. For example, when $k = 2$, either all the occupied chairs have even number or odd number. So in general, we can consider $k$ different kinds of seating arrangements: one which has chair numbers $\equiv 1 \mod k$, one with $2 \mod k$, and so on until $0 \mod k$. If $n$ is a multiple of $k$, all of these will be equally large. If not, they will roughly have the same size but be slightly different.

2. Once we've handled the $k$ condition, this is just a problem about placing $m$ people in either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$ chairs. This is a standard counting problem.

Answer 2

OK as per your clarification, people are seated in a row. Based on your question and your example, the next person can sit on the k$th$ chair i.e there are at least $(k-1)$ chairs between any two neighbors on the table.

There are $(m-1)$ places between people so the first condition is $n \geq (m-1) (k-1) + m$.

Now to solve this, here is an approach: we have $m!$ ways to sit $m$ people in a row. The next step is equivalent of finding ways to place remaining $(n - m)$ chairs between $m$ people or at two ends such that there are at least $k-1$ chairs between any two neighbors. This can be found using stars and bars method. Place $(k-1)$ chairs each in $(m-1)$ places between people first (there is only one way to do that) and then the rest $(n - mk + k - 1)$ chairs in $(m + 1)$ places. $[(m - 1$ places between them plus two at the ends$]$.

So altogether it comes to $m! \times {n+m+k-mk-1 \choose m}$ arrangements.