1

A group of 6 people consisting 3 married couples are to be seated together in a straight row. How many different ways are there of seating the 6 people if no husband is to sit next to another husband?

Since the husbands can't sit next to each other, I decided to place the wife in between the husband and arrange them.

H W H W H W

3! * 3! = 36.

Apparently, the answer is 144. Can anyone explain what went wrong?

XxS0ul678
  • 105
  • Could you specify what difficulties you are encountering with this problem? – N. F. Taussig Aug 17 '17 at 17:23
  • 1
    As you are relatively new to the site: people here tend to not respond well (or at all) to questions like this that look like routine homework problems and which show absolutely no effort. Please edit your post to show your work and to indicate where you are getting stuck. – lulu Aug 17 '17 at 17:42
  • @lulu Sorry, I find it very hard to explain what I was thinking. I hope this helps. – XxS0ul678 Aug 17 '17 at 17:50
  • 1
    note that 2 wives can sit next to each other. You have 4 times more configuration to take into account: HWHWHW, HWWHWH, HWHWWH and WHWHWH – fonfonx Aug 17 '17 at 17:51
  • @N.F.Taussig I added my workings to this post. You can check it out. – XxS0ul678 Aug 17 '17 at 17:51
  • @fonfonx Oh wow. But is there a better way to solve this qn instead of listing it out one by one? – XxS0ul678 Aug 17 '17 at 17:52
  • 1
    @XxS0ul678 yes, there is a general solution. First, seat the husbands. Next, seat the women inbetween the husbands in such a way that every gap between husbands has at least one woman in it. To accomplish this, first choose how many women go in each slot. This step can be counted via stars and bars. Of course, this is overkill for the problem as stated but will be useful for larger problems such as $5$ men and $20$ women. – JMoravitz Aug 17 '17 at 18:01

3 Answers3

1

The positions that can ocuppy the husbands are: $135, 136, 146, 246$

ajotatxe
  • 65,084
  • 1
    Grammar suggestion: "The positions the husbands can occupy are..." It is the husbands who are doing the occupying, not the positions. Alternatively "The positions that can be occupied by the husbands are..." – JMoravitz Aug 17 '17 at 18:04
1

With some work, show that there are four possible arrangements:

WHWHWH (and it's reflection)

HWHWWH (and it's reflection).

Can you finish the problem from here?

Alex R.
  • 32,771
1

Can anyone explain what went wrong?

The positions of the husbands and wives do not need to alternate since the wives may sit in adjacent seats. For instance, the seating arrangement $H_1W_1H_2W_2W_3H_3$ is permissible since no two of the husbands sit in adjacent seats.

A group of $6$ people consisting of $3$ married couples are to be seated together in a straight row. How many different ways are there of seating the $6$ people if no husband is to sit next to another husband?

Method 1: We arrange the wives, then insert the husbands among the wives.

Arrange the husbands in some order, say alphabetically, then hand each of them a chair.

Lay out three chairs for the wives. The wives can arrange themselves in those chairs in $3!$ ways. For each such arrangement arrangement, there are four spaces in which we can place the husbands, two between successive wives and two at the ends of the row. $$\square W_1 \square W_2 \square W_3 \square$$ To ensure that the husbands do not sit in adjacent positions, they must choose three of these four spaces. The first husband has four choices where to place his chair, the second has three, and the third has two. Hence, the number of permissible seating arrangements is $$3! \cdot 4 \cdot 3 \cdot 2 = 3!4!$$

Method 2: We use the Inclusion-Exclusion Principle.

The six people can be arranged in $6!$ ways. From these, we must exclude those arrangements in which two husbands sit in adjacent seats.

A pair of husbands sit in adjacent seats: There are $\binom{3}{2}$ ways to choose a pair of husbands who sit in adjacent seats. This gives us five objects to arrange, the block consisting of the pair of husbands and the other four people. The objects can be arranged in $5!$ orders. Within the block, the two husbands can be arranged in $2!$ orders. Hence, there are $$\binom{3}{2}5!2!$$ arrangements in which two husbands sit in adjacent seats.

However, $$6! - \binom{3}{2}5!2! = 0$$ Clearly, we have subtracted too much since the seating arrangement stated above shows it is possible to seat the three couples so that no two husbands sit in adjacent seats.

The reason we have subtracted too much is that we have subtracted those cases in which all three husbands sit together twice, once when we counted the leftmost and middle husband as our designated pair and once when we counted the rightmost and middle husband as our designated pair. We only want to subtract them once, so we need to add those cases to the total.

Two pairs of adjacent husbands: This can only occur if all three husbands sit in a block. This gives us four objects to arrange, the block of three husbands and the three wives. The four objects can be arranged in $4!$ ways. Within the block, the husbands can be arranged in $3!$ ways. Hence, there are $$4!3!$$ seating arrangements with two pairs of adjacent husbands.

Total: By the Inclusion-Exclusion Principle, the number of permissible seating arrangements is $$6! - \binom{3}{2}5!2! + 4!3!$$

N. F. Taussig
  • 76,571
  • May I know why is there a total of 7 space? Why is there 4 spaces in which to place the husbands? Wouldn't there be a total of 7 seats? 4 + 3 . – XxS0ul678 Aug 17 '17 at 18:31
  • Arranging the three wives creates four spaces in which we can place the husbands, two between adjacent wives and the two at the ends of the row. To ensure that the husbands are not adjacent, we must choose three of these four spaces for the husbands. This does not mean there are seven seats. We can arrange the husbands and wives, then seat them in a row of six chairs. – N. F. Taussig Aug 17 '17 at 18:40
  • I thought you are only arranging the three wives among themselves? For example, there are 3 spaces for the 3 wives. If you are arranging the wives, aren't you just swapping their position? – XxS0ul678 Aug 17 '17 at 18:48
  • This is what i am thinking in my mind w1 w2 w3 Since you are swapping it, wouldn't it be like w2 w3 w1 or w3 w1 w2. There are still 3 seats. – XxS0ul678 Aug 17 '17 at 18:49
  • First, we arrange the wives among themselves. Once we have placed them in a row, we can place the husbands in the four spaces indicated by the boxes. We choose three of those four spaces to separate the husbands, then arrange the husbands in the selected spaces. For instance, if we pick the first, second, and fourth spaces, we have an arrangement such as $H_1W_1H_2W_2W_3H_3$. – N. F. Taussig Aug 17 '17 at 18:50
  • I have rephrased the first solution and added a second solution. – N. F. Taussig Aug 18 '17 at 08:59