2
$\begingroup$

Possible Duplicate:
I have a problem understanding the proof of Rencontres numbers (Derangements)

Given a vector of n elements, how can I calculate the number of "true" permutations, i.e. permutations that do not leave any element at the same position? Expressed differently, how do I find the number of possible $n\times n$ permutation matrices that only have zeros on their diagonal?

  • 1
    Such permutations without fixed points are called [*derangements*](http://en.wikipedia.org/wiki/Derangement); they’ve been discussed here many times, and the Wikipedia article to which I linked has information on counting them. (The closed formulas aren’t very nice, but the recurrences aren’t bad at all.) [This earlier question](http://math.stackexchange.com/questions/83380/i-have-a-problem-understanding-the-proof-of-rencontres-numbers-derangements) has some very comprehensive answers.2012-12-14
  • 0
    @BrianM.Scott: Thanks for the answer! I tried searching for "constant" or "invariant", but didn't find anything. So, derangements is the term... (Would you consider adding this as a "real" answer rather than a comment so that I can accept it?)2012-12-14
  • 0
    Sure, I can do that: give me a couple of minutes.2012-12-14

1 Answers 1

1

Such permutations without fixed points are called derangements; they’ve been discussed here many times, and the Wikipedia article to which I linked has information on counting them. (The closed formulas aren’t very nice, but the recurrences aren’t bad at all.) This earlier question has some very comprehensive answers.