Chapter 7: Permutations

Exercise 7.1 🌟

This exercise illuminates the properties (mentioned in the book) related to an inversion table in some detail. It explains how to compute the number of left-to-right maxima, right-to-left minima, and right-to-left maxima from the inversion table.

All algorithms run in $\Theta(N)$ time without first trying to reconstruct the associated permutation.

• left-to-right maxima: Traverse the inversion table from left to right and register indices where $q_k=0$.

• right-to-left maxima: If $p_k$ is a RTL maximum, all elements greater than $p_k$ must be to its left. Therefore, a smaller $q_k$ means the element itself is larger. By traversing the inversion table right-to-left, the RTL maxima correspond exactly to the indices where $q_k$ achieves a new minimum.

  1. Initialize $\text{min$_q$} = \infty$ and an empty list.

  2. Traverse $k$ backwards from $N$ to 1:

     1. If $q_k < \text{min$_q$}$, add $k$ to the list and update $\text{min$_q$}=q_k$.

• right-to-left minima: Let $s_k = k- 1 - q_k$ denote the number of elements to the left of $p_k$ that are smaller than $p_k$. Similar to the logic above, by traversing the inversion table right-to-left, the RTL minima correspond exactly to the indices where $s_k$ achieves a new minimum.

  1. Initialize $\text{min$_s$} = \infty$ and an empty list.

  2. Traverse $k$ backwards from $N$ to 1::

     1. If $s_k<\text{min$_s$}$, add $k$ to the list and update $\text{min$_s$}=s_k$.

Exercise 7.2

Let $m$ be the number of cycles in the permutation and denote by $l_k$ the length of the $k$th cycle. The number of ways to write the sample permutation in cycle notation is $m! \prod_{k=1}^m l_k$.

For the sample permutation in Figure 7.1, we’ve $4!\times6 \times6\times2\times1=1728$ equivalent ways to write it down.

Exercise 7.3

There are $\binom{2N}{N}((N-1)!)^2/2$ permutations of $2N$ elements having exactly two cycles, each of length $N$.

There are $\binom{2N}{N}N!/2^N=(2N-1)!!$ permutations of $2N$ elements having exactly $N$ cycles, each of length 2. Notice that we must divide by $2^N$, since for a given representation all other possible ways of "flipping" elements in those $N$ cycles are duplicates.

Exercise 7.4

We must maximize the product from Exercise 7.2 subject to the constraint $\sum_{k=1}^m l_k = N$. The formula depends on the number of cycles and the product of their lengths. If we increase $m$ then we reduce the lengths and vice versa. Nonetheless, the contribution of $m$ is more important, as it grows factorially.

Let’s assume that we start with an identity permutation with $m=N$. This results in $N!$ equivalent representations. Can we maximize this number? If we set only one cycle to length 2 and keep the others at 1, then we get $(N-1)!2<N!$ for $N>2$. It turns out that we cannot attain a better result.

Therefore, the identity permutation has the greatest number of different representations with cycles. For the trivial edge cases of $N=1$ and $N=2$, all permutations have the exact same number of representations.

Exercise 7.5

The Python 3 program below implements the task in $\Theta(N^2)$ time.

def nis(p):
    """Computes the number of increasing subsequences in a given permutation."""
    n = len(p)
    s = [0] * n
    for i in range(n - 1, -1, -1):
        s[i] = 1
        for j in range(i + 1, n):
            if p[j] > p[i]:
                s[i] += s[j]
    return sum(s) + 1

if __name__ == '__main__':
    p = [9, 14, 4, 1, 12, 2, 10, 13, 5, 6, 11, 3, 8, 15, 7]
    print(nis(p))

It outputs 232 for the sample permutation from the book.

The example in the book is wrong. The reported errata only covers two problematic entries, but evidently there are more.

Exercise 7.6 🌟

This exercise introduces the probability integral transform, which is fundamental in simulation (generating samples from any continuous distribution using uniform random numbers) and in goodness‑of‑fit testing (the transformed samples should behave like a uniform sample).

Since $F$ is strictly increasing for all practical purposes, we’ve

$$a_1 < a_2 < a_3 \quad \Longleftrightarrow \quad F(a_1) < F(a_2) < F(a_3).$$

By the probability integral transform, $U_i = F(a_i)$ are independent and identically distributed (i.i.d.) uniform on $[0,1]$. For i.i.d. uniform random variables, all $3!$ orderings are equally likely by symmetry, because the joint density is symmetric. Hence,

$$\Pr\{a_1 < a_2 < a_3\} = \Pr\{U_1 < U_2 < U_3\} = \frac{1}{3!}.$$

Observe that we can easily change the relational operator, for example, from < to > and still get the same outcome. Furthermore, for $N$ i.i.d. continuous random variables, the probability of any fixed strict ordering is $1/N!$.

Exercise 7.7

$$\bold{11} \space \bold{12} \space 3 \space 4 \space 1 \space 9 \space 5 \space \bold{13} \space 8 \space \bold{15}\space 7\space 10\space 6\space 2 \space 14$$

Cycle leaders are shown in bold letters. Apparently, they’re left-to-right maxima.

Exercise 7.8

The Python 3 script below implements the original left-to-right minima based variant.

def to_foata(p):
    n = len(p)
    visited = [False] * n
    cycles = []

    for i in range(n):
        if not visited[i]:
            cycle = []
            j = i
            while not visited[j]:
                visited[j] = True
                cycle.append(p[j])
                j = p[j] - 1
            # Rotate so that minimum is first
            idx = cycle.index(min(cycle))
            cycle = cycle[idx:] + cycle[:idx]
            cycles.append(cycle)

    cycles.sort(reverse=True)

    foata = []
    for c in cycles:
        foata.extend(c)
    return foata

def from_foata(f):
    n = len(f)
    # Find left-to-right minima to locate cycle boundaries
    boundaries = [0]
    current_min = f[0]
    for i in range(1, n):
        if f[i] < current_min:
            boundaries.append(i)
            current_min = f[i]
    boundaries.append(n)

    cycles = []
    for k in range(len(boundaries) - 1):
        cycles.append(f[boundaries[k]:boundaries[k + 1]])

    # Build the permutation mapping from cycles (min-first form)
    p = [0] * n
    for cycle in cycles:
        for j in range(len(cycle) - 1):
            p[cycle[j] - 1] = cycle[j + 1]
        p[cycle[-1] - 1] = cycle[0]
    return p

if __name__ == "__main__":
    p = [9, 14, 4, 1, 12, 2, 10, 13, 5, 6, 11, 3, 8, 15, 7]
    print("Original permutation:", p)
    f = to_foata(p)
    print("Foata’s representation:", f)
    recovered = from_foata(f)
    print("Recovered permutation:", recovered)

Exercise 7.9 🌟

This exercise introduces a sophisticated tree based data structure called Fenwick tree.

For computing the inversion table corresponding to a given permutation, we scan the permutation left to right, maintaining a Fenwick tree over the values $1 \ldots N$. When we encounter the value $p_i$, we query how many values greater than $p_i$ have already been seen: that count is exactly $q_i$. Then we mark $p_i$ as seen. The usage of the Fenwick tree is important to attain an efficient linearithmic algorithm, as it natively supports range sums. Recall that marking $p_i$ as seen is nothing else than setting 1 for that position in the range. A naive approach would result in quadratic performance.

For computing the permutation corresponding to a given inversion table, we follow the algorithm from the book and process the entries from right to left ($i=N..1$). We maintain an array of “empty slots” that is represented as a Fenwick tree having 1 at each position that is still free. To set $p_i$ to be the $(q_i+1)$th largest of the integers not yet used, we binary search on the Fenwick tree’s prefix sums to find the smallest position $k$ such that the number of free slots up to $k$ is $i-q_i$. Then we mark that slot as occupied (set Fenwick tree at $k$ to 0).

The previous algorithm uses binary search with embedded computations of prefix sums. This achieves a near optimal performance $\Theta(N \log^2 N)$. It’s possible to leverage an optimization technique called binary lifting to reduce it to $\Theta(N \log N)$. This actually boils down to "walking" the Fenwick tree, as it stores partial sums in powers of 2 (this is why it’s called a binary indexed tree). By examining the largest power of 2, subtracting it from $k$ if the sum is smaller, and narrowing the interval, we can resolve the exact index in $O(\log N)$ operations.

Exercise 7.10

A one-to-one correspondence between permutations and lists of $N$ integers $q_1q_2 \dots q_N$ with $0 ≤ q_i \le N-i$ is easy to establish. Given a permutation, its altered inversion table is such a list. The reconstruction algorithm proves the existence of the transformation in the opposite direction:

