 perico
Topic Author
Posts: 16
Joined: July 14th, 2002, 3:00 am

### Secret Santa

Hi, guys, an easy problem for you:We have 10 people. Each one of them has to make a present to somebody else (not to himself), so that everyone will end up with one present from another guy from the group. After a valid draw in which everybody will get a present, which is the probability that at least one couple will share a present, that is A will give a present to B and B to A?. Which is the answer for n people?Note that the probability is AFTER a valid draw (in which nobody gives away to himself), which by the way is a different problem. wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

### Secret Santa

perico,essentially one needs to count the number of permutations without certain types of cycles. to calculate the probability (assuming all the valid draws are equally possible), denominator: the ones with no fixed point, which is known as 'derangement' (e.g., here is one hard version); numerator: denominator less the ones with no fixed point and no 2-cycles. one could write down the recurrence relation, but a simpler way is to consider the exponential generating function: starts with the one for all cycles: 1/(1-z) and sequentially removing the fixed point then the two cycles, i.e., denominator: the coefficients of exp(-z)/(1-z) and numerator: [exp(-z)-exp(-z-z^2/2)]/(1-z).for reference when n=10, one gets: 525105/1334961, which is already close to the limit of 1-1/sqrt(e) when n -> infty
Last edited by wileysw on June 26th, 2015, 10:00 pm, edited 1 time in total. riccardox
Posts: 2
Joined: February 25th, 2016, 2:29 pm

### Secret Santa

this is solved in a book Mosteller with an elementary method "straight from the book" let's say.  