June 27th, 2015, 6:54 am
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.