No two things are together (Gap method)

No two of a group of objects may be adjacent — the 'gap' method.

To permute $n$ distinct objects so that no two of a specified set of $k$ objects are ever adjacent, with the remaining $m=n-k$ objects unrestricted:

1. First arrange the $m$ unrestricted objects in a row: $^mP_m=m!$ ways.
2. This creates $m+1$ gaps — one before the first object, one between each consecutive pair, and one after the last (so $m-1$ internal gaps plus the 2 end gaps $=m+1$).
3. Place the $k$ restricted objects into these $m+1$ gaps, at most one per gap (so no two land in the same gap and hence never sit next to each other): $^{m+1}P_k$ ways.
4. By the rule of product, the total is $m!\times{}^{m+1}P_k.$ …