# Correct Combinatorial reasoning for constant positions

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:

$$A_i = i$$

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!

-
The trick seems to be that while the same permutations are counted more than once, they are counted exactly the # of fixed point placements - That is for example out of 4, the permutation, <1,2,4,3> may appear both when the first and second places are kept constant and therefore be counted as many times as necessary. – Guest 86 Feb 27 '13 at 0:39
@RossMillikan Thanks! I had a typo there. – CodeKingPlusPlus Feb 27 '13 at 0:41
If it's not too clear, what I meant is that I'm not sure what you mean by disjoint - You are in fact counting the same permutations more than once. But if you actually check the number of times you count them, it will match the amount of "fixed point" placements in them. – Guest 86 Feb 27 '13 at 0:43

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!.$$

-