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.

I am taking a probability course and we have been of course learning the classic problems of men with hats or variations of that in some other form. The problems being of the type if n men have n hats and mix them all together, whats the probability 0, 1, 2, or k men choose there hat. But from what I can gather is that they are all problems of the same type, for any given random permutation of k objects how many fixed points are there (we weren't taught this way, just my observations). My professor taught us to solve this using conditional probabilities (conditioning on whether the first person matched and then generating a system of equations) and using the inclusion-exclusion principle. But is there any other way to reason this?

Thanks for reading..

share|improve this question
1  
Are you sure you don't mean "for any given number of fixed points, how many permutations there are"? –  Qiaochu Yuan Feb 17 '11 at 19:18
    
ah. yes that is what I meant.. Apologies. –  user7198 Feb 17 '11 at 20:07
    
I answered this question here: math.stackexchange.com/questions/17320/… . I'll let the community decide whether this is a duplicate though. –  Qiaochu Yuan Feb 19 '11 at 0:03
    
I would say not quite a duplicate, as the other question asks for an explanation of a certain formula for these numbers, and this one asks for another way of finding a formula for them. (Nice answer on the other question, though, Qiaochu. I would upvote it if I hadn't already.) –  Mike Spivey Feb 19 '11 at 0:12

2 Answers 2

I believe these are called Rencontres Numbers (the number of permutations with exactly $k$ fixed points). These are also called Partial Derangements, I believe.

The wiki page I linked to gives you a recursive/generating function approach I believe (which I suppose could possibly be the conditional probability approach you mention).

Hope that helps.

share|improve this answer
1  
I just corrected the spelling of "rencontre" - hope you don't mind... :) –  Mike Spivey Feb 18 '11 at 21:37
    
@Mike: Thanks! I would have kept saying recon-tres :-) –  Aryabhata Feb 18 '11 at 21:39

The paper "Matchings, Derangements, Rencontres," by Hanson, Seyffarth, and Weston, has a nice discussion of the rencontre and related problems, including a generalization of the rencontre problem. They also prove an interesting recursive formula not given in the Wikipedia page linked to in Moron's answer:

$$D_{n,k} = n D_{n-1,k} + (-1)^{n-k} \binom{n}{k}.$$

This, of course, contains the famous derangement recurrence as a special case:

$$D_n = n D_{n-1} + (-1)^n,$$ where $D_n$ is the number of derangements (no fixed points) on $n$ elements.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.