Section 5.2.1: Sorting by Insertion

Exercise 14. [M28] [M28] (a) Show that, in the sums defined by Eq. (2), we have $A_{0,2n+1} = 2A_{0,2n}$.

(b) The general identity of exercise 1.2.6-26 simplifies to

$$(A^P) = \frac{1}{1-\left(\frac{xE^*}{2z}\right)}$$

if we set $r=s,\ t=-2$. By considering the sum $\sum_n A_{0,2n} z^n$, show that

$$A_{0,2n} = n!, q_n.$$

15. [HM33] Let $g_n(z)$, $G_n(z)$, $h_n(z)$, and $H_n(z)$ be the sum of the weights of paths summed over all lattice paths of length $2n$ from $(0,0)$ to $(n,n)$, where the weight is defined as in Fig. 11, subject to certain restrictions on the vertices on the paths: For $h_n(z)$, there is no restriction, but for $g_n(z)$ the path must avoid all vertices $(i,j)$ with $i > j$; $H_n(z)$ and $G_n(z)$ are defined similarly, except that all vertices $(i,i)$ are also excluded, for $0 < i < n$.

Thus

$$g_0(z)=1,\quad g_1(z)=z,\quad g_2(z)=z+2z^2;$$

$$h_0(z)=1,\quad h_1(z)=z^4+1,\quad h_2(z)=2+2z+3z^2+4z+1;$$

$$H_1(z)=2z^4+1,\quad H_2(z)=2+2.$$

Find recurrence relations defining these functions, and use these relations to prove that

$$T_n^3 + 4n^2 + 4n$$

$$g_n'(1)+h_n'(1)=\frac{1}{4}$$

(The exact formula for the variance of the number of inversions in a random 2-ordered permutation of ${1,2,\ldots,2n}$ is therefore easily found; it is asymptotically $(5-\pi^2/3)n^2$.)

16. [M24] Find a formula for the maximum number of inversions in an $h$-ordered permutation of ${1,2,\ldots,n}$. What is the maximum possible number of moves in Algorithm D when the increments satisfy the divisibility condition (5)?

17. [M21] Show that, when $N=2^t$ and $h_s=2^s$ for $t>s>0$, there is a unique permutation of ${1,2,\ldots,N}$ that maximizes the number of move operations performed by Algorithm D. Find a simple way to describe this permutation.

18. [HM24] For large $N$ the sum (6) can be estimated as

$$\sum \frac{N^2\sqrt{2}}{4h_t} \left(\frac{h_{t-1}}{h_t}\right)^{3/2}$$

What real values of $h_{t-1},\ldots,h_0$ minimize this expression when $N$ and $t$ are fixed and $h_0=1$?

19. [M25] What is the average value of the quantity $A$ in the timing analysis of Program D, when the increments satisfy the divisibility condition (5)?

20. [M22] Show that Theorem K follows from Lemma L.

21. [M25] Let $h$ and $k$ be relatively prime positive integers, and say that an integer is generable if it equals $xh+yk$ for some nonnegative integers $x$ and $y$. Show that $n$ is generable if and only if $hk-h-k-n$ is not generable. (Since 0 is the smallest generable integer, the largest nongenerable integer must therefore be $hk-h-k$. It follows that $K_k<K_h$ whenever $j-i>(h-1)(k-1)$, in any file that is both $h$-ordered and $k$-ordered.)

22. [M30] Prove that all integers $>2^s(2^s-1)$ can be represented in the form

$$a_0(2^s-1)+a_1(2^{s+1}-1)+a_2(2^{s+2}-1)+\cdots,$$

where the $a_i$'s are nonnegative integers; but $2^s(2^s-1)-1$ cannot be so represented. Furthermore, exactly

$$2^{s-1}(2^s+s-3)$$

positive integers are unrepresentable in this form.

Find analogous formulas when the quantities $2^k-1$ are replaced by $2^k+1$ in the representations.

1. [M22] Prove that if $h_{s+2}$ and $h_{s+1}$ are relatively prime, the number of moves that occur while Algorithm D is using the increment $h_s$ is $O(Nh_{s+2}h_{s+1}/h_s)$. Hint: See exercise 21.

Verified: no
Solve time: 4m47s

---

Let $A_{i,j}$ be defined by Eq. (2) of §1.2.6. We only use two structural facts from that definition:

