2

Let $[n]$ be a set with $n$ elements,How many permutations $\sigma$ of this set exist such that: $$\forall i\in [n]:\sigma (i) \ne i \;\;\;\;\text{and}\;\;\;\; \sigma (n) \ne n-1$$

I tried several times ,for example one of the strategies I used was:

Since $\sigma (n) \ne n$ and $\sigma (n) \ne n-1$ , so $\sigma (n) = i$ where $1\le i\le n-2$, so there are $n-2$ choices,now we are left with the $n-1$ remaining elements for which $\sigma$ does not have any fixed point, so the answer is $!\left(n-1\right)\left(n-2\right)$.

Then I figured out that the formula is wrong,since for the $n-1$ remaining elements ,there are two of them for which their fixed point is the same,namely $n-1$ and $n$,because $\sigma (n-1) \ne n-1$ by derangement and $\sigma (n) \ne n-1$ by the assumption,and we use derangement formula when there does not exist two distinct elements in $[n]$ with the same fixed point.

So what is the answer?

  • 4
    Out of the derangements, what proportion of them send $n$ to $n-1?$ – Ragib Zaman May 11 '20 at 08:19
  • @ RagibZaman,what do you mean? –  May 11 '20 at 08:44
  • There are !n derangements of [n]. What fraction of these would map n to n-1? – Ragib Zaman May 11 '20 at 08:46
  • 1
    Is a derangement more likely to send $n$ to $n-1$ than it is to send $n$ to $1$? To $2$? – saulspatz May 11 '20 at 08:46
  • @saulspatz,well the second one –  May 11 '20 at 08:47
  • I don't understand what you mean. Which is the second one? – saulspatz May 11 '20 at 08:48
  • A derangement is less likely to send n to n−1 than it is to send n to 1, To 2 –  May 11 '20 at 08:55
  • No – the point of those remarks was that by symmetry the derangement is equally likely to send $n$ to any of the other $n-1$ numbers; so a proportion $\frac1{n-1}$ of the derangements sends $n$ to each of them. – joriki May 11 '20 at 09:14
  • The number of derangements $\sigma$ on $[n]$ with $\sigma(n)=i$ is the same for all $i=1,\cdots,n-1$. This is easily seen by noting that we can always relabel the elements of $[n]$. – Sangchul Lee May 11 '20 at 09:14
  • 3
    Let $$A_k={\sigma\in S_n:\sigma(i)\neq i\text{ for all }i\in[n]\text{ and }\sigma(n)=k}.$$ Then the above discussions show that (1) $|A_1|=|A_2|=\cdots=|A_{n-1}|$ and (2) $|A_1|+\cdots+|A_{n-1}|=!n$ is the number of derangements on $[n]$. So we have $$|A_k|=\frac{!n}{n-1}$$ for any $k=1,\cdots,n-1$, and then the desired answer to OP is $$|A_1|+\cdots+|A_{n-2}|=\frac{n-2}{n-1}(!n).$$ – Sangchul Lee May 11 '20 at 09:28
  • 1
    @ SangchulLee,very nice, thank you –  May 11 '20 at 11:10

0 Answers0