Recursion for Number of Cycles
We have already seen that the
expected number of cycles in a permutation of size is
;
now we take a look at the distribution of permutations with various numbers of
cycles. Let
be the number of permutations of
with
cycles, and, as before, consider the effects
of adding in
. If
is part of a 1-cycle, there are
ways to assign the remaining students to the
remaining
cycles.
If
is not part of a 1-cycle, we can insert it
into any of the permutations counted in
in
ways.
Thus, we have,
|
|
|
The numbers generated by this recursion are called (unsigned) Stirling Numbers of the First Kind (see, for example, Graham et. al. Section 6.1). This recursion bears some resemblance to the one that generates Pascal’s Triangle and is straightforward to implement on a spreadsheet (Figure 4*).
Figure 4*: Spreadsheet Set-Up
for Computing
Table 5* shows values of the Stirling Numbers. The reader is invited to look for patterns in this table.
Table 5*: Permutations of n
with k cycles (
|
Number of Players (n) |
|
Number of Cycles (k) |
||||||||||
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
2 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
3 |
0 |
2 |
3 |
1 |
|
|
|
|
|
|
|
|
|
4 |
0 |
6 |
11 |
6 |
1 |
|
|
|
|
|
|
|
|
5 |
0 |
24 |
50 |
35 |
10 |
1 |
|
|
|
|
|
|
|
6 |
0 |
120 |
274 |
225 |
85 |
15 |
1 |
|
|
|
|
|
|
7 |
0 |
720 |
1764 |
1624 |
735 |
175 |
21 |
1 |
|
|
|
|
|
8 |
0 |
5040 |
13068 |
13132 |
6769 |
1960 |
322 |
28 |
1 |
|
|
|
|
9 |
0 |
40320 |
109584 |
118124 |
67284 |
22449 |
4536 |
546 |
36 |
1 |
|
|
|
10 |
0 |
362880 |
1026576 |
1172700 |
723680 |
269325 |
63273 |
9450 |
870 |
45 |
1 |
|
Figure 6* shows bar graphs of the probability distribution
of the number of cycles for . These graphs are all skewed to the right
(meaning there are more bars to the right of the median than to the left), but
as
gets bigger, they get closer to looking like a
normal distribution (i.e. a “bell shaped curve”). Shepp and Lloyd (1966) proved that these
distributions approach normal. These
graphs show how unlikely it is, as
gets bigger, that there will be many cycles of
small length.
Figure 6*: Probability Distribution of Number of Cycles for Several Values of n
6*a. 6*b
6*c. 6*d.
Graham, Ronald L., Knuth, Donald E., and Patashnik, Oren. Concrete Mathematics: A Foundation for
Computer Science, 2nd edition.
L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1966), 340-357.
Note: This is a supplement to, Borkovitz, Debra, “The Name Game: Exploring Random Permutations.” Mathematics Teacher 98 (October 2005).
PDF Version Back to Articles Home