Probability of 2 permutations of slightly different sets meeting in k places. I have already posted a simplified problem of this (and received a comprehensive answer) hoping that it would lead me to solving this one, however, it does not seem to be the case.
We have got two sets $A=\{1,2,3,...,n-2\}\cup\{s\}$ and $B=\{1,2,3,...,n-2\}\cup\{t\}$. So that, each of the sets contains $n-1$ elements of which $n-1$ are the same. One element is different (in $A$ there is $s$ and in $B$ we have got $t$. Now we take random, uniform permutations of set $A$ and $B$. What is the probability that these two permutations meet in exactly $k$ places ($k\in\{0,...,n-2\}$)? [Meeting in $k$ places means that they have the same numbers in $k$ places.]
This problem is of a great importance in my current work, so I would be extremely happy if you can help me.
 A: Step 1. Assume that $s$ and $t$ are equal, and you have to compute the number of matches $m'(k)$ for permutations of identical sets with $n-1$ elements.  Also solve the same problem for permutations of identical sets with $n-2$ elements ($m"(k)$).
Step 2. Adjust for the situations where $s$ and $t$ are in the same position. Subtract the number of permutations $m"(k-1)$ (matches from two permutations of identical sets with $n-2$ elements) from the $m'(k)$ matches, BUT add it to $m'(k-1)$. Do this for $k$ from $1$ to $n-2$.
So the number of matches is:
$m(k)=m'(k)-m"(k-1)+m"(k)$  for  $k=1,n-2$
and
$m(0)=m'(0)+m"(0)$ (0 matches doesn't lose anything as obviously $s, t$ cannot be matched)
The probability is the number of different permutations corresponding to $k$ matches ($m(k)$ obtained as above) divided by the total number of permutations $((n-1)!)^2$. 
A: Let the first permutation be identity and let the number you are seeking be $N_{n,k}$ (I'll use $n$ instead of $n-2$ for simplicity of notation). Pick $k$ places where permutations agree - $\binom {n}k$ ways. If $t$ gets mapped to $s$, the rest should be a derangement of $n-k$ elements - $D_{n-k}=[e^{-1}(n-k)!]$ ways. If $t$ gets mapped to $a\ne s$ ($n-k$ ways), then the rest of the elements can be arranged in $N_{n-k-1,0}$ ways. Combining get
$$N_{n,k}=\binom n k\left(D_{n-k}+(n-k)N_{n-k-1,0}\right)$$
You are left to find
$$N_{n,0}=D_n+nN_{n-1,0}=\sum_{i=0}^{n}D_{n-i}\frac {n!}{(n-i)!}\approx n!+n!n/e.$$
