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
![\begin{displaymath}
\left\langle{\,\sum_{j=1}^\infty \alpha_j}\right\rangle{} = ...
... {1\over i} = \ln n+\gamma+{\mathcal O}\left({1\over n}\right)
\end{displaymath}](g_1639.gif) |
(1) |
![\begin{displaymath}
\mathop{\rm var}\nolimits \left({\,\sum_{j=1}^\infty \alpha_...
...\textstyle{1\over 6}}\pi^2+{\mathcal O}\left({1\over n}\right)
\end{displaymath}](g_1640.gif) |
(2) |
![\begin{displaymath}
\lim_{n\to\infty} P(\alpha_1=0)={1\over e}
\end{displaymath}](g_1641.gif) |
(3) |
(Shepp and Lloyd 1966, Wilf 1990). Goncharov (1942) showed that
![\begin{displaymath}
\lim_{n\to\infty} P(\alpha_j=k)={1\over k!}e^{-1/j}j^{-k},
\end{displaymath}](g_1642.gif) |
(4) |
which is a Poisson Distribution, and
![\begin{displaymath}
\lim_{n\to\infty} P\left[{\left({\,\sum_{j=1}^\infty \alpha_j-\ln n}\right)(\ln n)^{-1/2}\leq x}\right]=\Phi(x),
\end{displaymath}](g_1643.gif) |
(5) |
which is a Normal Distribution,
is the Euler-Mascheroni Constant, and
is
the Normal Distribution Function. Let
Golomb (1959) derived
![\begin{displaymath}
\lambda\equiv\lim_{n\to\infty} {\left\langle{M(\alpha)}\right\rangle{}\over n}=0.6243299885\ldots,
\end{displaymath}](g_1649.gif) |
(8) |
which is known as the Golomb Constant or Golomb-Dickman constant. Knuth (1981) asked for the constants
and
such that
![\begin{displaymath}
\lim_{n\to\infty} n^b[\left\langle{M(\alpha)}\right\rangle{}-\lambda n-{\textstyle{1\over 2}}\lambda]=c,
\end{displaymath}](g_1650.gif) |
(9) |
and Gourdon (1996) showed that
![\begin{displaymath}
\left\langle{M(\alpha)}\right\rangle{}=\lambda(n+{\textstyle...
...e{1\over 6}} j^{1+2n}+{\textstyle{1\over 6}}j^{2+n}\over n^3},
\end{displaymath}](g_1651.gif) |
(10) |
where
![\begin{displaymath}
j\equiv e^{2\pi i/3}.
\end{displaymath}](g_1652.gif) |
(11) |
can be expressed in terms of the function
defined by
for
and
![\begin{displaymath}
{df\over dx}=-{f(x-1)\over x-1}
\end{displaymath}](g_1655.gif) |
(12) |
for
, by
![\begin{displaymath}
\lambda=\int_1^\infty {f(x)\over x^2}\,dx.
\end{displaymath}](g_1657.gif) |
(13) |
Shepp and Lloyd (1966) derived
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
![\begin{displaymath}
F(x)\equiv \lim_{n\to\infty} P(x,n) =\cases{
1 & if $x\geq ...
...^x F\left({t\over 1-t}\right){dt\over t} & if $0\leq x<1$.\cr}
\end{displaymath}](g_1663.gif) |
(15) |
Dickman then found the average value of
such that
, obtaining
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 Eric W. Weisstein
1999-05-25