1
$\begingroup$

Possible Duplicate:
Number of permutations where n ≠ position n

There are $N!$ permutations of the set $\{1,2,\ldots,N\}$

How many of them have zero identity elements?

An identity element is an element that has a value equal to its position. ie When for some $i$, the ith element equals $i$.

For example, $(2,3,4,1)$ has no identity elements, whereas $(2,1,3,4)$ has two identity elements.

  • 2
    These are called [derangements](http://en.wikipedia.org/wiki/Derangement). [This math.SE question](http://math.stackexchange.com/q/41949/264), and [this one](http://math.stackexchange.com/q/14666/264), cover the answer to your question.2012-06-16
  • 1
    Elements mapped to themselves by a permutation are called *fixed points*, not "identity elements".2012-06-16
  • 0
    http://math.stackexchange.com/questions/159158/counting-derangements-explanation-of-wp-description2012-06-16

1 Answers 1

2

The usual terminology would be "fixed points" or "1-cycles" instead of "identity elements".

A permutation with no fixed points is called a derangement. The Wikipedia article on derangements gives quite a bit of information about counting them.

  • 0
    http://math.stackexchange.com/questions/159158/counting-derangements-explanation-of-wp-description2012-06-16