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.
How many permutations of {1,2,…,n}.
combinatoricsdiscrete mathematicspermutations
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...
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.
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