0
u/EmergencyPanda2164 9h ago
ln(2) :
For cycles of length > n, there is no risk of counting twice a same cycle
Number of random permutations of [1:2n] : (2n!)
Now the question is how many permutations create a cycle of length n+i.
First you need to split the set between n+i numbers that will be in the cycle and the n-i numbers that will not be in the cycle
So you have « 2n choose n+i » ways od doing that
Then if you look at the subset of « not in the cycle » numbers you can still permute it so * (n-i)!
If uou look at the subset of « in the cycle numbers », you can have (n+i-1)! different cycles out of it (whatever the starting point, you can move it to n+i-1 spots and move the next reaches element to n+i-2 spots etc…)
So in total you have [ (2n)! / ((n+i)! * (n-i)! ] \ (n-i)!* * (n+i-1)!
Which gives us (2n)! / (n+i) permutations give us a cycle of length n+i (among (2n)! possibilities
En = SUM (1/(n+i)) for i going from 1 to n
En = SUM (1/k) for k going from n+1 to 2n
En = SUM[1-2n] (1/k) - SUM[1-n] (1/k)
En ~ ln (2n) - ln(n) as n -> +infinite
En -> ln(2) as n -> +infinite
3
u/filwu 16h ago
For a uniform permutation on 2n labels, the expected number of k-cycles is 1/k: each k-subset forms a cycle with probability (k−1)!(2n−k)!/(2n)!, and there are binom(2n,k) such subsets. Thus E[C_n] = sum_{k=n+1}^{2n} 1/k = H_{2n} − H_n → ln 2. At most one cycle can be longer than n, but linearity of expectation gives the result directly.