Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by Brian M. Scott, Davide Giraudo, QiL, martini, TMM Dec 14 '12 at 12:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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. –  Brian M. Scott Dec 14 '12 at 8:07
    
@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?) –  Thomas W. Dec 14 '12 at 8:51
    
Sure, I can do that: give me a couple of minutes. –  Brian M. Scott Dec 14 '12 at 8:52

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

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