Let $k$ and $n$ be positive integers with $k \ge n$. Then I want to prove that we can find ${}_k\text{P}_n$ permutations of $(1, 2, ..., k)$ of length k such that no two permutations have n elements matching.
For example, if $k = 4$ and $n = 2$, we find ${}_4\text{P}_2 = 12$ permutations of $(1, 2, 3, 4)$ with the property:
$1234, 1342, 1423, 2143, 2314, 2431, 3124, 3241, 3412, 4132, 4213, 4321$
If we pick any two of these permutations, they will not have more than one number in the same spot in both permutations. The first two digits use each of the 12 permutations of two distinct elements from $\{1, 2, 3, 4\}$ exactly once, as do the last two digits, the first and last digit, etc.
I cannot find an explicit construction through induction or backwards induction (or anything else) nor can I find a graph theory proof of this.