Htykuut

The numbers $1, 2, ldots, n$ are permuted. How many different permutations exist such that none of the numbers $1, 2, 3$ are adjacent when $n>4$?

Solution:
$4,5, ldots, n$ can be shuffled in $(n-3)!$ ways and $3!$ ways to arrange $1,2,3$. There are $n−2$ slots that are separated by $n−3$ shuffled numbers, and if we insert each of $1,2,3$ into a different slot, they cannot be adjacent. There are $binom{n - 2}{3}$ ways to do this.

Why is it $binom{n-2}{3}$ ways? I don't get the explanation.

Once you arrange $4,5,...,n$ in order, you have to put each of $1$, $2$ and $3$ either in a gap between two other numbers, or at one end of the list. But if you put one of them in a particular gap, or at a particular end, neither of the others can be put in the same place, or they would be adjacent in the final list.

Therefore you need to choose three different places to put $1,2,3$. There are $n-4$ gaps between the other numbers, and two additional places at the end, so $n-2$ places to choose from. The number of ways to choose $3$ things out of $n-2$ is $binom{n-2}3$.

You have $n-3$ numbers leaving $1,2,3$. Imagine you have a row of boxes, where each box denotes one of the $n-3$ numbers. You also have $n-2$ gaps: $n-4$ gaps between the boxes, and $1$ on each end.

$$_ b_1 _ b_2 _ ... _ b_{n-3} _$$

You have to permute the numbers in a manner such that $1,2,3$ are not adjacent to each other. This can be achieved if you select any $3$ distinct gaps out of the $n-2$ gaps to place one of $1,2,3$, since between any two gaps you have one or more boxes, or one or more numbers from the set ${4,5...,n}$, which ensures that $1,2,3$ are never adjacent to each other.

You can select $3$ gaps in $binom{n-2}3$ ways. The numbers in those gaps can permute in $3!$ ways and the remaining numbers can permute in $(n-3)!$ ways, giving you a total of $(n-3)!cdot3!cdotbinom{n-2}3$ ways.

There is a permutation of $1,2,3$ giving factor $3!$

There is a permutation of $4,5,dots n$ giving factor $(n-3)!$

The numbers $4,5,dots,n$ are "separated" (e.g. like $star7star5star4star6star$ if $n=7$) and $n-2$ slots/stars exists.

These stars must looked at as candidates for placing there exactly one of the numbers $1,2,3$.

So we must select $3$ of $n-2$ stars giving factor $binom{n-2}3$.

Then we end up with a total of: $$3!(n-3)!binom{n-2}3$$possibilities.

We can count the cases

• the permutations are n!

from which we need to eliminate the ways

• we can arrange $1,2,3$ adjacent that is: $3!(n-2)(n-3)!$


• we can arrange exactly a pair adjacent that is: $3!(n-3)![(n-3)(n-4)+2(n-3)]=3!(n-3)!(n-3)(n-2)$