Long permutations and long cycles

A permutation rearranges the elements of a list. The number of arrangements, say of a deck of cards, is finite, so eventually you have to arrive at an arrangement you’ve produced before, and history will repeat itself. Along the way, some cards may move in smaller cycles than others. Example For example, consider the permutation p = [5, 6, 2, 1, 0, 8, 3, 4, 9, 7] that sends i to p(i). Here indices start with 0. The number 2 is a fixed point: p(2) = 2. So it has a cycle length of 1. The number 1 is part of a cycle of length 3: p(1) = 6, p(6) = 3, and p(3) = 1. The longest cycle is [0, 5, 8, 9, 7, 4] which has length 6. Longest cycles What happens to the length of cycles as you permute longer lists? Obviously the longest possible cycle increases with the length of the list, but what happens to the average length of the longest cycle? Let Ln be the length of the longest cycle in a random permutation of n items. You’d expect the average value of Ln, written E[Ln], would increase when n…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town