1. Create an array of $N$ empty slots.

2. Process the values from smallest to largest ($v=1..N$).

   1. Place $v$ into the $(q_v+1)$th available empty slot from the left.

   2. Mark the slot as occupied.

Observe that we can use the same Fenwick tree based approach, as in the previous exercise. At the start, we initialize it with 1s at all $N$ positions (representing empty slots). Using binary lifting we can find the next available free slot in $O(\log N)$ time.

Exercise 7.11

There are $\binom{N}{k}$ independent ways to pick the rows and columns for rooks. Let the sequence of selected columns be $c_1 c_2 \dotsc c_k$. For any such sequence, we have an additional $k!$ possibilities to place rooks in selected rows; $k$ choices for $c_1$, $k-1$ choices for $c_2$, and so on. A symmetrical argument applies for permuting rows. Therefore, multiplying these numbers together gives the total to be $\binom{N}{k}^2k!.$

Exercise 7.12

There are symmetries. The "above and left" gives the same number as "below and right" that equals $\text{inv}(p)$. Furthermore, the "above and right" gives the same number as "below and left" that equals $\binom{N}{2}-\text{inv}(p)$.

Exercise 7.13

An involution is its own inverse. Therefore, the original matrix (lattice representation) must equal its transpose. This is by definition a symmetric matrix.

Exercise 7.14

9,4,14,1,5,12,15,2,6,10,13,3,8,11,7
9,14,4,1,5,12,15,2,6,10,13,3,8,11,7
9,4,14,5,1,12,15,2,6,10,13,3,8,11,7
9,4,14,1,5,15,12,2,6,10,13,3,8,11,7
9,4,14,1,5,12,15,6,2,10,13,3,8,11,7

Exercise 7.15 🌟

This exercises augments the main text by characterizing the nodes in an HOT that correspond to rises, double rises, falls, and double falls in permutations.

Let $x,y,z$ be 3 consecutive values in a permutation. Looking at Figure 7.5, we can see that an inorder traversal of a HOT reproduces the underlying permutation. Now, based on relationships between these 3 values, we can decipher the required structural characterizations of properties of permutations:

• $x<y \implies x\overset{-}{\space}y$ (rise). Because $x$ is smaller it’s an ancestor of $y$. For the inorder traversal to visit $y$ immediately after $x$, $y$ cannot have a left child. On the other hand, $x$ must have a right child.

• $y>z \implies y\overset{+}{\space}z$ (fall). Because $z$ is smaller it’s an ancestor of $y$. For the inorder traversal to visit $z$ immediately after $y$, $y$ cannot have a right child. On the other hand, $z$ must have a left child.

• $x < y < z \implies x\overset{-}{\space}y\overset{-}{\space}z$ (double rise). $y$ cannot have a left child, but it does have a right child, since it’s an ancestor of $z$. Therefore, $y$ only has a right child.

• $x > y > z \implies x\overset{+}{\space}y\overset{+}{\space}z$ (double fall). $y$ cannot have a right child, but it does have a left child, since it’s an ancestor of $x$. Therefore, $y$ only has a left child.

Exercise 7.16 🌟

This exercise showcases the connections between the local conditions of permutations with the global structural properties of HOTs. Furthermore, it introduces the boxed operator of the symbolic method for labelled objects. As a matter of fact, this is exactly what the book uses for deriving the GF for HOTs without mentioning it explicitly.

We can count such alternating permutations thankfully to bijection with HOTs. There are two types of such permutations: down-up (starts with a fall) and up-down (starts with a rise). There is a simple one-to-one correspondence between them, so it’s enough to handle one group. It turns out that down-up permutations can be nicely described using the symbolic method.

Let’s tackle the case when $N$ is odd. This can be expressed via the symbolic method

$$\mathcal{A} = \mathcal{Z} + \mathcal{Z}^{\Box} \star \mathcal{A}^2,$$

where $\mathcal{A}$ is the class of odd-length down-up permutations represented as HOTs consisting of strictly degree 0 and degree 2 nodes. This can be seen by recalling that the inorder traversal of a HOT reestablishes the original permutation. Since we have a sequence starting with a fall, using the rules from the previous exercise, we can conclude that the border elements of a sequence must be leaves together with all the peaks. In the middle, we have valleys.

In a HOT, the root must always be the absolute minimum value. To capture this via the symbolic method, we must use a new operator, called the min-box product, that controls the relabeling process. The corresponding functional equation is

$$A'(z) = 1 + A(z)^2,$$

with the initial condition $A(0) = 0$. The solution is $A(z) = \tan(z)$.

To handle the case when $N$ is even, notice that the absolute minimum (taking up 1 node) must be the root. Picking any candidate splits the sequence into two down-up sequences of different parities (zero is regarded as even). This gives

$$\mathcal{B} = \epsilon + \mathcal{Z}^{\Box} \star (\mathcal{B} \star \mathcal{A}),$$

where $\mathcal{B}$ is the class of even-length down-up permutations represented as HOTs. The corresponding functional equation is

$$B'(z) = B(z) \cdot A(z)=B(z) \cdot \tan(z),$$

with the initial condition $B(0) = 1$. The solution is $B(z)=\sec(z)$.

Since the two cases are disjoint, the combined result is

$$\boxed{F(z)=2(A(z)+B(z))-1-z=2(\tan(z)+\sec(z))-1-z},$$

where $F(z)$ is the EGF for alternating permutations. The coefficients can be extracted by looking at the Taylor expansions of the constituent functions. Notice that we multiply by two to include the up-down permutations, too. Finally, because up-down and down-up permutations are indistinguishable for lengths 0 and 1, multiplying by 2 overcounts them, hence, we must subtract extra terms.

Exercise 7.17

There is only one permutation (shown in Figure 7.5) associated with the given HOT, unlike BSTs (see Exercise 7.14).

Exercise 7.18

We just need to tweak a bit the symbolic method expression from Exercise 7.16 to include nodes with a single child (either left or right). This gives

$$\mathcal{K} = \mathcal{Z} + \mathcal{Z}^{\Box} \star (2\mathcal{K}+\mathcal{K}^2).$$

The corresponding functional equation is

$$K'(z)=1+2K(z)+K(z)^2,$$

with the initial condition $K(0) = 0$.

Exercise 7.19

Let $\mathcal{P}$ be the set of all permutations. For each permutation $p$, $\text{BST}(p)$ represents the corresponding BST built from $p$. Recall that multiple permutations may result in the same BST. Observe that the length of the given permutation determines the size of the associated BST. This gives

$$\begin{align*} C(z) &= \sum_{p \in \mathcal{P}} \text{ipl}(\text{BST}(p)) \frac{z^{|p|}}{|p|!} \\ &= \sum_{p_L \in \mathcal{P}} \sum_{p_R \in \mathcal{P}} \binom{|p_L| + |p_R|}{|p_L|} \Big( \text{ipl}(\text{BST}(p_L)) + \text{ipl}(\text{BST}(p_R)) + |p_L| + |p_R| \Big) \frac{z^{|p_L| + |p_R| + 1}}{(|p_L| + |p_R| + 1)!}. \end{align*}$$

The binomial convolution is fully justified, because even though the left and right subtrees are split based on the value of the root (first element in $p$), they maintain their relative order. The number of ways to interleave those two subsequences, without impacting the final tree, is exactly driven by the binomial coefficient. This becomes clearer by changing perspectives via lattice representation of permutations, more specifically looking at Figure 7.4. As stated in the book:

Note that many permutations might correspond to the same binary search tree: interchanging columns corresponding to a node above and a node below any node will change the permutation, not the tree.

The pivot is the root of the BST (first element in the permutation). Everything above and below of it are elements comprising the subtrees. Now, the number of ways to change columns for those elements is exactly dictated by the binomial coefficient.

Differentiating both sides of the equation, as was done in the book for HOTs, we get

$$C'(z) = \sum_{p_L \in \mathcal{P}} \sum_{p_R \in \mathcal{P}} \binom{|p_L| + |p_R|}{|p_L|} \Big( \text{ipl}(\text{BST}(p_L)) + \text{ipl}(\text{BST}(p_R)) + |p_L| + |p_R| \Big) \frac{z^{|p_L| + |p_R|}}{(|p_L| + |p_R|)!}.$$

We can use $H(z)$ to enumerate permutations, thus we get our differential equation

$$C'(z) = 2 C(z) H(z) + 2zH(z)H'(z)=\frac{2C(z)}{1-z}+\frac{2z}{(1-z)^3}.$$

Exercise 7.20

