Golomb-Dickman Constant

Let  be a permutation of  elements, and let  be the number of permutation cycles of length  in this permutation. Picking  at random, it turns out that

			(1)
			(2)
			(3)
			(4)
			(5)
			(6)

(Shepp and Lloyd 1966, Wilf 1990), where  is a harmonic number and  is a generalized harmonic number.

In addition,

(7)

(Shepp and Lloyd 1966, Wilf 1990). Goncharov (1942) showed that

(8)

which is a Poisson distribution, and

(9)

which is a normal distribution,  is the Euler-Mascheroni constant, and  is the normal distribution function.

Let

(10)

i.e., the length of the longest cycle in . Golomb (1964) computed an approximation (with a sizable error) to the constant defined as

			(11)
			(12)

(OEIS A084945) and which is known as the Golomb constant or Golomb-Dickman constant.

Knuth (1997) asked for the constants  and  such that

(13)

and Gourdon (1996) showed that

(14)

where

(15)

 can be expressed in terms of the function  defined by  for  and

(16)

for , by

(17)

Shepp and Lloyd (1966) derived

			(18)
			(19)
			(20)

where  is the logarithmic integral.

Surprisingly, there is a connection between  and prime factorization (Knuth and Pardo 1976, Knuth 1997, pp. 367-368, 395, and 611). Dickman (1930) investigated the probability  that the greatest prime factor  of a random integer between 1 and  satisfies  for . He found that

(21)

where  is now known as the Dickman function. Dickman then found the average value of  such that , obtaining

			(22)
			(23)
			(24)
			(25)
			(26)

which is identical to .

REFERENCES:

Dickman, K. "On the Frequency of Numbers Containing Prime Factors of a Certain Relative Magnitude." Arkiv för Mat., Astron. och Fys. 22A, 1-14, 1930.

Finch, S. R. "Golomb-Dickman Constant." §5.4 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 284-292, 2003.

Golomb, S. W. "Random Permutations." Bull. Amer. Math. Soc. 70, 747, 1964.

Goncharov, W. "Sur la distribution des cycles dans les permutations." C. R. (Dokl.) Acad. Sci. URSS 35, 267-269, 1942.

Goncharov, W. "On the Field of Combinatory Analysis." Izv. Akad. Nauk SSSR 8, 3-48, 1944. English translation in Amer. Math. Soc. Transl. 19, 1-46, 1962.

Gourdon, X. Combinatoire, Algorithmique et Géometrie des Polynômes. Ph. D. thesis. École Polytechnique, 1996.

Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.

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.

Sloane, N. J. A. Sequences A084945, A174974, and A174975 in "The On-Line Encyclopedia of Integer Sequences."

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