# Number of arrangements possible

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?

– user840532
Nov 14, 2020 at 5:32
• Are the chairs arranged in a row? in a circle? Nov 14, 2020 at 9:35
• @N.F.Taussig chairs are arranged in a row. Nov 15, 2020 at 5:00

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.

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.

• sir, But it is not a round table. Nov 15, 2020 at 5:06
• Added some more details. Nov 15, 2020 at 6:20