Employing Theorem 7.1 gives 1,576,575 permutations.

Exercise 7.21

From left to right, the frequencies are: 224, 1 and 896.

Exercise 7.22

The smallest number corresponds to a chain shape. The largest number corresponds to balanced trees. The reason is obvious, since in these trees subtree sizes drop rapidly.

Exercise 7.23

The arguments are literally the same as for the direct derivation of EGF, just that we are growing larger structures from the perspective of those larger structures. As a side note, we can immediately read out this recurrence from the differential equation for the involution EGF (presented in the book) by equating coefficients for $N$ on both sides of the equation.

Exercise 7.24

This is a variation of the previous exercise. We need to add cycles of length 3 into the picture, that entails a "double loop." This gives

$$b_{N+1}=b_N+Nb_{N-1}+N(N-1)b_{N-2}, \quad \text{ for $N>1$ with $b_0=b_1=1,b_2=2$}.$$

Exercise 7.25

Our generating function is

$$P_k(z) = \exp\left( \sum_{j=1}^k \frac{z^j}{j} \right).$$

The radius of convergence bound is (see Section 5.5 in the book)

$$[z^N]P_k(z) \le \underset{x \in (0,\infty)}{\min} \frac{P_k(x)}{x^N}\sim \underset{x \in (0,\infty)}{\min}\frac{\exp(x^k / k)}{x^N}.$$

Because we are looking for the behavior as $N \to \infty$, we expect the minimizing value of $x$ to grow large. For large $x$, the highest degree term in the polynomial exponent, $x^k/k$, completely dominates the lower-order terms.

To minimize this, we take the derivative of its logarithm with respect to $x$ and set it to zero

$$\begin{align*} \frac{d}{dx} \left( \frac{x^k}{k} - N \ln x \right) &= x^{k-1} - \frac{N}{x} = 0 \\ &\therefore x^k = N \implies x = N^{1/k}. \end{align*}$$

This gives

$$[z^N] P_k(z) \le \frac{P_k(N^{1/k})}{N^{N/k}} \sim \frac{e^{N/k}}{N^{N/k}}.$$

Using the Stirling's approximation $N! \sim (N/e)^N$, we get

$$N! [z^N] P_k(z) \sim (N/e)^N\left( \frac{e^{N/k}}{N^{N/k}} \right)= N^{N(1-1/k)} e^{-N(1-1/k)}.$$

Exercise 7.26

Actually, in the derivation of the EGF for the number of permutations that consist only of cycles of odd length (see Exercise 5.7), we had indirectly solved this problem, too. Thus, the EGF associated with the combinatorial class $P^*_{EVEN}$ is

$$P_{EVEN}^*(z) = \frac{1}{\sqrt{1-z^2}}.$$

The EGF for cycles of length divisible by $t$ is a simple generalization of even length cycles

$$C_t(z) = \sum_{k\ge1} \frac{z^{tk}}{tk}= \frac{1}{t} \sum_{k\ge1} \frac{(z^t)^k}{k} = \frac{1}{t} \ln \frac{1}{1-z^t}.$$

Exponentiate to find the EGF for the permutations

$$P_t^*(z) = \exp\left( \frac{1}{t} \ln \frac{1}{1-z^t} \right)=\frac{1}{(1-z^t)^{1/t}}.$$

Exercise 7.27

The book contains a typo, the starting point should be $(1 - z)D(z) = e^{-z}$.

Following the instruction from the book gives

$$\begin{align*} -D(z) + (1 - z)D'(z) &= -e^{-z} \\ -D(z) + (1 - z)D'(z) &= -(1 - z)D(z) \\ -D(z) + D'(z) - zD'(z) &= -D(z) + zD(z) \\ D'(z) - zD'(z) &= zD(z). \end{align*}$$

Let $d_N$ be the number of derangements of size $N$. Now, we extract the coefficient of $\frac{z^N}{N!}$ using Table 3.4 from the book

$$d_{N+1} - N d_N = N d_{N-1} \implies d_{N+1} = N (d_N + d_{N-1}) \qquad \text{for $N>1$},$$

with $d_1=0$ and $d_2=1$.

Exercise 7.28 🌟

This exercise showcases the limitations of symbolic systems, like SymPy to handle large problem sizes. It also demonstrates how to speed up the computation using dynamic programming.

Slow Symbolic Manipulation

The next Python 3 script uses SymPy to evaluate the EGF according to Table 7.5. Compare this method with the "manual" approach in Exercise 6.63. Nevertheless, don’t try to run this with $k>8$, as it requires an eternity to finish.

import sympy as sp
import math

def slow_restricted_permutations(k, max_N=20):
    """
    Prints a table of the number of permutations of N elements (N < max_N)
    that contain no cycles of length < k.
    """
    z = sp.Symbol('z')

    # Build the polynomial for the forbidden cycle lengths
    if k <= 1:
        forbidden_cycles = 0
    else:
        forbidden_cycles = sum((z ** j) / j for j in range(1, k))

    # Define the EGF: 1/(1-z) * exp(-forbidden_cycles)
    egf = sp.exp(-forbidden_cycles) / (1 - z)
    # Expand the Taylor series up to z^(max_N - 1)
    # .removeO() strips the Big-O term so we can easily extract coefficients
    series_expansion = egf.series(z, 0, max_N).removeO()

    print(f"--- Permutations with no cycles of length < {k} ---")
    print(f"{'N':<5} | {'Count'}")
    print("-" * 25)

    for n in range(1, max_N):
        z_n = series_expansion.coeff(z, n)
        count = int(z_n * math.factorial(n))
        print(f"{n:<5} | {count}")

# Print number of derangements.
slow_restricted_permutations(k=2, max_N=20)

Fast Combinatorial Approach

Instead of expanding the generating function, we can build the permutations directly via the proper combinatorial recurrence (see the previous exercise and Exercise 7.24). Let $p_N$ be the number of valid permutations of size $N$. Consider the element $N$. In a valid permutation, it must belong to a cycle of some length $j$. Because of our restriction, $k \le j \le N$. For any valid cycle length $j$:

• We need to pick $j-1$ other elements from the remaining $N-1$ elements. There are $\binom{N-1}{j-1}$ ways to do this.

• There are $(j-1)!$ ways to arrange these $j$ elements into a valid cycle.

• There are $p_{N-j}$ ways to arrange the remaining elements into valid cycles.

Multiplying these together and summing over all possible allowed cycle lengths $j$, gives our recurrence

$$p_N = \sum_{j=k}^N \binom{N-1}{j-1} (j-1)! \, p_{N-j}= \sum_{j=k}^N \frac{(N-1)!}{(N-j)!} p_{N-j}.$$

The next Python 3 script employs dynamic programming and achieves stunning performance compared to the previous variant. It handles much larger problem sizes than required for this exercise.

import math

def fast_restricted_permutations(k, max_N=20):
    """
    Computes the number of permutations of N elements with no cycles < k
    using a dynamic programming recurrence.
    """
    p = [0] * max_N

    # Base case: 1 way to form a valid permutation of size 0 (the empty set)
    if max_N > 0:
        p[0] = 1

    print(f"--- Permutations with no cycles of length < {k} ---")
    print(f"{'N':<5} | {'Count'}")
    print("-" * 25)

    for n in range(1, max_N):
        if n > 0:
            total = 0
            for j in range(k, n + 1):
                ways_to_form_cycle = math.factorial(n - 1) // math.factorial(n - j)
                total += ways_to_form_cycle * p[n - j]
            p[n] = total

        print(f"{n:<5} | {p[n]}")

# Try with "wild" arguments
fast_restricted_permutations(k=41, max_N=93)

Exercise 7.29 🌟

This exercise defines the concept of an arrangement and enumerates them.

There are $\binom{N}{k}$ ways to form a subset of size $k$ from $N$ elements. In an arrangement, the order matters, so we must multiply this by $k!$. In other words, the product is a total number of ways to form $k$-tuples from $N$ elements. Finally, we must sum over all $k$. We can translate this in terms of an EGF

$$A(z)=\sum_{N\ge 0}a_N\frac{z^N}{N!}=\sum_{N\ge 0} \left(\sum_{k=0}^N\binom{N}{k}k!\right)\frac{z^N}{N!}=\frac{e^z}{1-z}.$$

The RHS follows from the definition of a binomial sum of factorials (see Tables 3.3 and 3.4 in the book).

As a side note, we can also derive the EGF using the symbolic method. An arrangement takes $N$ labels and partitions them into two distinct groups:

• The primary ordered group defining the $k$-tuples of selected elements.

• The leftover unordered group consisting of unselected elements.

