Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

christmas combinatorics

Name: Anonymous 2008-12-26 9:02

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

Name: Anonymous 2008-12-26 11:33

>>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

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List