Five people are preparing for a Christmas party. They organize a draw to decide who will have to buy a present for whom. On each of five tickets the name of one person is written. Next the tickets are being drawn. A draw is succesful if nobody draws the ticket with his own name. How many succesful draws are possible?
This is easy enough to do by hand, but this seems to be a combinatorics problem which can be generalized for n people. How can I find a way of doing this for n people using combinatorics/probability (in other words, how can I do this problem with combinatorics/probability)?
Answer
The underlying combinatorial notion for this problem is that of derangements. Just as $n!$ denotes the total number of permutations of an $n$-element set, $\{ 1 , \ldots , n \}$, the value $D_n$ denotes the total number of permutations of $\{ 1 , \ldots , n \}$ which leave no elements fixed. (In certain places you will see the notation $!n$ used instead, but as Douglas S. Stones remarks in a comment below, this notation may lead to ambiguity and is not very common in the literature.)
[The linked Wikipedia article says more about this topic than I know.]
No comments:
Post a Comment