Vtgyjfy

If $6$ people are standing up in queue for a picture, then in how many ways can they be re queued for the picture if no person has same right hand neighbor?

Why is $6!/2$ wrong?

(The answer is $309$.)

Edit: Based on @Phicar's suggestion in the comments, an attempt using the Inclusion-Exclusion Principle:

$$6!- 5.5! +4.4! -3 .3! + 2.2! - 1$$

Your count
$$frac{6!}{2}$$
is the number of arrangements in which a particular person is to the left of another person since by symmetry, she is to the left of that person in half the arrangements.

Let's follow @Phicar's advice and apply the Inclusion-Exclusion Principle.

There are $6!$ arrangements. From these, we must subtract those rearrangements in which one or more people has the same right neighbor.

In the original arrangement, there are five people who have right neighbors.

A person with a right neighbor keeps the same right neighbor: There are five ways to choose a person with a right neighbor who keeps the same right neighbor. If we treat the two of them as a unit, we have five objects to arrange, which can be done in $5!$ ways. Hence, there are $binom{5}{1}5!$ rearrangements in which a person keeps the same right neighbor, as you correctly calculated.

This gives us a running count of $6! - binom{5}{1}5!$, but we have subtracted too much.

Two people with a right neighbor each keep the same right neighbor as before: There are $binom{5}{2}$ ways to choose which two people with a right neighbor each keep the same right neighbor as before. There are two cases here, depending on whether the two selected people are adjacent, but they both result in the same number of objects to arrange.

If the two selected people are adjacent, then there are four objects to arrange, a block of three consecutive people who remain together and three individuals.

If the two selected people are not adjacent, then there are again four objects to arrange, two pairs of adjacent people and two individuals.

In both cases, there are $4!$ ways to arrange the four objects.

Hence, there are $binom{5}{2}4!$ rearrangements in which two people each retain the same right neighbor as before.

This gives us a running count of $6! - binom{5}{1}5! + binom{5}{2}4!$, but now we have added too much.

Three people with a right neighbor each keep the same right neighbor as before: There are $binom{5}{3}$ ways to select which people with a right neighbor each retain the same right neighbor as before. There are three cases here, depending on how many of the selected people are adjacent, but they all result in the same number of objects to arrange.

If the three selected people are adjacent, there are three objects to arrange, a block of four consecutive people and two individuals.

If exactly two of the three selected people are adjacent, there are three objects to arrange, a block of three consecutive people, a pair of adjacent people, and an individual.

If no two of the three selected people are adjacent, there are again three objects to arrange, three pairs of adjacent people.

In each case, there are $3!$ ways to arrange the three objects.

Hence, there are $binom{5}{3}3!$ rearrangements in which three people retain the same right neighbor.

This gives us a running count of $6! - binom{5}{1}5! + binom{5}{2}4! - binom{5}{3}3!$, but now we have subtracted too much.

Four people with a right neighbor each keep the same right neighbor as before: There are $binom{5}{4}$ ways to select which four people with a right neighbor who each keep the same right neighbor as before. There are three cases, depending on which person does not keep the same right neighbor as before, but they all result in the same number of objects to arrange.

If the first or next to last person is not selected, we have two objects to arrange, a block of five consecutive people and an individual.

If the second or fourth person is not selected, we have two objects to arrange, a block of four people and a pair of adjacent people.

If the third person is not selected, we have two objects to arrange, each consisting of a block of three consecutive people.

In each case, there are $2!$ ways to arrange the two objects.

Hence, there are $binom{5}{4}2!$ rearrangements in which four people each keep the same right neighbor as before.

This gives us a running count of $6! - binom{5}{1}5! + binom{5}{2}4! - binom{5}{3}3! + binom{5}{4}2!$, but we have added too much.

All five people with a right neighbor each keep that right neighbor: There is only one such rearrangement, namely the original arrangement.

Hence, by the Inclusion-Exclusion Principle, the number of rearrangements of the six people in which no person keeps the same right neighbor is
$$6! - binom{5}{1}5! + binom{5}{2}4! - binom{5}{3}3! + binom{5}{4}2! - binom{5}{5}1!$$