How many derangements on a set $[n]$ does there exist such that $\sigma(n)\ne n-1$ and $\sigma(n-1)\ne n-2$

119 Views Asked by At

How many derangements on a set $[n]$ does there exist such that $\sigma(n)\ne n-1$ and $\sigma(n-1)\ne n-2$.

Let $\mathbb A$ be the set of all derangements such that $\sigma(n)= n-1$ and $\mathbb B$ be the set of all derangements such that $\sigma(n-1)= n-2$.

Define $$A_{m,i}:=\left\{\sigma \in S_n:\sigma(k)\ne k \;\;\;\text{for all}\;\; k \in[n] \;\;\;\text{and}\;\; \sigma(n)= m,\sigma(n-1)=i \right\}$$

Then $$\left|A_{1,1}\right|=\left|A_{1,2}\right|=...=\left|A_{1,n-2}\right|=\left|A_{1,n}\right|=...=\left|A_{n-1,1}\right|=\left|A_{n-1,n-2}\right|=\left|A_{n-1,n}\right|$$

On the other hand :

$$!n=\left|A_{1,1}\right|+\left|A_{1,2}\right|+...+\left|A_{1,n-2}\right|+\left|A_{1,n}\right|+...+\left|A_{n-1,1}\right|+\left|A_{n-1,n-2}\right|+\left|A_{n-1,n}\right|$$ $$\iff$$ $$\underbrace{\sum_{i=1}^{n-2}\left|A_{n-1,i}\right|+\left|A_{n-1,n}\right|}_{\mathbb A}+\underbrace{\sum_{m=1}^{n-1}\left|A_{m,n-2}\right|}_{\mathbb B}+\sum_{m=1}^{n-2}\sum_{i=1}^{n-3}\left|A_{m,i}\right|+\sum_{m=1}^{n-2}\left|A_{m,n}\right|=!n$$

Which implies $A_{m,i}=\frac{!n}{\left(n-1\right)^{2}}$

So the answer is:

$$n!-[\mathbb A+\mathbb B-\mathbb A\cap\mathbb B]$$

$$=!n-\left[!n-\sum_{m=1}^{n-2}\sum_{i=1}^{n-3}\left|A_{m,i}\right|-\sum_{m=1}^{n-2}\left|A_{m,n}\right|-\left|A_{n-1,n-2}\right|\right]$$

$$=\frac{!n}{\left(n-1\right)^{2}}\left(n-3\right)\left(n-2\right)+\frac{!n}{\left(n-1\right)^{2}}\left(n-2\right)+\frac{!n}{\left(n-1\right)^{2}}$$$$=\frac{!n}{\left(n-1\right)^{2}}\left(\left(n-2\right)^{2}+1\right)$$

However the answer is not true, after some calculation by hand I figured out that in general the sets $A_{m,i}$ are not equal,what is the answer to this question?

1

There are 1 best solutions below

7
On BEST ANSWER

The big problem here is that you seem to be counting permutations, not derangements: the sum of the $|A_{m,i}|$ should not be $n!$.

Let $D$ be the set of derangements of $[n]$, and let $B_n=\{\sigma\in D:\sigma(n)=n-1\}$ and $B_{n-1}=\{\sigma\in D:\sigma(n-1)=n-2\}$. Clearly we want

$$|D\setminus(B_n\cup B_{n-1})|=|D|-(|B_n|+|B_{n-1}|)-|B_n\cap B_{n-1}|\;.$$

I will write $d_n$ for the number of derangements of $[n]$. For each $k\in[n-1]$ there are $\frac{d_n}{n-1}$ derangements $\sigma$ of $[n]$ such that $\sigma(n)=n-1$ and the same number that send $n-1$ to $n-2$, so $|B_n|=|B_{n-1}|=\frac{d_n}{n-1}$. You also miscounted the sets $A_{m,i}$: there are $(n-1)^2+1$ of them, not $(n-1)^2$.

Now suppose that $\sigma\in B_n\cap B_{n-1}$. There are two possibilities: $\sigma(n-2)=n$, and $\sigma(n-2)\ne n$.

  • If $\sigma(n-2)=n$, $\sigma\upharpoonright[n-3]$ is a derangement of $[n-3]$, and there are $d_{n-3}$ of those.
  • If $\sigma(n-2)\ne n$, $\sigma$ is one of the bijections from $[n-2]$ to $[n-3]\cup\{n\}$ such that $\sigma(k)\ne k$ for $k\in[n-3]$, and $\sigma(n-2)\ne n$. There is exactly one excluded value for each $k\in[n-2]$, exactly as if we were counting derangements of $[n-2]$, so there are $d_{n-2}$ such bijections.

Thus, $|B_n\cap B_{n-1}|=d_{n-2}+d_{n-3}$. The derangement numbers satisfy the recurrence $d_n=(n-1)(d_{n-1}+d_{n-2})$, so $|B_n\cap B_{n-1}|=\frac{d_{n-1}}{n-2}$. Thus,

$$|D\setminus(B_n\cup B_{n-1})|=d_n-\frac{2d_n}{n-1}+\frac{d_{n-1}}{n-2}=\frac{(n-3)d_n}{n-1}+\frac{d_{n-1}}{n-2}\;.$$

For example, for $n=4$ we get $\frac{d_4}3+\frac{d_3}2=\frac93+\frac22=4$, which is correct: the four derangements in question are $3142$, $3412$, $4312$, and $2341$.

The expression $\frac{(n-3)d_n}{n-1}+\frac{d_{n-1}}{n-2}$ can be rewritten in a variety of ways, e.g.,

$$\begin{align*}\frac{(n-3)d_n}{n-1}+\frac{d_{n-1}}{n-2}&=\frac{(n-3)n!}{n-1}\sum_{k=0}^n\frac{(-1)^k}{k!}+\frac{(n-1)!}{n-2}\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}\\ &=(n-1)!\left(\frac{n(n-3)}{n-1}\sum_{k=0}^n\frac{(-1)^k}{k!}+\frac1{n-2}\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}\right)\\ &=(n-1)!\left(\frac{(-1)^n(n-3)}{(n-1)(n-1)!}+\frac{n^3-5n^2+7n-1}{(n-1)(n-2)}\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}\right)\\ &=\frac{(-1)^n(n-3)}{n-1}+(n^3-5n^2+7n-1)(n-3)!\sum_{k=0}^{n-1}\frac{(-1)^k}{k!}\;, \end{align*}$$

but I don’t at the moment see any very nice way. In practice one can make use of the fact that $d_n=\left\lfloor\frac{n!}e+\frac12\right\rfloor$.