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.

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.

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

GZIP: On