2
$\begingroup$

I "created" this excercise on my own when I worked on a task relating to stochastics, but I might need a little bit of help.

Task

Let $M = \{1, 2, ..., N\}$ be a set and $N!$ the number of permuations $\sigma$ on $M$. Furthermore, let $k$ be the number of elements $i \in M$ with the property $\sigma(i) = i$. With $k$ being arbitrary, how many permutations are there with that specific number of fixed elements under $\sigma$?

My own "solution" so far:

Since $k$ is the number of fixed elements under $\sigma$, we have $N - k$ elements that are "loose". We can order these fixed elements such that they appear at the top of an imaginary diagram that shows us the various connections of the different elements. Now, we take a look at the $N - k$ elements that are still loose and wonder how many permuations we can generate. Overall, there are $(N - k)!$ permuations left.

I tried to distinguish between an even and odd number of elements of $M$, but that didn't lead me anywhere.

I would appreciate a hint on this one such that helps me figuring it out on my own.

$\endgroup$
  • $\begingroup$ If $k=0$ then you want the derangements. For general $k$, we note that there are $\binom nk$ ways to pick the $k$ fixed points, and then we need a derangement on the rest. $\endgroup$ – lulu Oct 17 '16 at 19:52
1
$\begingroup$

Pick which of the $k$ elements are fixed. Then, pick a specific derangement of the remaining elements.

There are $!(n-k) \cdot \binom{n}{k}$ such permutations matching your conditions.

$\endgroup$
  • $\begingroup$ ... which can be proven by induction? $\endgroup$ – Julian Oct 17 '16 at 20:03
  • $\begingroup$ It doesn't need induction. It is direct. $\endgroup$ – JMoravitz Oct 17 '16 at 20:06
  • $\begingroup$ Thanks, I'll have a look at it! $\endgroup$ – Julian Oct 17 '16 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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