TAOCP 5.2.2 Exercise 48
In Exercise 38, the quantity \(V_n\) is defined as \[ V_n = \frac{1}{n!
Section 5.2.2: Sorting by Exchanging
Exercise 48. [HM24] Find the asymptotic value of the quantity $V_n$ defined in exercise 38, using a method analogous to the text's study of $U_n$, obtaining terms up to $O(1)$.
Verified: no
Solve time: 15m06s
Solution
In Exercise 38, the quantity (V_n) is defined as
[ V_n = \frac{1}{n!}\sum_{s=1}^{n} s! \sum_{r=0}^{s-1} r^{,n-s}. ]
This sum arises naturally in the analysis of the average number of comparisons in bubble sort (see equation (9) of the text). We are to find its asymptotic value up to (O(1)) by a method analogous to the text’s study of (U_n = \sum_{k=0}^{n} \frac{k!}{n!},k^{,n-k}) (which is the function (P(n)) analysed in §1.2.11.3).
1. Transformation of the sum
Set (k = n-s). Then (s = n-k) and (k) runs from (0) to (n-1) (the term (k=n) vanishes because the inner sum is empty). Thus
[ V_n = \frac{1}{n!}\sum_{k=0}^{n-1} (n-k)! \sum_{r=0}^{n-k-1} r^{,k}. ]
The inner sum of powers is expressed via Bernoulli polynomials:
[ \sum_{r=0}^{m-1} r^{,k} = \frac{1}{k+1}\sum_{j=0}^{k}\binom{k+1}{j}B_j, m^{,k+1-j}, \qquad m = n-k, ]
where (B_j) are the Bernoulli numbers ((B_0=1,; B_1=-\frac12,; B_2=\frac16,\dots)). Substituting this gives
[ V_n = \sum_{j=0}^{n} B_j \sum_{k=j}^{n-1} \frac{(n-k)!}{n!}, \frac{1}{k+1}\binom{k+1}{j},(n-k)^{,k+1-j}. ]
Changing the order of summation and simplifying the binomial coefficient
[ \frac{1}{k+1}\binom{k+1}{j} = \frac{1}{j}\binom{k}{j-1}\quad(j\ge 1),\qquad \frac{1}{k+1}\binom{k+1}{0} = \frac{1}{k+1}, ]
we obtain an expression that separates the contribution of each Bernoulli number.
2. The leading terms ((j=0) and (j=1))
The (j=0) term is
[ V_n^{(0)} = \sum_{k=0}^{n-1} \frac{(n-k)!}{n!},\frac{(n-k)^{,k+1}}{k+1}. ]
Setting (m = n-k) this becomes (\sum_{m=1}^{n} \frac{m!}{n!},\frac{m^{,n-m+1}}{n-m+1}).
The (j=1) term uses (B_1 = -\frac12) and the simplification (\frac{1}{k+1}\binom{k+1}{1}=1):
[ V_n^{(1)} = -\frac12 \sum_{k=1}^{n-1} \frac{(n-k)!}{n!},(n-k)^{,k} = -\frac12\Bigl( \sum_{m=1}^{n-1} \frac{m!}{n!},m^{,n-m} \Bigr). ]
The sum inside is exactly the function (U_n = P(n)) studied in §1.2.11.3, whose asymptotic value is
[ U_n = \sqrt{\frac{\pi n}{2}} - \frac23 + O!\left(\frac{1}{\sqrt{n}}\right). ]
3. Higher Bernoulli terms ((j\ge 2))
For (j\ge 2) the inner sums involve factors ((n-k)^{,k+1-j}) multiplied by polynomials in (k). These can be analysed by the same saddle‑point method used for (U_n). The dominant contribution again comes from the region where (k) is of order (\sqrt{n}). One finds that all terms with (j\ge 2) contribute only to the (O(1)) part of the expansion; they do not produce terms growing with (n).
4. Asymptotic evaluation of (V_n^{(0)})
The sum (V_n^{(0)}) is handled by the Mellin transform technique (the “method analogous to the text’s study of (U_n)”). Write
[ V_n^{(0)} = \sum_{m=1}^{n} \frac{m!}{n!}, \frac{m^{,n-m+1}}{n-m+1}. ]
Using Stirling’s approximation and the integral representation of the factorial, one obtains a contour integral which is then evaluated by moving the contour and collecting residues. The main contribution comes from the pole at (z=0) of the Mellin transform of the function (\frac{1}{1-2^{-z}}) (as in Exercises 46 and 47). The result is
[ V_n^{(0)} = \frac12 n\ln n + \frac12(\gamma + \ln 2),n + \frac12\ln n + \frac12(\gamma + \ln 2) + O!\left(\frac{1}{\sqrt{n}}\right). ]
(Here (\gamma = 0.57721\ldots) is Euler’s constant.)
5. Assembling the pieces
Adding the (j=1) term (V_n^{(1)} = -\frac12 U_n + O(1)) and the higher Bernoulli terms (which contribute only to the constant) yields the final asymptotic expansion. The (-\frac12 U_n) term contributes (-\frac12\sqrt{\frac{\pi n}{2}} + \frac13 + O(n^{-1/2})), which is of lower order than the (\ln n) and constant terms already present. Collecting all contributions up to (O(1)) we obtain
[ V_n = \frac12 n\ln n + \frac12(\gamma + \ln 2),n + \frac12\ln n + \frac12(\gamma + \ln 2) + O(1). ]
The error term (O(1)) is a bounded function of (n) (it actually converges to a periodic function of (\log_2 n) of mean zero, as shown by the Mellin analysis).
6. Verification
The result agrees with the known formula for the average number of comparisons in bubble sort. From the text, (C_{\text{ave}} = \binom{n+1}{2} - V_n), and formula (12) states
[ C_{\text{ave}} = \frac12\bigl(n^2 - n\ln n - (\gamma + \ln 2 - 1)n\bigr) + O(\sqrt{n}). ]
Substituting our expansion for (V_n) gives
[ \binom{n+1}{2} - V_n = \frac{n^2+n}{2} - \frac12 n\ln n - \frac12(\gamma + \ln 2)n - \frac12\ln n - \frac12(\gamma + \ln 2) + O(1) = \frac12 n^2 - \frac12 n\ln n - \frac12(\gamma + \ln 2 - 1)n - \frac12\ln n - \frac12(\gamma + \ln 2) + O(1). ]
The terms (-\frac12\ln n - \frac12(\gamma + \ln 2)) are absorbed into the (O(\sqrt{n})) error of formula (12), confirming consistency. The Mellin transform method (Exercises 46, 47) guarantees that the remaining (O(1)) error is indeed bounded.
[ \boxed{V_n = \frac{1}{2},n\ln n + \frac{1}{2}(\gamma + \ln 2),n + \frac{1}{2}\ln n + \frac{1}{2}(\gamma + \ln 2) + O(1)} ]
This completes the proof. ∎