The number of ways to distribute $N$ labels onto $k$ items is $\binom{N}{k}$. Therefore,

$$\text{Arrangements} = \text{SEQ}(\mathcal{Z}) \star \text{SET}(\mathcal{Z}).$$

Exercise 7.30

The hint gives the answer, since there is a bijection between the original permutations and their complements. Furthermore, the number of rises in a permutation $p$ equals the number of falls in its complement $q$, and vice versa. For example, let $p_i<p_{i+1}$ be a rise in $p$. It becomes a fall in q, because

$$N+1-p_i>N+1-p_{i+1} \implies -p_i>-p_{i+1}.$$

Thankfully, due to this bijection, the average number of rises and the average number of falls must be identical. Their total is $N-1$, so the result follows immediately.

Exercise 7.31 🌟

The book’s claim of an "alternative direct" derivation isn't just euphemism for two pages of agonizing algebraic brute force. As shown below, things roll out pretty easily. The recurrence based approach, where the phrase from the book "leads directly" hides a full page of algebraic massage, isn’t at all an easy route.

$$\begin{align*} A(z,u) &= \sum_{p \in \mathcal{P}} u^{runs(p)}\frac{z^{|p|}}{|p|!} \\ &= 1 + \sum_{p \in \mathcal{P}} \Big( \text{runs}(p) u^{\text{runs}(p)} + (|p| + 1 - \text{runs}(p)) u^{\text{runs}(p)+1} \Big) \frac{z^{|p|+1}}{(|p|+1)!} \\ A_z(z,u) &= \sum_{p \in \mathcal{P}} \Big( \text{runs}(p) u^{\text{runs}(p)} + |p|u^{\text{runs}(p)+1} + u^{\text{runs}(p)+1} - \text{runs}(p) u^{\text{runs}(p)+1} \Big) \frac{z^{|p|}}{|p|!} \\ A_z(z,u) &= uA_u(z,u) + uzA_z(z,u) + uA(z,u) - u^2A_u(z,u) \\ A_z(z,u) &= \frac{1}{1-uz} \Big( uA(z,u) + u(1-u)A_u(z,u) \Big). \end{align*}$$

Exercise 7.32

$$\begin{align*} A(z,u) &= \frac{1-u}{1 - u e^{z(1-u)}} \\ &= (1-u) \sum_{m \ge 0} \left( u e^{z(1-u)} \right)^m \\ &= \sum_{m \ge 0} u^m (1-u) e^{zm(1-u)}. \end{align*}$$

We can also expand the exponential into a Taylor series

$$e^{zm(1-u)} = \sum_{N \ge 0} \frac{\big(zm(1-u)\big)^N}{N!} = \sum_{N \ge 0} \frac{z^N}{N!} m^N (1-u)^N.$$

Substitute that expanded exponential back into our equation

$$\begin{align*} A(z,u) &= \sum_{m \ge 0} u^m (1-u) \left( \sum_{N \ge 0} \frac{z^N}{N!} m^N (1-u)^N \right) \\ &= \sum_{N \ge 0} \frac{z^N}{N!} \underbrace{\left( \sum_{m \ge 0} m^N u^m (1-u)^{N+1} \right)}_{p_N(u)}. \end{align*}$$

Thus, $A_{Nk}=[u^k]p_N(u)$. Again, we continue expanding terms, this time the binomial

$$(1-u)^{N+1} = \sum_{j=0}^{N+1} \binom{N+1}{j} (-u)^j = \sum_{j \ge 0} (-1)^j \binom{N+1}{j} u^j.$$

Now substitute this back into our polynomial expression

$$p_N(u) = \left( \sum_{m \ge 0} m^N u^m \right) \left( \sum_{j \ge 0} (-1)^j \binom{N+1}{j} u^j \right).$$

The indices in the sums must satisfy the following equations:

$$m + j = k \implies m = k - j \\ m \ge 0 \implies k-j \ge 0 \implies j \le k.$$

Substituting $m=k-j$ we get

$$A_{Nk} = \sum_{0 \le j \le k} (-1)^j \binom{N+1}{j} (k-j)^N.$$

Exercise 7.33

The equation in this exercise is known as Worpitzky's identity. We’ve already done bulk of the work in the previous exercise. The idea is to start with $p_N(u)$ and run it in "reverse" (focus on the underlined part in the expression for $A(z,u)$).

$$\begin{align*} \sum_{x \ge 0} x^N u^x &= \frac{p_N(u)}{(1-u)^{N+1}} \\ &= \left( \sum_{k=1}^N A_{Nk} u^k \right) \frac{1}{(1-u)^{N+1}} \\ &= \left( \sum_{k=1}^N A_{Nk} u^k \right) \left( \sum_{j \ge 0} \binom{N+j}{N} u^j \right) . \end{align*}$$

Substituting $j=x-k$ into the binomial coefficient gives us the coefficient for the RHS

$$x^N = \sum_{k=1}^N A_{Nk} \binom{N+x-k}{N}.$$

A permutation with $k$ runs has $k-1$ falls and $N-k$ rises. Based on Exercise 7.30, the number of rises equals the number of falls in a complementary permutation, so

$$x^N = \sum_{k=1}^N A_{Nk} \binom{x +k-1}{N}.$$

Exercise 7.34

Instead of looking at a finished permutation and trying to find the subsequences, let's build the permutations around a specific increasing subsequence of length $k$. This is what the book’s hint is trying to tell. To force an increasing subsequence of length $k$ to exist in a permutation of length $N$, we make the following choices:

• Pick $k$ slots out of the $N$ available positions where our subsequence will live. There are $\binom{N}{k}$ ways to do this.

• Pick $k$ labels for our subsequence. There are $\binom{N}{k}$ ways to choose these values.

• Because this must be an increasing subsequence, the $k$ chosen labels must be placed into the $k$ chosen slots in exactly one specific order (sorted from smallest to largest).

• We have $N-k$ leftover labels and $N-k$ leftover slots. We can arrange these however we want. There are $(N-k)!$ ways to place them.

Multiplying these choices together and simplifying, we get

$$S_{Nk} =\binom{N}{k} \binom{N}{k} (N-k)!= N!\binom{N}{k} \frac{1}{k!}.$$

Summing $S_{Nk}$ over all $k$ we get $S_N$

$$S_N = N! \sum_{k=0}^N \binom{N}{k} \frac{1}{k!}.$$

Exercise 7.35

In the previous exercise, we’ve already found the total number of increasing subsequences of length $k$ across all permutations of length $N$.

Now, we plug this directly into the definition of an exponential CGF

$$C_k(z) = \sum_{N \ge k} S_{Nk} \frac{z^N}{N!} = \sum_{N \ge k} \left( N! \binom{N}{k} \frac{1}{k!} \right) \frac{z^N}{N!}= \frac{1}{k!} \sum_{N \ge k} \binom{N}{k} z^N= \frac{z^k}{k! (1 - z)^{k+1}}.$$

From Exercise 4.4 we get that $S_{Nk}/N!\sim \frac{N^k}{(k!)^2}$.

Exercise 7.36

Combining the formula for the grand total (see the book) with the one from the previous exercise, we get

$$C_{\ge 3}(z) = \frac{1}{1-z} \exp\left( \frac{z}{1-z} \right) - \left( \frac{1}{1-z} + \frac{z}{(1-z)^2} + \frac{z^2}{2(1-z)^3} \right).$$

Observe that the average number asymptotically doesn’t depend on polynomial terms stemming from the short subsequences. This is expected, since for large $N$, extremely small sequences are asymptotically negligible, although their numbers can be significant in an absolute sense. Therefore, the estimate from Theorem 7.6 still applies.

Exercise 7.37

According to Theorem 7.7, the average number of all mentioned node types is $\approx N/3$. The expected total storage cost is the sum of the expected costs of each node type. Therefore, the storage requirement is $\sim (c_0+c_1+c_2)N/3$.

Exercise 7.38

This is a corollary of the proof given in Exercise 7.30. Namely, peaks in the original permutation turns into valleys in the complement, and vice versa. So, due to this bijection, valleys and peaks have the same distribution for random permutations.

As Anscombe's quartet demonstrates, it would be a blunder to quickly jumpt to a conclusion about identical distributions of parameters purely based on equality of their averages and/or variances. Proving a bijection is one reliable way to establish distributional alignment.

Exercise 7.39

Based on the corollary of Theorem 6.7, the average number of leaves in a random binary Catalan tree is $\sim N/4$. Exercise 6.40 shows that the average number of unary nodes in a random binary Catalan tree is $\sim 2N/4=N/2$. Therefore, the average number of binary nodes is also $\sim N/4$, so the storage requirement is $\sim (c_0+2c_1+c_2)N/4$.

