*N.B. A detailed on-line essay by S. Finch
was the starting point for this entry.*

Let be a Permutation of elements, and let be the number of Cycles of length in this Permutation. Picking at Random
gives

(1) |

(2) |

(3) |

(4) |

(5) |

(6) | |||

(7) |

Golomb (1959) derived

(8) |

(9) |

(10) |

(11) |

(12) |

(13) |

(14) |

Mitchell (1968) computed to 53 decimal places.

Surprisingly enough, there is a connection between and Prime Factorization (Knuth and Pardo 1976, Knuth 1981, pp. 367-368, 395, and 611). Dickman (1930) investigated the probability
that the largest Prime Factor of a random Integer between 1 and satisfies for
. He found that

(15) |

(16) |

which is .

**References**

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/golomb/golomb.html

Gourdon, X. 1996. http://www.mathsoft.com/asolve/constant/golomb/gourdon.html.

Knuth, D. E. *The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed.* Reading, MA: Addison-Wesley, 1973.

Knuth, D. E. *The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed.* Reading, MA: Addison-Wesley, 1981.

Knuth, D. E. and Pardo, L. T. ``Analysis of a Simple Factorization Algorithm.'' *Theor. Comput. Sci.* **3**, 321-348, 1976.

Mitchell, W. C. ``An Evaluation of Golomb's Constant.'' *Math. Comput.* **22**, 411-415, 1968.

Purdom, P. W. and Williams, J. H. ``Cycle Length in a Random Function.'' *Trans. Amer. Math. Soc.* **133**, 547-551, 1968.

Shepp, L. A. and Lloyd, S. P. ``Ordered Cycle Lengths in Random Permutation.'' *Trans. Amer. Math. Soc.* **121**, 350-557, 1966.

Wilf, H. S. *Generatingfunctionology, 2nd ed.* New York: Academic Press, 1993.

© 1996-9

1999-05-25