Correct Combinatorial reasoning for constant positions

Question

Suppose we have an array $A$ indexed from $1$ to $n$. Let a constant position be any index $i$ for $1 \leq i \leq n$ of the array such that:

\begin{equation} A_i = i \end{equation}

For example the array $\lbrack1,4,3,5, 2 \rbrack$ has the constant positions $1$ and $3$.

I want to the prove the number of constant positions over all permutations of $\lbrack n\rbrack$ is $n!$. Consider $n=3$ we have the following permutations:

\begin{align} &\lbrack 1, 2, 3\rbrack \implies 3 \text{ constant positions}\\ &\lbrack 1, 3, 2\rbrack \implies 1\text{ constant positions}\\ &\lbrack 2, 1, 3\rbrack \implies 1\text{ constant positions}\\ &\lbrack 2, 3, 1\rbrack \implies 0\text{ constant positions}\\ &\lbrack 3, 1, 2\rbrack \implies 0\text{ constant positions}\\ &\lbrack 3, 2, 1\rbrack \implies 1\text{ constant positions}\\ \end{align}

Thus, for $n=3$ we have $3!=6$ permutations.

Here is my proof:

We have $n$ disjoint cases:

Suppose there is a $1$ in position $1$ of the array $A$. Then there are $(n-1)!$ ways to rearrange the remaining elements. Suppose there is a $2$ in position $2$ of the array $A$. Then there are $(n-1)!$ ways to rearrange the remaining elements.

$\vdots$

Suppose there is an $n$ n in the $n^{th}$ position of the array $A$. Then there are $(n-1)!$ ways to rearrange the other elements.

Now, since each case is disjoint of every other case we can invoke the addition rule and therefore we have $n$ copies of $(n-1)!$:

\begin{align} =& n(n-1)! \\ =& n! \end{align}

1. Is my reasoning correct?
2. I think these cases are not necessarily disjoint in terms of the permutations that you can generate, but maybe in terms of what I am actually counting, perhaps they are.

All help is greatly appreciated!

Answer 1

Your proof is essentially correct, for the reasons given in the comments. Here's a somewhat more systematic approach which shows that the main trick to the problem is to change the order of summation in a double sum.

For a permutation $\sigma$ of $\{1,2,\dots,n\}$, let $\text{Fix}(\sigma) = \{ 1 \leq i \leq n : \sigma(i) = i \}$. You are asking to compute $$ \sum_{\sigma \in S_n} |\text{Fix}(\sigma)| = \sum_{\sigma \in S_n} \sum_{i \in \text{Fix}(\sigma)} 1. $$ But this is equal to $$ \sum_{i=1}^n \sum_{\sigma \in S_n : \sigma(i) = i} 1 = \sum_{i=1}^n (n-1)! = n \cdot (n-1)! = n!. $$