Exercise 7.40 🌟

This exercise illuminates the bridge between continuous random variables and discrete permutations. It once again emphasizes the benefits of associating discrete structures to corresponding continuous models.

Rises and falls depend solely on relative of order of values in a sequence. Thus, a sequence of $N$ random real numbers between 0 and 1 (uniformly and independently generated) may be regarded as a random permutation of $N$ elements. Based on the Theorem 7.7 from the book, in a random permutation of $N$ elements, the average numbers of double rises and double falls are $\sim N/6$ each.

Let $X_1, X_2, \dots, X_N$ be a sequence of independent, uniformly distributed continuous random variables on the interval $[0, 1]$. A double fall occurs starting at index $i$ if

$$X_i > X_{i+1} > X_{i+2}.$$

Because these variables are continuous and independent, the probability of any two being exactly equal is zero. Therefore, any specific triplet $(X_i, X_{i+1}, X_{i+2})$ must fall into one of $3! = 6$ possible strict orderings. By symmetry, since they are drawn from the exact same uniform distribution, every single one of those 6 orderings is equally likely. Only exactly one of those 6 orderings is a strictly descending sequence. Therefore, the probability of a double fall occurring at any specific index $i$ is exactly 1/6.

Let $B_i$ be a Bernoulli random variable, with success probability $p=1/6$, indicating if there is a double fall starting at index $i$. There are $N-2$ possible starting positions, so the total expectation for the number of double falls is $(N-2)/6$ (due to linearity of expectations). The number of double rises follows by symmetry. This concludes the continuous-model proof of the above asymptotic result.

Exercise 7.41

There are multiple issues with this exercise. First, it has nothing to do with Exercise 6.18 (Kraft's equality). Second, the differential equation contains an error, a missing $u$. Finally, the denominator of the closed-form solution is permuted. All these are corrected below.

We apply the symbolic method for labelled objects with parameters. We must mark any root that has a right-child (either right-branching node and/or binary node in an HOT). This gives (notice the usage of the boxed operator, see Exercise 7.16)

$$\mathcal{K}=Z+\mathcal{Z}^{\Box}\star\mathcal{K}+u\mathcal{Z}^{\Box}\star\mathcal{K}+u\mathcal{Z}^{\Box}\star\mathcal{K}^2.$$

Differentiating both sides of the corresponding functional equation with respect to $z$ (effectively taking out the root)

$$K_z(z,u)=1+(1+u)K(z,u)+uK^2(z,u).$$

Recall, that the boxed product is translated into an integral over $z$. Differentiation "annihilates" integration.

Let $K=K(z,u)$ be an abbreviated form for the EGF. We need to integrate

$$\frac{dK}{(1+K)(1+uK)} = dz.$$

Using partial fractions

$$\begin{align*} \frac{1}{1-u} \int \left( \frac{1}{1+K} - \frac{u}{1+uK} \right) dK &= \int dz \\ \frac{1}{1-u} \left( \ln(1+K) - \ln(1+uK) \right) &= z + C. \end{align*}$$

Since an empty tree has size 0, $K(0,u) = 0$, which means $C = 0$. Thus,

$$\ln \left( \frac{1+K}{1+uK} \right) = z(1-u) \implies \frac{1+K}{1+uK} = e^{z(1-u)} \implies \boxed{K(z,u) = \frac{1 - e^{(u-1)z}}{e^{(u-1)z} - u}}.$$

It’s easy to verify that the formula is correct by computing $A(z,u) = 1 + uK(z,u)$.

Exercise 7.42

To have one inversion, exactly one pair of neighboring elements must be swapped. There are $N-1$ such candidate pairs.

To have two inversions, exactly two pairs must swapped, which can happen in $\binom{N-1}{2}$ ways. But for neighboring pairs the order of swaps also matters. This adds $N-2$ additional choices. So, the total is $\binom{N-1}{2}+(N-2)$.

For three inversions, we can select 3 pairs, but for neighboring pairs the order matters. Furthermore, if we have a neighboring triplet, then the order of swaps of the first and third pairs also matters. Besides, we can also pick pairs of elements at distance 2. For example, $a,b,c$ turned into $c,b,a$ produces 3 inversions. Combined this gives

$$\binom{N-1}{3}+(N-2)(N-3)+(N-3)+(N-2)=\binom{N-1}{3}+(N-2)^2+N-3.$$

Exercise 7.43

The next snippet is an expanded version of Program 7.2 from the book to also produce the inversion table $q$.

int[] q = new int[N]; // assume q[0] = 0
for (int i = 1; i < N; i++) {
   int c = 0;
   for (int j = i; j >= 1 && a[j - 1] > a[j]; j--) {
      c++;
      exch(a, j, j - 1);
   }
   q[i] = c;
}

Exercise 7.44

We can virtually follow the same combinatorial reasoning from the book (see the direct solution with CGFs) to derive the recurrence. The base cases are $p_{00}=1$ and $p_{Nk}=0$ for $k < 0$ or $k>\binom{N}{2}$. Otherwise,

$$p_{Nk}=\frac{1}{N}\sum_{0 \le j < N} p_{(N-1)(k-j)}.$$

Exercise 7.45 🌟

This exercise augments the methodology introduced in Section 6.9 pertaining to additive parameters for trees. It allows us to derive CGFs purely in combinatorial fashion without solving tedious recurrences and ODEs.

From Table 7.5 in the book, the EGF for involutions is $I(z) = \exp\left(z + \frac{z^2}{2}\right).$

Every inversion $(i, j)$ in an involution can be uniquely classified as either an internal inversion (where $i$ and $j$ belong to the same 2-cycle) or a cross-inversion (where $i$ and $j$ belong to different cycles). Since expectation is linear, we can calculate the toll (see below) of each cycle configuration independently and sum them.

To find the CGF $C(z)$, we use the framework of additive parameters over sets: we isolate the specific cycle components that interact to create inversions, specify a toll function $E(z)$, multiply by the standard EGF kernel component $\frac{z^k}{k!}$, and then multiply the result by $I(z)$. Notice that we work at the level of cycles and let the machinery of GFs handle the translation of costs in terms of element wise inversions. We all the time operate at the same abstraction level, where cycles are the basic ingredients.

Internal Inversions (1 cycle of size 2)

Every 2-cycle creates exactly 1 internal inversion. Therefore, $E_1(z)=z^2/2$.

Cross-Inversions (One 1-cycle, One 2-cycle)

Suppose an inversion is formed by interactions between a 1-cycle and a 2-cycle. Suppose we have 3 elements (1, 2, 3). Cycles (1, 3)(2) yield the permutation 3, 2, 1. There are 2 cross-inversions. 1 is inverted relative to 2 and 2 is inverted relative to 3. Therefore, $E_2(z)= 2 \cdot \frac{z^3}{3!} =\frac{z^3}{3}$.

Cross-Inversions (Two 2-cycles)

Suppose we have 4 elements (1, 2, 3, 4). We know each 2-cycle inherently contains exactly 1 internal inversion. Therefore, any configuration of two 2-cycles will always have exactly 2 internal inversions. We can find the cross-inversions by looking at the total inversions of the sub-permutations:

• Cycles (1, 4)(2, 3) yield the permutation 4, 3, 2, 1. This has 4 cross-inversions. Elements 2 and 3 are inverted relative to 4, and 1 is inverted relative to 2 and 3. Again, we don't care about total number of inversions; we’re counting purely inversions crossing the borders.

• Cycles (1, 3)(2, 4) yields the permutation 3, 4, 1, 2. This has 2 cross-inversions. 1 is inverted relative to 4 and 2 is inverted relative to 3. These are the only pairs crossing the borders.

Therefore, $E_3(z)=6z^4/4!=z^4/4$.

Total Cost and Average

By the fundamental rules of additive parameters over sets, the total CGF is simply the sum of all the isolated toll-generating components, multiplied by the counting function $I(z)$. This gives

$$C(z) =(E_1(z)+E_2(z)+E_3(z))I(z)= \left( \frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} \right) I(z).$$

The average number of inversions in an involution is

$$\begin{align*} \frac{N! [z^N] C(z) }{N! [z^N] I(z) } &= \frac{ \frac{1}{2} [z^{N-2}] I(z) + \frac{1}{3} [z^{N-3}] I(z) + \frac{1}{4} [z^{N-4}] I(z) }{[z^N] I(z)} \\ &= \frac{N(N-1)}{2} \frac{I_{N-2}}{I_N} + \frac{N(N-1)(N-2)}{3} \frac{I_{N-3}}{I_N} + \frac{N(N-1)(N-2)(N-3)}{4} \frac{I_{N-4}}{I_N} \\ &\sim \frac{N^2}{4}. \end{align*}$$