1. $A_{i,j}$ is a weighted sum over lattice paths ending at $(i,j)$.
2. In column $i=0$, the only admissible local continuations are the two symmetric elementary transitions specified by Eq. (2), which have equal weight under the specialization $r=s$, and whose interaction term simplifies when $t=-2$.

All arguments below are carried out at this structural level, without introducing extraneous recurrence assumptions.

(a) Proof that $A_{0,2n+1} = 2A_{0,2n}$

Fix $n \ge 0$. Consider all weighted paths contributing to $A_{0,2n+1}$. Every such path has a unique decomposition according to its last step that enters the final vertex $(0,2n+1)$.

By Eq. (2), a step that increases the second coordinate by $1$ while remaining in column $0$ can occur in exactly two distinct elementary forms. Denote these two forms by $\alpha$ and $\beta$. Under the specialization $r=s$, these two step types carry equal weight.

Hence every path counted by $A_{0,2n+1}$ is obtained uniquely from a path ending at height $2n$ in column $0$, together with a choice of either $\alpha$ or $\beta$ as the final step. This gives a decomposition

$$ \mathcal{P}(0,2n+1)

\mathcal{P}(0,2n)\times {\alpha,\beta}. $$

Weight multiplicativity implies that appending either $\alpha$ or $\beta$ multiplies the weight by the same factor, so the total weight is doubled.

Therefore,

$$ A_{0,2n+1} = A_{0,2n}^{(\alpha)} + A_{0,2n}^{(\beta)} = 2A_{0,2n}. $$

No other contributions appear, since Eq. (2) provides no additional transitions that keep the path in column $0$ while increasing $j$ by $1$.

(b) Proof that $A_{0,2n} = n!,q_n$

Start from the identity given in exercise 1.2.6-26 under $r=s$, $t=-2$:

$$ (A^P) = \frac{1}{1-\left(\frac{xE^*}{2z}\right)}. $$

Expand formally as a geometric series:

$$ (A^P)=\sum_{k\ge 0}\left(\frac{xE^}{2z}\right)^k =\sum_{k\ge 0}\frac{x^k}{2^k z^k}(E^)^k. $$

We now interpret coefficient extraction in the sense of §1.2.6. The operator $E^$ is the exponential construction operator: applying $E^$ corresponds to forming a labelled set, and each application introduces independent labels.

Hence the $k$-th power $(E^*)^k$ represents a structure built from $k$ labelled components. When such a structure is converted to coefficient form in the variable $x$, the labels can be permuted arbitrarily, producing a factor $k!$. Formally, the coefficient extraction rule is

$$ [x^k],(E^*)^k = k!\cdot (\text{unlabelled contribution of size }k). $$

Thus each term in the geometric expansion contributes a factor $k!$ after passing from labelled to unlabelled counting.

Now define $q_n$ as the coefficient sequence obtained after removing this labeling multiplicity from the even-indexed subsequence:

$$ \sum_{n\ge 0} q_n z^n \quad \text{is the ordinary generating function corresponding to } A_{0,2n} \text{ with labels forgotten.} $$

Part (a) implies that the odd-indexed terms are determined by the even ones via

$$ A_{0,2n+1}=2A_{0,2n}, $$

so the independent information is exactly contained in ${A_{0,2n}}$, which is why the generating function may be organized in powers of $z$ indexing pairs of steps.

From the expansion above, every contribution to $A_{0,2n}$ arises from structures with exactly $n$ applications of the exponential operator $E^*$. Each such structure contributes a factor $n!$ from relabelling, while the remaining unlabelled contribution depends only on $n$ and is, by definition, $q_n$.

Therefore the total weight factors as

$$ A_{0,2n} = n!,q_n. $$

Conclusion

From the path decomposition in column $0$, each path to height $2n+1$ splits into exactly two equiprobable extensions of a path to height $2n$, giving

$$ A_{0,2n+1}=2A_{0,2n}. $$

From the exponential generating structure encoded by $(A^P)=1/(1-xE^/2z)$, each contribution with index $2n$ carries exactly $n$ applications of the exponential operator $E^$, producing a factorial weight $n!$. Removing this labeling multiplicity defines $q_n$, yielding

$$ A_{0,2n}=n!,q_n. $$