[Math] Number of ways in which $4$ people can be selected out of $10$ people sitting in a row such that exactly two are consecutive

combinationscombinatorics

Number of ways in which $4$ people can be selected out of $10$ people sitting in a row such that exactly two are consecutive is?

My attempt:

I tried two approaches:

  1. PIE: required ways = total ways – ways in which three are consecutive +
    ways in which four are consecutive. But I do not know how to calculate "ways in which three are consecutive", so I am stuck.

  2. Direct: the problem is that:

    • If I select two people at the ends: - - 3 4 5 6 7 8 9 10 or 1 2 3 4 5 6 7 8 - -, then I have six more ways to select the third person, but am unsure about the fourth way.
    • If I select two people in the middle, like so 1 2 3 - - 6 7 8 9 10, then selecting the next two people is troublesome, as the seats 1 and 2 cannot be occupied.

Both these approaches seem cumbersome. I hope there's a simpler way. What is that?

Best Answer

Method 1: Suppose we have four green balls, two of which are placed in a box, and six blue balls. Line up the six blue balls in a row. This creates seven spaces, five between successive blue balls and two at the ends of the row. Choose one of these seven spaces for the box with two green balls. Choose two of the remaining six spaces for the other two green balls. Now number the balls from left to right. The numbers on the green balls represent the positions of the selected people. Notice that exactly two of the green balls are consecutive, namely the ones in the box. Hence, there are $$\binom{7}{1}\binom{6}{2} = 105$$ ways to select four people from a row of $10$ people so that exactly two of the adjacent people are consecutive.

Observe that this is essentially your second method condensed into a single step. There are five ways to place the box with two green balls between two blue balls and two ways to place the box at an end of the row of six blue balls. This accounts for the factor of $7$. In each case, we are left with six spaces, two of which must be filled with the remaining green balls.

Method 2: In your first approach, you overlooked the possibilities that no two selected people are adjacent and that two separated disjoint pairs of adjacent people are selected. There are $\binom{10}{4}$ ways to select four of the ten people. From these, we must exclude the four cases below.

No two selected people are adjacent: We line up six blue balls in a row, creating seven spaces. We choose four of these seven spaces in which to place a green ball, then number the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{4}$ such cases.

Two separated disjoint pairs of adjacent people are selected: We line up six blue balls in a row, creating seven spaces. We choose two of the seven spaces in which to place two boxes, each of which contains two green balls, then numbers the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{2}$ such cases.

A block of three consecutive people and a fourth person not adjacent to them are selected: We line up six blue balls in a row, creating seven spaces. We choose one of the seven spaces for a box with three green balls and one of the remaining six spaces for the other green ball, then number the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{1}\binom{6}{1}$ such cases.

A block of four consecutive people is selected: We line up six blue balls in a row, creating seven spaces. We choose one of the seven spaces for a box with four green balls, then number the balls from left to right. The numbers on the green balls represent the positions of the selected people. There are $\binom{7}{1}$ such cases.

Thus, the number of permissible selections is $$\binom{10}{4} - \binom{7}{4} - \binom{7}{2} - \binom{7}{1}\binom{6}{1} - \binom{7}{1} = 105$$

Related Question