The last line follows from the known ratio for the number of involutions

$$I_{N-k} / I_N \sim N^{-k/2}.$$

Even though involutions are a highly restricted, symmetric subset of permutations (composed entirely of 1-cycles and 2-cycles), they are just as hard a nut to crack for insertion sort as unrestricted permutations!

Exercise 7.46 🌟

This exercise illustrates the finite calculus in action.

We proceed to prove by induction on $k$ that $I(N,k)=N!\,p_{Nk}$ is a fixed polynomial in $N$ for any fixed $k$, when $N > k$. Definitely this covers the phrase "for sufficiently large $N$."

The base case $k=0$ is satisfied, since only the identity permutation has no inversions, so $I(N,0)=1$ for all $N$. This is a fixed polynomial.

For the inductive step, assume that $I(N,i)$ is a fixed polynomial in $N$ for all fixed $i<k$, when $N > i$. We use the standard "largest" construction for inversion numbers. Placing $N$ in a position that creates $j$ new inversions ($0\le j\le N-1$) and adding the inversions of the smaller permutation gives (see also Exercise 7.44)

$$I(N,k)=\sum_{j=0}^{\min(N-1,k)} I(N-1,k-j).$$

Observe that the sum cannot have more than $k$ summands. Let’s pull out the first term $j=0$ and "move" it to the LHS

$$I(N, k) - I(N-1, k) = \sum_{j=1}^{k} I(N-1, k-j).$$

$k$ is fixed and by the inductive hypothesis all subordinate items are fixed polynomials on the RHS, hence the whole sum is also a fixed polynomial. By the standard properties of the finite difference operator (see the remark below), we can conclude that $I(N,k)=N!p_{Nk}$ is a fixed polynomial in $N$ for any fixed $k$ when $N$ is large enough.

Any standard polynomial of degree $d$ can be rewritten as a linear combination of falling factorials up to degree $d$ (using Stirling numbers of the second kind). The "anti-difference" (which is just a finite sum) perfectly mimics continuous integration and gives back the original sequence:

$\sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C.$

Exercise 7.47

Observe that the identity permutation, regard it as a sorted sequence of numbers from 1 to $2N$, has 0 inversions. It’s lattice path is exactly that "down-right-down-right..." diagonal. Any departure from this ideal line, either going above or below, means that some larger numbers were skipped during the traversal. Thus, cells between the actual path and the main diagonal denote inversions.

Exercise 7.48 🌟

This exercise demonstrates how combinatorial ideas may be nicely translated into the language of the symbolic method.

The book contains an error, $P(z,u)$ is OBGF rather than EBGF. In other words, the kernel is simply $z^{|p|}$.

To prove this combinatorially, we just need to verify two things: that paths can be concatenated perfectly, and that the inversions add up cleanly without any "cross-contamination."

The Consequence of a Diagonal Touch

What does it actually mean when a lattice path touches the main diagonal at some point $(k, k)$? If the path hits $(k, k)$, it means we have taken exactly $k$ Right steps and $k$ Down steps. Consequently, the first $2k$ values (the numbers $1, 2, \dots, 2k$) have perfectly filled exactly $k$ Odd indices and $k$ Even indices. Because we process values in strictly increasing order, the path after $(k,k)$ will purely consist of the values $2k+1, \dots, 2N$.

The Additivity of Inversions

Can an element placed after the diagonal touch form an inversion with an element placed before the diagonal touch? The answer is no! Therefore, no "cross-contamination" may occur. All values placed after the touch are strictly larger than all values placed before the touch.

Therefore, if a path splits at the diagonal into Path $A$ and Path $B$, the total number of inversions is strictly additive

$$\text{inv}(A \Join B) = \text{inv}(A) + \text{inv}(B).$$

Furthermore, because the values are perfectly partitioned into these blocks, there are no binomial choices to make about relabeling paths. This means we are strictly in the realm of OGFs. The paths concatenate directly like blocks. This additive nature of the problem permits clean decomposition into subproblems (reminiscent of the divide-and-conquer paradigm); recall the difficulties in analyzing tree height, where this wasn’t possible.

Proving the First Equation

Let $\mathcal{P}$ be the class of all 2-ordered permutation lattice paths. Let $\mathcal{Q}$ be the analogous class for paths that never touch the diagonal except at the endpoints. Every single lattice path that returns to the diagonal can be uniquely decomposed into a sequence of these basic $\mathcal{Q}$ paths, just by chopping it at every single diagonal touch. This gives

$$\mathcal{P} = \text{SEQ}(\mathcal{Q}) \implies P(z,u) = \frac{1}{1 - Q(z,u)}.$$

Proving the Second Equation

The exact same logic applies to the second equation, just restricted to a subset of the space. Thus,

$$\mathcal{S} = \text{SEQ}(\mathcal{T}) \implies S(z,u) = \frac{1}{1 - T(z,u)}.$$

Exercise 7.49 🌟

This exercise definitely showcases the benefits of having multiple representations (in this case lattice paths). By purely geometric reasoning we can establish profoundly new relationships between GFs that would otherwise be extremely hard to attain.

The two equations in this exercise are direct translations of the physical geometry of the lattice paths (see also the previous two exercises).

The Elevation Principle

We can build path $\mathcal{T}$ of length $N$ from path $\mathcal{S}$ of length $N-1$ by

$$\mathcal{T}=\text{Right} \Join \mathcal{S} \Join \text{Down}.$$

Notice that $\mathcal{T}$ only touches the diagonal at the endpoints. Geometrically, this envelope (Right...Down) shifts the entire inner path $\mathcal{S}$ up and right by one grid unit. The initial move adds 1 inversion together with the extra $N-1$ inversions due to moving away $\mathcal{S}$ from the main diagonal.

Recall the definition of the BGF: the exponent of $u$ designates the number of inversions, whilst $z$ reflects the size. To encode the increase +1 in inversions over the whole length of the current path $\mathcal{S}$, we simply embellish the GF by passing $uz$ instead of $z$ into $S(z,u).$ In the same manner, the first Right move increases both the number of inversions and size by one, hence we just multiply the GF by $uz$. Therefore, $T(z, u) = uz S(uz, u)$.

The Asymmetry Principle

A path $\mathcal{Q}$ may be above or below the diagonal except at the endpoints. A path $\mathcal{T}$ is restricted to always stay above the diagonal except at the endpoints. Let path $\mathcal{T}^-$ represent the mirrored path $\mathcal{T}$ around the diagonal (stays always below it except at the endpoints), where all Right moves were replaced by Down moves, and vice versa. Clearly, $\mathcal{Q}=\mathcal{T}+\mathcal{T^-}$. Just by looking at Figure 7.10, we see that the number of inversions in $\mathcal{T}$ and $\mathcal{T}^-$ are generally different.

The path of the identity permutation starts with a Down move. Thus, the mirrored path $\mathcal{T}^-$ is more aligned with this reference path than $\mathcal{T}$, since it also starts with a Down move. The initial difference of -1 is maintained throughout the whole length of $\mathcal{T}$. Therefore, $\mathcal{T}$ has $N$ more inversions than $\mathcal{T}^-$. This gives

$$T^-_N(u) = u^{-N} T_N(u) \implies T^-(z,u)=T(z/u,u) \implies T^-(uz,u)=T(z,u).$$

Therefore,

$$Q(z,u) = T(z,u) + T\left(\frac{z}{u}, u\right) \implies Q(uz, u) = T(uz, u) + T(z, u).$$

Exercise 7.50

$$\begin{align*} S(z, u) &= \frac{1}{1 – T(z, u)} \\ &= S(z,u)T(z,u)+1 \\ &= uzS(z,u)S(uz,u)+1. \end{align*}$$

$$\begin{align*} P(z, u) &= \frac{1}{1 – Q(z, u)} \\ &= Q(z,u)P(z,u)+1 \\ &= (T(z, u) + T(z/u, u))P(z,u) + 1 \\ &= (uzS(uz,u)+zS(z,u))P(z,u) + 1. \end{align*}$$

Exercise 7.51

The book contains an error, we’re looking for $P_u(z,1)$ instead of $P_u(1,z)$.

Let $W = \sqrt{1 - 4z}$. We know our base functions are:

• $S(z, 1) = \frac{1 - W}{2z}$, since path $\mathcal{S}$ reflects the lattice path of a binary tree. This provides the identity $1 - 2zS(z, 1) = W$.

