Let me copy here my answer from Russian forum dxdy.ru, which is based on the approach outlined in my paper.
Two given rows of a $3\times N$ matrix define a permutation of order $N$. Let $c_i$ ($i=1,2,\dots,N$) be the number of cycles of length $i$ in this permutation (in particular, $c_1$ is the number of fixed points).
Then the number of different third rows that form derangements (i.e. fixed-point-free permutations) with respect to each of the first two rows equals $$\sum_{j=0}^n (-1)^j\cdot (n-j)!\cdot [z^j]\ F(z),$$ where $[z^j]$ is the operator of taking the coefficient of $z^j$ and $$F(z) = (1+z)^{c_1}\cdot \prod_{i=2}^n \left( \left(\frac{1+\sqrt{1+4z}}2\right)^{2i} + \left(\frac{1-\sqrt{1+4z}}2\right)^{2i} \right)^{c_i}.$$
Particular cases:
- For $c_1=n$ (i.e., two given rows are equal), we get just the number derangements.
- For $c_n=1$, we get menage numbers A000179(n).
- For $n=2m$ and $c_2=m$, we get A000316(m) = A000459(m)$\cdot 2^m$.
This question inspired me to add the following new sequences to the OEIS: A277256, A277257, and A277265.