How many permutations of {1,2,…,n}.

combinatoricsdiscrete mathematicspermutations

How many permutations of {1,2,…,n} where n >=5 are there such that none of {1,2,3} are adjacent to one another?

Example: the permutation (5,3,1,4,2) does not meet the condition described in the problem because 1 and 3 are in two adjacent places and the permutation (2,5,3,4,1) as well as (1,6,2,5,3,4) meets this condition.

Best Answer

Moving comment to answer:

First arrange the numbers $4,5,6,\dots,n$.

Next, pick a "hole" between those or to either side to place the $1$. Then pick a different hole to place the $2$, etc...

$(n-3)!\cdot (n-2)(n-3)(n-4)$

In general, the number of permutations of $1,2,3,\dots,k,\dots,n$ where none of $1,2,\dots,k$ are adjacent, the same approach works.

$(n-k)!\cdot \frac{(n-k+1)!}{(n-2k+1)!}$

or better yet, using $a\frac{b}{~}$ to denote the falling factorial $a\frac{b}{~}=\underbrace{a(a-1)(a-2)\cdots(a-b+1)}_{b~\text{terms}} = \frac{a!}{(a-b)!}$ this would be

$(n-k)!\cdot (n-k+1)\frac{k}{~}$

Related Question