2
$\begingroup$

I am a new student in stats and struggling with this question:

If 4 people are seated randomly in a row of 8 seats, what is the probability that no 2 persons will sit on adjacent seats?

4 people will take 4 seats and there will be 4 seats left. The 4 people can be arranged in 4! ways. And we can distribute 4 empty seats in the below 5 different spots. That is 5C4. So, I get 5! as answer. Is that right?

_P_P_P_P_

P:People in seats.

$\endgroup$
1
  • 3
    $\begingroup$ Pay attention to what the question is asking for. It specifically asked for a probability that no 2 persons sit next to eachother. $5!$ could not possibly be a probability since it is greater than one. $\endgroup$ – JMoravitz Oct 21 '17 at 14:48
7
$\begingroup$

There are only 2 ways when there is 1 empty seat between them

P_P_P_P_

or

_P_P_P_P

When there are 2 empty seats like P__P_P_P, we have 3 places to fit the 2 empty seats together(P__P_P_P,P_P__P_P and P_P_P__P)

Total ways to choose seats is 8C4

So probability is ${\frac{5}{8C4}}$

NOTE- 4! arrangement in both numerator and denominator will cancel out

$\endgroup$
6
  • 3
    $\begingroup$ You are missing several more cases such as P_ _P_P_P. You can have empty seats next to one another. $\endgroup$ – JMoravitz Oct 21 '17 at 14:47
  • $\begingroup$ @JMoravitz thanks. $\endgroup$ – Sagar Chand Oct 21 '17 at 14:51
  • $\begingroup$ @samjoe, what cases am I missing in total number of cases? $\endgroup$ – Sagar Chand Oct 21 '17 at 14:51
  • $\begingroup$ Well its correct now.. +1 :) $\endgroup$ – jonsno Oct 21 '17 at 14:55
  • 1
    $\begingroup$ @Gnudiff as I pointed out in my answer that there are 4! arrangement for 4 people. This would be same in denominator as well and thus would cancel out $\endgroup$ – Sagar Chand Oct 22 '17 at 5:15
5
$\begingroup$

A good first step is to count how many ways the people could sit themselves. There are indeed $4!$ ways that the people can arrange themselves in a line. Your reasoning for how many ways to choose how to distribute the empty seats however is incorrect though by chance happens to give the correct number. A more correct argument would be that you start the people in a line and put an empty seat inbetween each as such:

$$P\underline{*}P\underline{*}P\underline{*}P$$

We still have one extra empty seat left to place and five available positions for that seat of which we need to pick one:

$$\underline{~}P\underline{*}\underline{~}P\underline{*}\underline{~}P\underline{*}\underline{~}P\underline{~}$$

This gives a total of $4!\cdot 5$ ways in which they can arrange themselves with no two people sitting together.

As mentioned before, this is merely the first step to determining the probability. Now that we have the count of how many ways it can occur, we divide by the total number of ways that the four could seat themselves (reminding ourselves that each way they could sit is equally likely to occur which is what allows us to find probability in this fashion in the first place).

There are $\binom{8}{4}$ ways in which we choose which seats they occupy and $4!$ ways they arrange themselves within those seats giving the final probability as:

$$\frac{4!\cdot 5}{4!\cdot\binom{8}{4}}=\frac{5}{\binom{8}{4}}$$


More info as to why your method of counting was incorrect: Suppose instead there were twelve seats and four people. We would need eight empty seats then. By your logic we would have wanted to choose eight of the following five seats:

$\underline{~}P\underline{~}P\underline{~}P\underline{~}P\underline{~}$

But, that would lead to $\binom{5}{8}$ which is zero.

Instead in the situation with eight empty seats and four people out of twelve total seats, we would approach like I did above: distribute three of the empty seats to keep them separated: Then in the five available spaces distribute the remaining five seats remembering that you can put multiple seats into the same slot. Using stars-and-bars this would amount to $\binom{9}{4}$ possible arrangements of the empty seats.

$\endgroup$
3
$\begingroup$

To be found is the number of sums $r_1+r_2+r_3+r_4+r_5=4$ where $r_1,r_5$ are non-negative integers and $r_2,r_3,r_4$ are positive integers.

Think of e.g. $r_2$ as the number of open seats between the first and the second person in the line.

