Permutations of {1 .. n} where {1 .. k} are not adjacent The Problem:
So I was thinking up some simple combinatorics problems, and this one stumped me.

Let N be the set of numbers $\{1 .. n\}$, or any set of cardinality $n$
Let K be the set of numbers $\{1 .. k\}$ where $k < n$, or any subset of N of cardinality $k$
How many permutations of N exist such that no two members of set k are adjacent?


Here was my basic approach:

Solutions = Permutations of N - Permutations of N that contain a pair in K
Permutations of N = nPn = n!
Every item in K will occur in each permutation of N so we loop through: 
 You place down one item of K
 Possibilities where the next is in K = K - 1
 You place down an item of K 
 possibilities where next is in k = k-2
 ...
 You place the last item in K

The total permutations with a pair would therefore be:
$  (k-1) + (k-2) + ... + 0 $
However, many of those entries are duplicates, so we have to rule out instances where two of those pairs occurred in one set, and then again rule out instances that occurred three times, up pairs occurred k times
I think the amount with two pairs would best be found by getting the amount with one pair minus the amount with no more. 
To do this I would loop as:
You place two items in K
There are k-2 chances the next item is in k
You place an item in K
There are k-3 chances the next item is in k
...
You place your last item in K

Total permutations with two pairs $= (k - 2) + (k - 3) + ... + 0$
Total permutations with three pairs $= (k - 3) + (k - 4) + ... + 0$
And so on..
And at this point I know I am incorrect, because I would get a total of:
$( (k-1) + (k-2) + ... + 0 ) - ( (k-2) + (k-3) + ... + 0 ) - ( (k-3) + (k-4) + ... + 0 ) + ... + 0$ permutations that contain pairs. 
This number is waaay negative...

As I pointed out at the end of that, my solution finds a negative amount of permutations that have pairs in them, and so it is clearly wrong. If someone could explain my error, or else show a better way to approach the problem, I would greatly appreciate it.
Things that I think could be causing my answer to be wrong:


*

*I'm not sure if my generalization for removing the permutations with multiple pairs from the total amount of possible pairs works correctly if the pair does not occur as the first appearance of a member of set K

 A: 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.
A: 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.
