Extension of Recursion to Missing Cycles

 

            We extend the logic we used to show  to find a recursion for , the number of permutations with no fixed points and no 2-cycles; this line of exploration will give insight into a pretty result.  As before, we think about adding the element .  If  is part of a 3-cycle, it must be last in the cycle; there are  ways to pick the first two elements in the cycle, and  ways to assign the other elements in the permutation.  If  is not part of a 3-cycle, there are  ways to insert it into a permutation counted by , so we have

 

 

 This recursion is not as amenable to our earlier tricks, but it is also straightforward to set up on a spreadsheet (Figure 1*), where we also calculate the probabilities that there are no 0 or 1 cycles. 

 

Figure 1*: Spreadsheet Set-UP for Computing , the Number of Permutations Without 1- or 2-Cycles and Associated Probabilities

 

 

 

From Table 2*, we see the probabilities seem to stabilize at around .223 or so, and since our last probability stabilized at , it makes sense to take natural logarithms to see whether this probability might be near a power of , and we see that it seems to be approaching . 

 

Table 2*: Exploring Values of  

 

 

 

 

 

0

1

1

 

 

1

0

0

 

 

2

0

0

 

 

3

2

0.33333333

 

-1.09861

4

6

0.25

 

-1.38629

5

24

0.2

 

-1.60944

6

160

0.22222222

 

-1.50408

7

1140

0.22619048

 

-1.48638

8

8988

0.22291667

 

-1.50096

9

80864

0.22283951

 

-1.5013

10

809856

0.2231746

 

-1.4998

11

8907480

0.22315115

 

-1.49991

12

106877320

0.22312518

 

-1.50002

13

1389428832

0.22312899

 

-1.50001

 

 

With similar logic, we find the recursion for the number of permutations with no 1, 2, or 3 cycles

 

 

and Table 3* shows that the probability that there are no 1, 2, or 3 cycles seems to approach , and continuing with further recursions shows that the probability that a permutation has no cycles of length  or less seems to approach . 

 

Table 3*: Exploring Values of , the Number of Permutations with No 1-, 2-, or 3-Cycles and Associated Probabilities

 

 

 

 

 

0

0

0

 

 

1

0

0

 

 

2

0

0

 

 

3

6

0.25

 

-1.386294361

4

24

0.2

 

-1.609437912

5

120

0.166666667

 

-1.791759469

6

720

0.142857143

 

-1.945910149

7

6300

0.15625

 

-1.85629799

8

58464

0.161111111

 

-1.825661021

9

586656

0.161666667

 

-1.822218677

10

6384960

0.15995671

 

-1.832852063

11

76471560

0.159647817

 

-1.834785031

12

994831200

0.159760379

 

-1.834080221

13

13939507296

0.159896542

 

-1.833228286

14

13939507296

0.159896542

 

-1.833228286

15

2.09098E+11

0.159900553

 

-1.8332032

 

 

 

It turns out that the probability that a permutation has no cycles of length  approaches  and these probabilities are all independent of each other, so that the probability that a permutation has no cycles of length  approaches .   These results are proved using advanced statistical techniques in Shepp and Lloyd (1966), and they can also be proved directly from the inclusion-exclusion property.  To get some sense of why they should be true (with a caveat that intuition can be faulty), we take  equal to some large number, say a million, and take a random permutation.  The expected number of fixed points is 1, and the probability that there are more than 5 fixed points is less than 0.1%.  The expected number of 2 cycles is .  The presence of such a small number of fixed points has negligible effect on the presence of such a small number of 2-cycles.

This is another result worthy of a pause: the expected number of  -cycles is , and the probability that there are no  -cycles is .  The reader is invited to find recurrences similar to those for  for the distributions of  -cycles, and to compute small cases and look for patterns.