That comes to the same as finding the number of sums $s_1+s_2+s_3+s_4+s_5=1$ where the $s_i$ are non-negative integers.

It is immediately clear that thers are $5$ solutions for that. If it is not immediately clear then this can be found by means of stars and bars.

Since the students are distinghuisable we must multiply with $4!$

So there are $5\cdot4!$ possibilities.

This on a total of $8\times7\times6\times5=\frac{8!}{4!}$.

So the probabilitity is: $$\frac{5\cdot 4!4!}{8!}$$

$\endgroup$
3
$\begingroup$

Another way to solve this problem in general, with $n$ seats and $p$ people.

Consider that each person is taking a bag with him, to be placed to his right.
It can be easily figured that the number of ways to accomodate them is the same as that in which the places for the bags are cancelled and the remaining assigned to people without bag: $\binom{n-p}{p}$ ways to seat them.
To counter-check that we can also say that it is the number of ways to place the $n-2p$ vacant seats in the $p+1$ spaces at the side of those occupied, i.e. the weak compositions of $n-2p$ into $p+1$ parts.

But the last guy is allowed to place the bag in the corridor, if sitting at the extreme of the row, which is not a case included under the above. He is occupying then one fixed place, with the remaining seats to be occupied by $p-1$ people as before : so $\binom{n-1-(p-1)}{p-1}=\binom{n-p}{p-1}$ ways.

Thus $$\binom{n-p}{p}+\binom{n-p}{p-1}=\binom{n+1-p}{p}$$ total ways to seat them.

And for the probability, the above divided the number of ways to seat people without bags, i.e. $\binom{n}{p}$

The procedure can be easily extended to 2,3, .. bags.

In our case $$prob=\binom{8+1-4}{4}/\binom{8}{4}=5/\binom{8}{4}$$

$\endgroup$
1
$\begingroup$

This doesn't directly answer your question, but provides an nice alternative method to solving this question

This might not exactly be the general method for solving a question like this given in a statistics class, but it's an possibly fun way to solve the question (something people do in math competitions)

Calculation through recurrence relations

Let $C_i$ denote the number of ways $i$ people can be seated in $2i$ chairs such that no two are adjacent. Obviously for this question, we want to derive $$\frac{C_4}{\binom{8}{4}}$$

For $C_1$, there are two ways to seat one person in two chairs.

For $C_2$, you can reason that there is a total three ways.

For $C_3$, notice that if the third person is fixed/seated at the very end as so $$-...-P$$ Where $-$ represents an chair and $P$ is a person, we realize that the total number of ways for the other two people to be seated so that no two are adjacent is equal to $C_2$.

If the third person is fixed/seated second to the very end as so $$-...P-$$ Then it can be observed that this determines the seats of all the other people (try proving this yourself), thus giving us one combination for that seating for the third person.

So in conclusion, we see that $C_3=C_2+1$

In fact we can easily generalize this to $C_n=C_{n-1}+1$ by taking a more general case if you like.

But back to the question, for $C_4$, we know it is equal to $C_3+1$, which in turn is equal to $C_2+1+1=5$.

Knowing that, we can conclude that the answer to your question would be $$\frac {5}{\binom{8}{4}} = \frac {5}{70} = \frac {1}{14}$$

$\endgroup$
3
  • $\begingroup$ If you're going to be using nCr notation for binomial coefficients, then you might consider using a different letter to denote values from your recurrence relation. That, or you could move to the more standard and widely used \binom{n}{r} $\binom{n}{r}$ notation. $\endgroup$ – JMoravitz Oct 21 '17 at 15:15
  • $\begingroup$ Thanks, that makes a lot more sense. $\endgroup$ – Stone Oct 21 '17 at 15:16
  • $\begingroup$ Certainly $\frac{5}{\binom{8}{4}} = \frac{5}{70} = \frac{1}{14}$. $\endgroup$ – Jeppe Stig Nielsen Oct 21 '17 at 20:22
0
$\begingroup$

Since probability has been asked for, we can simplify by taking people to be indistinguishable.

Denoting vacant seats by $V$ and permissible seats for people by asterisks, $\;* V * V * V * V *$

people can be placed in $\binom54$ ways against $\binom84$ unrestricted ways, so $Pr = \dfrac5{70}= \dfrac1{14}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.