0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Can anyone please reply? $\endgroup$ Nov 14, 2020 at 4:55
  • $\begingroup$ please reply anyone $\endgroup$ Nov 14, 2020 at 5:12
  • 2
    $\begingroup$ please don't include so many 'please answer' or 'please reply' in the comments. If you do this very much, it is considered spamming. $\endgroup$
    – user840532
    Nov 14, 2020 at 5:32
  • $\begingroup$ Are the chairs arranged in a row? in a circle? $\endgroup$ Nov 14, 2020 at 9:35
  • $\begingroup$ @N.F.Taussig chairs are arranged in a row. $\endgroup$ Nov 15, 2020 at 5:00

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ sir, But it is not a round table. $\endgroup$ Nov 15, 2020 at 5:06
  • $\begingroup$ Added some more details. $\endgroup$
    – Math Lover
    Nov 15, 2020 at 6:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .