Number Theory > Constants > Golomb-Dickman Constant >
Discrete Mathematics > Combinatorics > Permutations >
MathWorld Contributors > Finch, Steven >

Golomb-Dickman Constant

DOWNLOAD Mathematica Notebook

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

<sum_(j=1)^(infty)alpha_j>=sum_(i=1)^(n)1/i
(1)
=H_n
(2)
=lnn+gamma+O(1/n)
(3)
var(sum_(j=1)^(infty)alpha_j)=sum_(i=1)^(n)(i-1)/(i^2)
(4)
=H_n-H_(n,2)
(5)
=lnn-n+gamma-1/2-1/6pi^2+O(1/n)
(6)

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

In addition,

lim_(n->infty)P(alpha_1=0)=1/e
(7)

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

lim_(n->infty)P(alpha_j=k)=1/(k!)e^(-1/j)j^(-k),
(8)

which is a Poisson distribution, and

lim_(n->infty)P[(sum_(j=1)^inftyalpha_j-lnn)(lnn)^(-1/2)<=x]=Phi(x),
(9)

which is a normal distribution, gamma is the Euler-Mascheroni constant, and Phi(x) is the normal distribution function.

Let

M(alpha)=max_(j){j:alpha_j>0},
(10)

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

lambda=lim_(n->infty)(<M(alpha)>)/n
(11)
=0.6243299885...
(12)

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

Knuth (1997) asked for the constants b and c such that

lim_(n->infty)n^b[<M(alpha)>-lambdan-1/2lambda]=c,
(13)

and Gourdon (1996) showed that

<M(alpha)>=lambda(n+1/2)-(e^gamma)/(24n)+(1/(48)e^gamma-1/8(-1)^n)/(n^2)+((17)/(3840)e^gamma+1/8(-1)^n+1/6j^(1+2n)+1/6j^(2+n))/(n^3),
(14)

where

j=e^(2pii/3).
(15)

lambda can be expressed in terms of the function f(x) defined by f(x)=1 for 1<=x<=2 and

(df)/(dx)=-(f(x-1))/(x-1)
(16)

for x>2, by

lambda=int_1^infty(f(x))/(x^2)dx.
(17)

Shepp and Lloyd (1966) derived

lambda=int_0^inftyexp(-x-int_x^infty(e^(-y))/ydy)dx
(18)
=int_0^1exp(int_0^x(dy)/(lny))dx
(19)
=int_0^1e^(li(x))dx,
(20)

where li(x) is the logarithmic integral.

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

F(x)=lim_(n->infty)P(x,n)={1 if x>=1; int_0^xF(t/(1-t))(dt)/t if 0<=x<1,
(21)

where F(x) is now known as the Dickman function. Dickman then found the average value of x such that p=n^x, obtaining

mu=lim_(n->infty)<x>
(22)
=lim_(n->infty)<(lnp)/(lnn)>
(23)
=int_0^1x(dF)/(dx)dx
(24)
=int_0^1F(t/(1-t))dt
(25)
=0.62432999,
(26)

which is identical to lambda.

Wolfram Web Resources

Mathematica »

The #1 tool for creating Demonstrations and anything technical.

 Wolfram|Alpha »

Explore anything with the first computational knowledge engine.

 Wolfram Demonstrations Project »

Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more.
Computerbasedmath.org »

Join the initiative for modernizing math education.

 Online Integral Calculator »

Solve integrals with Wolfram|Alpha.

 Step-by-step Solutions »

Walk through homework problems step-by-step from beginning to end. Hints help you try the next step on your own.
Wolfram Problem Generator »

Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.

 Wolfram Education Portal »

Collection of teaching and learning tools built by Wolfram education experts: dynamic textbook, lesson plans, widgets, interactive Demonstrations, and more.

 Wolfram Language »

Knowledge-based programming for everyone.