2
$\begingroup$

I know that the number of permutations with no fixed points over a set with $n$ elements approaches $\frac{n!}e$ as $n$ grows.

I'm interested in finding a limit (if there's exist) for the number of permutations with a single fixed point.

Thank you

  • 1
    I think you mean "the number of permutations over a set with $n$ elements with no fixed points approaches $\frac{n!}{e}$."2012-01-21
  • 0
    corrected it... thanks.2012-01-21

1 Answers 1

7

If $D(n)$ denotes the number of derangements of $n$ (permutations with no fixed points), then a permutation with a single fixed point is just a fixed point together with a derangement of the non-fixed points, so there are $n D(n-1)$ such permutations on $n$ letters. Hence there are asymptotically $\frac{n!}{e}$ such permutations as well.

A more general approach to questions of this type that also allows you to place constraints on the number of $k$-cycles for any $k$ is given by the exponential formula; see this series of blog posts for an introduction.

  • 0
    Why D(n) is asymptotically n!/e? - Thanks2012-01-21
  • 0
    @Amihai: see for example http://en.wikipedia.org/wiki/Derangement .2012-01-21
  • 0
    Sorry, was not thinking. it's easy... thanks again!2012-01-21