• $P(z, 1) = \frac{1}{W}$.

To save space, let write $S$ for $S(z,1)$ and $S_*$ for $S_*(z,1)$.

$$\begin{align*} S(z, u) &= uz S(z, u)S(uz, u) + 1 \\ \hline S_u(z, u) &= z S(z,u)S(uz,u) + uz S_u(z,u)S(uz,u) + uz S(z,u) \left[ z S_z(uz,u) + S_u(uz,u) \right] \\ \hline S_u &= z S^2 + z S_u S + z S (z S_z + S_u) && \text{(evaluate at $u=1$)} \\ &= z S^2 + 2z S S_u + z^2 S S_z \\ &\therefore S_u (1 - 2z S) = z S^2 + z^2 S S_z \implies S_u W = z S^2 + z^2 S S_z. \end{align*}$$

We can also find $S_z = \frac{S^2}{W}$ by differentiating $S(z,1) = zS(z,1)^2 + 1$ with respect to $z$.

$$\begin{align*} P(z, u) &= (uz S(uz, u) + z S(z, u)) P(z, u) + 1 \\ \hline P_u(z, u) &= \left[ z S(uz, u) + u z (z S_z(uz, u) + S_u(uz, u)) + z S_u(z, u) \right] P(z,u) + \left[ u z S(uz, u) + z S(z, u) \right] P_u(z, u) \\ \hline P_u &= \left[ z S + z^2 S_z + 2z S_u \right] P + 2z S P_u && \text{(evaluate at $u=1$)} \\ &= \frac{1}{W^2} \left[ z S + z^2 S_z + 2z S_u \right]. \end{align*}$$

Now we just evaluate the three terms in that bracket using $zS = \frac{1-W}{2}$ and our derivatives from step 1. The goal is to express everything on the RHS in terms of $W$. It helps to remember that $1-W^2 = 4z$. We’ve

$$\begin{align*} z S &= \frac{1-W}{2} \\ \hline z^2 S_z &= z^2 \frac{S^2}{W} \\ &= \frac{(zS)^2}{W} \\ &= \frac{(\frac{1-W}{2})^2}{W} \\ &= \frac{1 - 2W + W^2}{4W} \\ \hline 2z S_u &= 2z \frac{z S^2 (1+W)}{2 W^2} \\ &= \frac{(zS)^2 (1+W)}{W^2} \\ &= \frac{(\frac{1-W}{2})^2 (1+W)}{W^2} \\ &= \frac{(1-W)^2(1+W)}{4W^2} \\ &= \frac{(1-W)(1-W^2)}{4W^2} \\ &= \frac{(1-W)(4z)}{4W^2} \\ &= \frac{z(1-W)}{W^2}. \end{align*}$$

The biggest simplification happens in

$$\begin{align*} zS + z^2 S_z &= \frac{1-W}{2} + \frac{1 - 2W + (1-4z)}{4W} \\ &= \frac{2W - 2W^2}{4W} + \frac{2 - 2W - 4z}{4W} \\ &= \frac{2 - 2W^2 - 4z}{4W} \\ &= \frac{4z}{4W} = \frac{z}{W}. \end{align*}$$

Plugging everything back into the formula for $P_u$ and further simplifying, we get

$$P_u(z,1) = \frac{z}{W^4}= \frac{z}{(1-4z)^2}.$$

Exercise 7.52

A 3-ordered permutation of total length $3N$ consists of exactly 3 perfectly sorted sublists, each of length $N$, interleaved together. Because the individual sublists are already sorted, inversions can only occur between elements of two different sublists. There are 3 pairs of such sublists.

Let $X_{ij}$ be a random variable for the number of inversions between 2 ordered sublists. We already know the expectation of this variable from Theorem 7.9. By the linearity of expectation, we have

$$E[X_{12}+X_{13}+X_{23}]= E[X_{12}]+E[X_{13}]+E[X_{23}]\sim\sqrt{\frac{\pi}{48}} (3N)^{3/2}.$$

Wikipedia has a detailed coverage of shellsort including answers related to this exercise.

Exercise 7.53

Let $C_N$ be the average number of comparisons to sort an array of size $N$ using this hybrid method. The divide-and-conquer recurrence is (see also Theorem 7.9 from the book)

$$C_N \sim 2C_{N/2} + \sqrt{\frac{\pi}{128}} N^{3/2}.$$

According to Theorem 2.5 from the book, the performance is commensurate with the driving function $\sim c_1\sqrt{\frac{\pi}{128}} N^{3/2}$ (see Exercise 2.68 for the value of $c_1$). We know that the quicksort implementation from Chapter 1 takes about $\sim 2N \ln N$ comparisons. The objective is to find the threshold value below which the hybrid algorithm is faster. This gives

$$(2+\sqrt 2)\sqrt{\frac{\pi N}{128}}< 2 \ln N \implies N \lesssim 550.$$

This is significantly larger than the one from Exercise 1.19. At any rate, the exact threshold isn’t that important. The key takeaway is that specialized sorting algorithms may play an important optimization role despite being asymptotically inferior compared to mainstream algorithms.

Exercise 7.54

The recurrence directly follows from Theorem 7.10 in the book and Exercise 3.71

$$p_{Nk} = \frac{N-1}{N} p_{(N-1)k} + \frac{1}{N} p_{(N-1)(k-1)},$$

with the boundary conditions:

• $p_{00}=1$,

• $p_{Nk}=0$ for $k > N$,

• $p_{N0}=0$ for $N>0$.

Exercise 7.55

The counting GF is $C_N(u)=N!P_N(u)=\sum_k \left[ N \atop k \right] u^k$. Let’s employ the double counting technique (see Exercise 2.34). The first way is

$$C_N'(u) = \frac{d}{du} \sum_k \left[ N \atop k \right] u^k = \sum_k k \left[ N \atop k \right] u^{k-1} \implies C_N'(1) = \sum_k k \left[ N \atop k \right].$$

By Theorem 7.10, we also know that

$$\ln(C_N(u)) = \ln(u) + \ln(u+1) + \ln(u+2) + \dots + \ln(u+N-1).$$

Taking derivates of both sides gives

