Permutations of {1 .. n} where {1 .. k} are not adjacent

Let's call the elements up to $k$ white and the others black, and consider elements of the same colour to be indistinguishable for now. For arrangements beginning with a white element, glue a black element to the left of all other white elements and choose $k-1$ slots among the resulting $n-k$ objects (excluding the initial white element) for the glued pairs. For arrangements beginning with a black element, glue a black element to the left of all white elements and choose $k$ slots among the resulting $n-k$ objects for the glued pairs. In total, that makes $\binom{n-k}{k-1}+\binom{n-k}k=\binom{n-k+1}k$ arrangements. Each corresponds to $k!$ permutations of the white elements and $(n-k)!$ permutations of the black elements, so the total number of permutations is

$$ \binom{n-k+1}kk!(n-k)!=\frac{(n-k+1)!k!(n-k)!}{(n-2k+1)!k!}=\frac{(n-k+1)!(n-k)!}{(n-2k+1)!}\;. $$

If $n-2k+1\lt0$, i.e. $k\gt\frac{n+1}2$, the binomial coefficient is zero and there are no such permutations.

An alternate explanation to @joriki's answer.

Let the $k$ elements $\{1,2,3,\dots,k\}$ be called "white" and the remaining $n-k$ elements be called "black."

First arrange the $n-k$ black elements in a row, leaving a bit of extra space to either side including to the left of the leftmost and to the right of the rightmost black element.

In these $n-k+1$ available spaces, choose $k$ of them to be occupied by white elements.

Arrange the white elements in a row and place them in the chosen locations.

There are then $\binom{n-k+1}{k}(n-k)!k!$ arrangements.

Note that when $k>n-k+1$, i.e. $k>\frac{n+1}{2}$ you will be forced to have two white elements adjacent and will have zero possible arrangments.