Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.