|
|
A330852
|
|
Numerator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n*2^n*(A(n) - (n - 1)!*zeta(n)) of the limiting distribution of the number of comparisons in quicksort, for n >= 2, with A(0) = 1 and A(1) = 0.
|
|
9
|
|
|
1, 0, 7, 19, 937, 85981, 21096517, 7527245453, 19281922400989, 7183745930973701, 3616944955616896387, 273304346447259998403709, 76372354431694636659849988531, 25401366514997931592208126670898607, 110490677504100075544188675746430710672527, 37160853195949529205295416197788818165029489819
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.
First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence
Sum_{r=0..p} Stirling1(p+2, r+1)*B(p-r)/(p-r)! + Sum_{r=0..p} F(r)*F(p-r) = 0, where F(r) = Sum_{i=0..r} Stirling1(r+1,i+1)*G(r-i) and G(k) = Sum_{a=0..k} (-1)^a*B(k-a)/(a!*(k-a)!*2^a).
Then A(n) = L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.
Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants (-2)^n*A(n), which they denote by a_n. See also Finch (2020).
The Maple program below is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.
The rest of the references give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).
|
|
REFERENCES
|
Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.
|
|
LINKS
|
S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019. [They have the first eight moments for the number of comparisons in quicksort from which Hennequin's first eight asymptotic cumulants can be derived.]
|
|
EXAMPLE
|
The first few fractions A(n) are
1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...
The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) are
1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...
|
|
MAPLE
|
# Produces the sequence (B(n): n >= 0)
B := proc(m) option remember: local v, g, f, b:
if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
if 2 <= m then
g := proc(k) add((-1)^a*B(k - a)/(a!*(k - a)!*2^a), a = 0 .. k): end proc:
f := proc(r) add(Stirling1(r + 1, i + 1)*g(r - i), i = 0 .. r): end proc:
b := proc(p) (-1)^p*(add(Stirling1(p + 2, r + 1)*B(p - r)/(p - r)!, r = 1 .. p) + add(f(rr)*f(p - rr), rr = 1 .. p - 1) + 2*(-1)^p*p!*add((-1)^a*B(p - a)/(a!*(p - a)!*2^a), a = 1 .. p) + 2*add(Stirling1(p + 1, i + 1)*g(p - i), i = 1 .. p))/(p - 1): end proc:
v := simplify(b(m)): end if: v: end proc:
# Produces the sequence (A(n): n >= 0)
A := proc(m) option remember: local v:
if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
if 2 <= m then v := -(m - 1)!*add(A(k + 1)*B(m - 1 - k)/(k!*(m - 1 - k)!), k = 0 .. m - 2) + B(m): end if: v: end proc:
# Produces the sequence of numerators of the A(n)'s
seq(numer(A(n)), n = 0 .. 15);
|
|
MATHEMATICA
|
B[m_] := B[m] = Module[{v, g, f, b}, If[m == 0, v = 1]; If[m == 1, v = 0]; If[2 <= m, g[k_] := Sum[(-1)^a*B[k - a]/(a!*(k - a)!*2^a), {a, 0, k}]; f[r_] := Sum[StirlingS1[r + 1, i + 1]*g[r - i], {i, 0, r}]; b[p_] := (-1)^p*(Sum[StirlingS1[p + 2, r + 1]*B[p - r]/(p - r)!, {r, 1, p}] + Sum[f[rr]*f[p - rr], {rr, 1, p - 1}] + 2*(-1)^p*p!*Sum[(-1)^a*B[p - a]/(a!*(p - a)!*2^a), {a, 1, p}] + 2*Sum[StirlingS1[p + 1, i + 1]*g[p - i], {i, 1, p}])/(p - 1); v = Simplify[b[m]]]; v];
A[m_] := A[m] = Module[{v}, If[ m == 0, v = 1]; If[m == 1, v = 0]; If[2 <= m , v = -(m - 1)!*Sum[A[k + 1]*B[m - 1 - k]/(k!*(m - 1 - k)!), {k , 0 , m - 2}] + B[m]]; v];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|