# Thread: Permutation and fix points

1. ## Permutation and fix points

A Challenge Problem:
Let $\displaystyle S_n$ be all the permutations of {1,2,...,n}.
for any given permutation $\displaystyle \sigma$, if $\displaystyle \sigma(i)=i$, we say $\displaystyle i$ is a fix point of $\displaystyle \sigma$.
A permutation may have several fix points, let $\displaystyle FP(\sigma)$ be the set of fix points of the permutation $\displaystyle \sigma$.

Problem: How many permutations are there whose fix-points set has exactly k elements(points)? k=0,1,...,n.

2. Drexel28, This is a new problem derived from another thread.
So, enjoy this problem!

3. Originally Posted by Shanks
A Challenge Problem:
Let $\displaystyle S_n$ be all the permutations of {1,2,...,n}.
for any given permutation $\displaystyle \sigma$, if $\displaystyle \sigma(i)=i$, we say $\displaystyle i$ is a fix point of $\displaystyle \sigma$.
A permutation may have several fix points, let $\displaystyle FP(\sigma)$ be the set of fix points of the permutation $\displaystyle \sigma$.

Problem: How many permutations are there whose fix-points set has exactly k elements(points)? k=0,1,...,n.
Solution: Fix the $\displaystyle \ell$ elements of $\displaystyle \{1,\cdots,n\}$ that you want to fix. Then, the number of permutations with those fixed points are precisely the amount of bijective maps one can form from $\displaystyle n-\ell$ points onto itself with $\displaystyle f(x)\ne x,\text{ }\forall x$. These are the derangements of $\displaystyle \left\{1,\cdots,n-\ell\right\}$. So, for the fixed $\displaystyle \ell$ elements there are $\displaystyle \text{Derange}\left(n-\ell\right)$ permutations. Thus, the total number of permutations is the number of ways you can pick the $\displaystyle \ell$ elements. Thus, the answer is $\displaystyle {n\choose \ell}\text{Derange}\left(n-\ell\right)$.

Remark: It can be proven that $\displaystyle \text{Derange}\left(k\right)$$\displaystyle =\text{floor}\left( \frac{k!}{e}+\frac{1}{2}\right)$

5. You could Google it. Or, I mean there is usually, or at least in a couple of my books, an adequate introduction to the concept of derangements mixed in with $\displaystyle S_n$ in group theory books.

6. Originally Posted by Shanks
Here is the standard way to count derangements.
$\displaystyle \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$.

That is gotten by use of the inclusion/exclusion rule.

7. Oh, I see.
There is a problem called " Euler envelope&box problem" in the Set theory.
They are very similar or exactly the same problem stated in a different way.
Thank you!

8. Originally Posted by Plato
Here is the standard way to count derangements.
$\displaystyle \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$.

That is gotten by use of the inclusion/exclusion rule.
Another question:
How to manipulate $\displaystyle \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$
to

$\displaystyle \text{Derange}(n)=\text{floor}\left( \frac{n!}{e}+\frac{1}{2}\right)$?
Can we prove that they are equal by induction?

9. Originally Posted by Shanks
Another question:
How to manipulate $\displaystyle \text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$
to

$\displaystyle \text{Derange}(n)=\text{floor}\left( \frac{n!}{e}+\frac{1}{2}\right)$?
Can we prove that they are equal by induction?
$\displaystyle n!\sum_{k=1}^{n}\frac{(-1)^k}{k!}=n!\left(\sum_{k=1}^{\infty}\frac{(-1)^k}{k!}-\sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}\right)=\frac{n!}{e}-n!\sum_{k=n+1}^{\infty}\frac{(-1)^k}{k!}$. You can take it from there.

10. Oh, I see. Thank you!