christmas combinatorics

assuming everyone knows how the 'secret santa' system works

given n people in a randomly selected 'secret santa' arrangement (each person draws a name out of a hat, nobody can have themself, etc), what is the probability that there are no pairs of people that have each other?

this question has been bugging the hell out of me because i don't know enough graph theory and it can probably be solved with digraphs. plus it's probably obvious

How exactly were you going to approach it with graph theory?

i lol'd

>>2
every valid secret santa arrangement can be represented as a digraph with no loops, where each vertex has exactly one edge entering/exiting it (i'm not very sure on this terminology). incidentally it turns out every valid arrangement is a derangement of n objects.. you could get the probability by counting how many derangements have no 2-cycles in their distinct cycle decomposition. i was thinking graph theory because i only know the basics and it seems appropriate

hell yeah abuse of terminology

>>4
Hell yeah!

>>4
Doesn't seem a very good idea to me, i've never really seen graphs used to prove probabalistic statements except if you use random graphs.

I'd be more inclined to just induct.

What you want is the probability that a random permutation of n elements has no fixed points and no transpositions in its cycle decomposition.  If you follow the same method as here:

http://en.wikipedia.org/wiki/Random_permutation_statistics#Number_of_permutations_that_are_derangements

you can calculate this as being the sum of the first n coefficients in  the taylor expansion of e^{-z -z^2/2}.  However if n is big at all (say greater than 10), this is practically just e^{-1 -1^2/2} = e^{-3/2} = 0.22313.

Now if you already know that there are no fixed points (noone has their own name), you can divide this by the probability that a random cycle has no fixed points, which is calculated at the wikipedia article as e^{-1} = .36788.  This gives a probability of e^{-1/2} = 0.60653.

oh good, it wasn't totally obvious! thanks for that, now i can sleep easy

(i wouldn't have thought of doing it that way because i haven't learned a thing about generating functions...)