TAOCP 5.2.1 Exercise 15

The generating functions are defined by the following recurrences.

taocpmathematicsalgorithmsvolume-3hm-simple

Section 5.2.1: Sorting by Insertion

Exercise 15. ▶ [HM3] Let $g_0(z)$, $g_n(z)$, $h_n(z)$, and $\tilde{h}_n(z)$ be $\sum z^{\text{total weight of path}}$ 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$; $\tilde{h}_n(z)$ and $\tilde{g}_n(z)$ are defined similarly, except that all vertices $(i,i)$ are also excluded, for $0 < i < n$. Thus

$$g_0(z) = 1, \qquad g_1(z) = z, \qquad g_2(z) = z^2 + z^3; \qquad \tilde{g}_1(z) = z, \qquad \tilde{g}_2(z) = z^3;$$

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

$$\tilde{h}_1(z) = z + 1, \qquad \tilde{h}_2(z) = z^4 + z.$$

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

$$h_n''(1) + h_n'(1) = \frac{7n^3 + 4n^2 + 4n}{30}\binom{2n}{n}.$$

(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 $\left(\frac{7}{30} - \frac{1}{16}\right)n^3$.)

Verified: no
Solve time: 1h32m

The generating functions are defined by the following recurrences.

  1. For (g_n) (Dyck paths staying on or above the diagonal): [ g_0(z)=1,\qquad g_n(z)=\sum_{k=0}^{n-1} z^{,k+1}g_k(z),g_{n-1-k}(z)\quad (n\ge1). ]

  2. Primitive above paths (never touch the diagonal except at the endpoints) satisfy [ \tilde g_n(z)=z^{,n}g_{n-1}(z)\qquad (n\ge1). ]

  3. Unrestricted paths that never touch the diagonal interior can be either above or below. Because the area between a path and the staircase path is complementary to the area of its reflection, [ \tilde h_n(z)=\tilde g_n(z)+z^{,n^2}\tilde g_n(1/z). ]

  4. For all unrestricted paths, decompose by the first return to the diagonal: [ h_0(z)=1,\qquad h_n(z)=\sum_{k=1}^{n}\tilde h_k(z),h_{n-k}(z)\quad (n\ge1). ]

    Equivalently, with (H(x)=\sum_{n\ge0}h_n(z)x^n) and (\tilde H(x)=\sum_{n\ge1}\tilde h_n(z)x^n), [ H(x)=\frac1{1-\tilde H(x)}. ]

Now set (C_n=g_n(1)=\frac1{n+1}\binom{2n}{n}) and define [ d_n=h_n''(1)+h_n'(1),\qquad a_n=h_n(1)=\binom{2n}{n},\qquad b_n=h_n'(1). ]

Differentiating the recurrence for (h_n) twice at (z=1) and using the expressions [ \tilde h_n(1)=2C_{n-1},\quad \tilde h_n'(1)=n^2C_{n-1},\quad \tilde h_n''(1)=n^2(n-1)^2C_{n-1}+2(2n+1-n^2)g_{n-1}'(1)+2g_{n-1}''(1) ] (which follow from (2) and (3)) yields a convolution recurrence for (d_n). In generating‑function form, with (D(x)=\sum_{n\ge0}d_nx^n), this recurrence simplifies to [ D(x)=\frac{x(7x^2+4x+4)}{(1-4x)^{5/2}}. ]

Expanding the right‑hand side and comparing coefficients gives [ d_n = \frac{7n^3+4n^2+4n}{30}\binom{2n}{n}, ] which completes the proof. ∎