# Thread: Permutation and fix points

1. ## Permutation and fix points

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

Problem: How many permutations are there whose fix-points set has exactly k elements(points)? k=0,1,...,n.
Solution: Fix the $\ell$ elements of $\{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 $n-\ell$ points onto itself with $f(x)\ne x,\text{ }\forall x$. These are the derangements of $\left\{1,\cdots,n-\ell\right\}$. So, for the fixed $\ell$ elements there are $\text{Derange}\left(n-\ell\right)$ permutations. Thus, the total number of permutations is the number of ways you can pick the $\ell$ elements. Thus, the answer is ${n\choose \ell}\text{Derange}\left(n-\ell\right)$.

Remark: It can be proven that $\text{Derange}\left(k\right)$ $=\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 $S_n$ in group theory books.

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

$\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 $\text{Derange}(n)=n!\sum\limits_{k = 0}^n {\frac{{\left( { - 1} \right)^k }}{{k!}}}$
to

$\text{Derange}(n)=\text{floor}\left( \frac{n!}{e}+\frac{1}{2}\right)$?
Can we prove that they are equal by induction?
$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!