Count permutation pairs such that for each element, either permutation gives it a different position from its original position

45 Views Asked by At

How many permutation pairs $(\sigma,\tau)$ are there such that for every $1\leq i \leq n$, $\tau (i) \neq i \vee \sigma(i) \neq i$? For calrification, the permutations are over $[n]$.

What I know is that the amount of derangements over $[n]$ is $\Sigma_{j=0}^n \frac{(-1)^j n!}{j!}$, so that means the amount of pairs which allow for $\tau(i) \neq i \wedge \sigma(i) \neq i$ is the square of that sum. Yet, the condition in the question doesn't seem complementary to what I just described. So, can I proceed?

1

There are 1 best solutions below

0
On BEST ANSWER

You can use a similar method as the one calculating the number of derangements.

Let $S_k$ be the set of permutation pairs $(\sigma,\tau)$ such that $\sigma(k)=k\wedge \tau(k)=k$, then the number you want to count is $(n!)^2-|S_1\cup\cdots\cup S_n|$.

By the the inclusion–exclusion principle,

$$|S_1\cup\cdots\cup S_n|=\sum_{j=1}^n\binom{n}{j}(-1)^{j+1}((n-j)!)^2=n!\sum_{j=1}^n\frac{(-1)^{j+1}(n-j)!}{j!}.$$

So the result is

$$n!\sum_{j=0}^n\frac{(-1)^{j}(n-j)!}{j!}.$$