3
$\begingroup$

Book: Probability For Dummies®, 2006, Rumsey, Deborah, PhD, Published by, Wiley Publishing, Inc., page 82 -- Extract from Google Books

Problem: "Suppose you have four friends named Jim, Arun, Soma, and Eric. How many ways can you rearrange the individuals in a row so that Soma and Eric don't sit next to each other?"

Question: How can I generalize a way to find the answer? In other words, I understand why 4! is involved, but how do I generalize finding 6 from (24-6)=18 to, for example, 7 seats and 3 people can't sit next to each other?

Update: If k is number of spots (4), p is # of people that can't sit together (2), and x is the # of locations in k where p can begin (3), then is this true? Answer = $k!-(x \times p!)$ I've attached an image, which I hope is correct.

enter image description here

| cite | improve this question | | | | |
$\endgroup$
  • 2
    $\begingroup$ The idea is to treat Soma and Eric as one unit, then apply the normal formulae. $\endgroup$ – Parcly Taxel Mar 24 '17 at 16:18
  • $\begingroup$ How do you mean to generalize? $\endgroup$ – kingW3 Mar 24 '17 at 16:20
  • $\begingroup$ kingW3, I just added the following text to the question: "how do I generalize finding 6 from (24-6)=18 to, for example, 7 seats and 3 people can't sit next to each other?" $\endgroup$ – mellow-yellow Mar 24 '17 at 16:40
3
$\begingroup$

"Suppose you have four friends named Jim, Arun, Soma, and Eric. How many ways can you rearrange the individuals in a row so that Soma and Eric don't sit next to each other?"

Your answer of $18$ is incorrect.

Method 1: Subtract the number of seating arrangements in which Soma and Eric sit next to each other from the total number of seating arrangements.

There are four positions to fill with four different people, so they can be arranged in a row in $4!$ orders, as you realized.

Now we count arrangements in which Soma and Eric sit together. We treat them as a unit, which means we have three objects to arrange, Jim, Arun, and the unit consisting of Soma and Eric. We can arrange these three objects in a row in $3!$ ways. However, the unit consisting of Soma and Eric can be arranged internally in $2!$ ways. Hence, the number of seating arrangements in which Soma and Eric sit together is $3!2!$.

Thus, the number of seating arrangements in which Soma and Eric do not sit together is $$4! - 3!2! = 24 - 6 \cdot 2 = 24 - 12 = 12$$

Method 2: We arrange Jim and Arun, then insert Soma and Eric so that they do not sit in adjacent seats.

Jim and Arun can be arranged in $2!$ ways. In each case, we have three spaces in which to place Soma and Eric, indicated by the empty squares below.

$$\square \text{Jim} \square \text{Arun} \square$$

or

$$\square \text{Arun} \square \text{Jim} \square$$

To ensure Soma and Eric do not sit together, we must choose two of the three spaces in which to place them. We can then arrange Soma and Eric within these chosen spaces in $2!$ ways. Hence, there are $$2! \cdot \binom{3}{2} \cdot 2! = 2! \cdot \frac{3!}{2!1!} \cdot 2! = 2! \cdot 3! = 2 \cdot 6 = 12$$ permissible seating arrangements.

In how many ways can seven people be seated if a particular group of three people cannot be seated next to each other?

We use the second method.

Rather than naming the people, we will use colored balls as placeholders. Arrange four blue balls in a row. This creates five spaces in which to insert three green balls, as indicated by the positions of the squares below.

$$\square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square$$

To ensure that no two of the green balls are adjacent, we choose three of the five spaces in which to place the green balls, which we can do in $\binom{5}{3}$ ways. Now number the balls from left to right. The positions occupied by the green balls are the seating positions of the people who are not to sit in adjacent seats. For instance, if we place green balls in the positions by the first, third, and fourth squares, the people who are not to sit next to each other will occupy the first, fourth, and sixth seats in the row. $$\color{green}{\bullet} \color{blue}{\bullet} \color{blue}{\bullet} \color{green}{\bullet} \color{blue}{\bullet} \color{green}{\bullet} \color{blue}{\bullet}$$ The other four people can be arranged in the positions occupied by the blue balls in $4!$ ways. The people who are not to sit next to each other can be arranged in the three positions occupied by the green balls in $3!$ ways. Thus, the number of permissible seating arrangements is $$\binom{5}{3}4!3! = 10 \cdot 24 \cdot 6 = 1440$$

How can we generalize this to $n$ people if a particular group of $m$ people do not sit next to each other?

We place $n - m$ blue balls in a row. This creates $n - m + 1$ spaces in which to place green balls ($n - m - 1$ between successive blue balls and two at the ends of the row). To ensure that no two people from the group of $m$ people sit in adjacent seats, we must choose $m$ of these $n - m + 1$ spaces in which to insert a green ball, which we can do in $\binom{n - m + 1}{m}$ ways. We then number the balls from left to right. Again, the numbers on the green balls represent the positions of the people who do not sit next to each other. The $n - m$ people who sit in seats whose numbers appear on a blue ball can be arranged in those seats in $(n - m)!$ ways. The $m$ people who sit in seats whose numbers appear on a green ball can be arranged in those seats in $m!$ ways. Hence, the number of permissible seating arrangements is $$\binom{n - m + 1}{m}(n - m)!m! = \frac{(n - m + 1)!}{(n - 2m + 1)!m!} \cdot (n - m)!m! = \frac{(n - m + 1)!(n - m)!}{(n - 2m + 1)!}$$ You can verify that this formula is correct by setting $n = 4$ and $m = 2$ in the first problem and $n = 7$ and $m = 3$ in the second problem.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Because you wrote, "Your answer of 18 is incorrect" and the book's author wrote the answer, the author's answer is incorrect. Thank you for this level of detail! $\endgroup$ – mellow-yellow Mar 24 '17 at 19:23
2
$\begingroup$

Hint -

One easy method to do these type of problems is = Total ways - Number of ways Soma and Eric sit together.

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

I will try to put a generalization formula here. Please correct me if I am wrong:

Lets say we have $n$ people in a line, where $m$ certain people are not next to each other. (Assume $n \gt m$)

This can be solved using the complement.

$n! - m!(n-m+1)!$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Something seems off with my answer now that I'm looking at it. I just don't know what $\endgroup$ – WaveX Mar 24 '17 at 16:55
  • $\begingroup$ Nevermind my answer follow the one supplied by N. F. Taussig $\endgroup$ – WaveX Mar 24 '17 at 17:54

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.