$$\frac{C_N'(u)}{C_N(u)} = \frac{1}{u} + \frac{1}{u+1} + \frac{1}{u+2} + \dots + \frac{1}{u+N-1}.$$

Recall that $C_N(1)=N!P_N(1)=N!$ and the RHS evaluated at $u=1$ is simply $H_N$. Equating both ways of computing $C'_N(1)$ gives

$$\sum_k k \left[ N \atop k \right] =N!H_N.$$

Exercise 7.56

Assume for convenience that $N$ is even and that the array is a random permutation of $N$ elements. Let $i$ be the index of the smallest number and $j$ be the index of the second smallest number. Initialize these indices based on the relative order of $a_0$ and $a_1$. The algorithm proceeds as follows:

1. The loop variable $k=2..N-1$ points to the current pair of elements. It increases in increments of 2.

   1. If $a_k < a_{k+1}$ then

      1. If $a_k< a_i$ then

         1. If $a_{k+1}<a_i$ then

            1. Set $j=k+1$

         2. Else

            1. Set $j=i$

         3. Set $i=k$

      2. Else If $a_k<a_j$ then

         1. Set $j=k$

   2. Else perform the above checks just with $k$ and $k+1$ swapped.

The above algorithm performs exactly $\frac{3}{2}N$ comparisons in every single case.

The index variable $i$ is set $H_N$ times, the average number of left-to-right minima in a permutation. The index variable $j$ is always updated whenever $i$ is altered, plus anytime a candidate for the second smallest appears. In a random permutation, the probability that the $k$th element is the minimum of the first $k$ elements is $1/k$. The book explains the reason. But the probability that it’s exactly the second smallest of the first $k$ elements is also $1/k$ using the same argumentation. Therefore, the total number of updates to index variables is $\sim 3H_N$.

The presented solution and analysis is fully aligned with the theme of the book. Nonetheless, the asymptotically optimal solution is based on a tournament tree.

Exercise 7.57

Assume that an “exchange” costs twice as much as a “record access.” We need to find the threshold value for which selection sort is a better choice than insertion sort. The model is based on statements about these sorting methods from the book

$$\frac{N^2}{2}+200N <\frac{N^2}{4}+200\frac{N^2}{4} \implies N \ge 5.$$

Exercise 7.58

We need to find the threshold value for which selection sort is a better choice than quicksort. The model is based on statements about these sorting methods from the book

$$\frac{N^2}{2}+200N <2N\ln N+200\frac{N}{3}\ln N \implies 22 \le N \le 433.$$

Exercise 7.59

The asymptotic behavior is identical to the standard array version given in Theorem 7.11 from the book. Without swaps, the remaining sequence is intrinsically uniformly random, although not independent from the starting permutation. Therefore, computing the average still works via linearity of expectation, but finding the variance requires advanced methods.

To understand where dependence comes from, take a look at all permutations of $N=3$ elements and count the number of index updates for each of them (in both passes). The marginal probability that the second pass requires 1 update is 1/2. Nonetheless, if we know that we had 2 index updates in the first pass (these are associated with permutations (2, 1, 3), (3, 1, 2) and (2, 3, 1)) then $\Pr\{Pass_2 = 1 \mid Pass_1 = 2\} = 2/3 \neq 1/2$.

The permutation pattern concept sheds more light onto why those leftover permutations may be regarded as uniformly random.

Exercise 7.60

Let $V$ be the total volume of input data. Since there are $N$ records, and each record has $N$ words, the total input data is $V=N^2$.

Notice that just reading the input requires $\Omega(V)$ time. Interestingly, selection sort turns out to have an optimal performance, since its number of compares and total data movement cost are both $O(V)$. Recall that only the first word is used as a key. All in all, it definitely has a total of $\Theta(V)=\Theta(N^2)$ runtime.

Observe also that no other enlisted sorting method achieves this goal, as their data movement costs are higher than linear in terms of input size.

The moral of the story is that, depending on the context, even a generally "inferior" algorithm may become an undisputed winner. This is why machine and inputs models are crucial in evaluating algorithms.

Exercise 7.61

Similarly as in Theorem 7.13 from the book, we want to get

$$[u^jz^N] \frac{e^{(u-1)z^k/k}}{1-z}=[u^jz^N] \frac{e^{u z^k / k} e^{-z^k / k}}{1-z}.$$

Let’s first extract the component depending on $u$, whilst treating the rest as "constant." This gives

$$[u^j] e^{u z^k / k} = \frac{(z^k / k)^j}{j!} = \frac{z^{kj}}{j! k^j}.$$

Substitute this back into our initial formula, and our extraction problem becomes

$$[z^N] \left( \frac{z^{kj}}{j! k^j} \frac{e^{-z^k/k}}{1-z} \right)=\frac{1}{j! k^j} [z^{N-kj}] \frac{e^{-z^k/k}}{1-z}.$$

The Taylor series for $e^{-z^k/k}$ is

$$\sum_{m\ge0} \frac{(-1)^m z^{km}}{m! k^m}.$$

The division by $1-z$ means that we must take a partial sum of this expansion upto $N-kj$. For a fixed $k$ and $j$, as $N \to \infty$ this is equivalent to

$$\lim_{N \to \infty} [z^{N-kj}] \frac{e^{-z^k/k}}{1-z} = \sum_{m\ge0} \frac{(-1/k)^m}{m!}=e^{-1/k}.$$

If we plug this asymptotic limit back into the expression from the beginning, we get

$$\text{Probability} \sim \frac{1}{j! k^j} e^{-1/k} = \frac{e^{-\lambda} \lambda^j}{j!}.$$

Setting $\lambda=1$ we get the result from Theorem 7.13 in the book.

Exercise 7.62

The question, translated into the language of cycles in a permutation of length 100, is "What is the probability that a random permutation of length 100 contains no cycles of length strictly greater than 50?"

If $k > 50$, it is physically impossible to have more than one cycle of length $k$ when $N=100$. Theorem 7.13 in the book already provides the average number of such cycles; here, it’s the same as the probability of having a cycle of that length. Since the events are mutually exclusive, the total probability of having any cycle larger than 50 is just the sum of the individual probabilities. Taking the complementary event, we get

$$P\{\text{max cycle} \le 50\} = 1 - \sum_{k=51}^{100} \frac{1}{k} \approx 30\%.$$

Exercise 7.63

Let $b(p)$ be the number of executions of the instruction k=p[k], where $p$ denotes a random permutation of length $N$.

In the derivation that follows, $u$ acts as the size variable (hence taking the derivative with respect to $u$ to pull down the $N$ at the end), and $z$ as the cost. This is in contrary with the book’s usual notational convention, but favored by Knuth.

Let $B_N(z)$ be the PGF for $b(p)$ on permutations of size $N$. Obviously, $B_0(z)=1$. We can decompose a random permutation $p$ based on the position of its leader (following Knuth's paper cited in the book related to this exercise). The first cycle always starts at index 1, so one leader is predefined. It helps to look at Figure 7.1 (and Foata's correspondence) to recognize leaders of cycles. Let’s focus on this particular leader, to understand the decomposition.

Because 1 is guaranteed to be the minimum of its cycle, the inner loop will fully traverse its cycle of length $k$. Consequently, the target instruction runs $k-1$ times. For all the other members of the same cycle, the loop will abort earlier, effectively simulating the algorithm on the remaining elements. They physically split into two independent permutations $q$ (the rest of the cycle) and $r$ (the elements outside the cycle): one of size $k-1$ and one of size $N-k$, respectively. Because the other leaders are equally likely to be anywhere, this yields the recursive relationship (see also Exercise 7.59)

$$b(p) = b(q) + b(r) + k-1.$$

Translating this into generating functions, we get the recurrence

$$B_N(z) = \frac{1}{N} \sum_{k=0}^{N-1} z^k B_k(z) B_{N-1-k}(z).$$

Multiplying both sides by $N u^{N-1}$ and sum over all $N \ge 1$ gives

$$\sum_{N \ge 1} N B_N(z) u^{N-1} = \sum_{N \ge 1} \left( \sum_{k=0}^{N-1} (z^k B_k(z)) B_{N-1-k}(z) \right) u^{N-1}= \sum_{N \ge 0} \left( \sum_{k=0}^{N} (z^k B_k(z)) B_{N-k}(z) \right) u^{N}.$$

This factors perfectly into our target functional equation

$$B_u(z, u) = B(z, zu)B(z, u).$$

Computing the mean and variance proceeds similarly to the steps laid out in Exercise 3.67 and will not be repeated here. The mean and variance are:

$$\mu_N = (N+1)H_N - N \\[0.3cm] \sigma_N^2 = 2N^2 + 4N - (N+1)^2 H_N^{(2)} - (N+1)H_N.$$

Exercise 7.64

The inner loop of Program 7.6 scans the array from left-to-right and bubbles up the current maximum in the corresponding subarray to its final position. This shifts the entries in the inversion sequence one position to the left and decreases their values by one.

If the next scan is done in the opposite direction, the current minimum is bubbled to its final position at the front. Because this displaces elements to the right, it shifts their entries in the inversion sequence one position to the right. However, because the sweeping element is smaller than the displaced elements, their inversion values stay the same (they do not increase), while the minimum element's inversion count drops to zero.

Wikipedia has more details about this bidirectional bubble sort.

Exercise 7.65

The formula for extracting coefficients is based on a similar approach as for the longest cycle calculation from the book (see also Theorem 7.2)

$$E[S_N] = \sum_{k=0}^{N-1} \Pr\{S_N > k\} = \sum_{k=0}^{N-1} [z^N] \frac{1}{1-z} \exp\left( - \sum_{i=1}^k \frac{z^i}{i} \right),$$

where $S_N$ denotes a random variable for the length of the shortest cycle in a random permutation of $N$ elements. The Python script below "implements" this formula.

import sympy as sp

def expected_shortest_cycle(max_n):
    z = sp.Symbol('z')

    for N in range(1, max_n):
        expected_value = 0
        # Pre-calculate the 1/(1-z) series truncated to O(z^(N+1))
        gf = (1 / (1 - z)).series(z, 0, N + 1).removeO()

        for k in range(N):
            exponent = -sum(z ** i / i for i in range(1, k + 1))
            exp_term = sp.exp(exponent).series(z, 0, N + 1).removeO()
            full_series = (gf * exp_term).expand()
            prob = full_series.coeff(z, N)
            expected_value += prob

        print(f"N = {N}: {expected_value} (approx {float(expected_value):.4f})")

expected_shortest_cycle(10)

It outputs

N = 1: 1 (approx 1.0000)
N = 2: 3/2 (approx 1.5000)
N = 3: 5/3 (approx 1.6667)
N = 4: 15/8 (approx 1.8750)
N = 5: 59/30 (approx 1.9667)
N = 6: 301/144 (approx 2.0903)
N = 7: 1819/840 (approx 2.1655)
N = 8: 12943/5760 (approx 2.2470)
N = 9: 104663/45360 (approx 2.3074)

If you multiply each entry by $N!$, then you get back the OEIS sequence A028417.