TAOCP 7.2.2.1 Exercise 213

Section 7.2.2.1: Dancing Links

Exercise 213. [M21] [M21] If $\pi$ and $\pi'$ are two partitions of the same set, say that $\pi < \pi'$ if the restricted growth string of $\pi$ is lexicographically less than the restricted growth string

of $\pi'$. Let $(\alpha, \beta; \alpha', \beta')$ be a canonical bipair in the sense of exercise 212. Also let $\pi$ be a partition of the items such that $\alpha$ and $\beta$ are two of its parts, and let $\pi'$ be the same partition but with $\alpha'$ and $\beta'$ substituted. Is $\pi < \pi'$?

Verified: no
Solve time: 2m12s

Solution

Let the items be linearly ordered and let the restricted growth string of a partition be defined in the standard way: scanning items in increasing order, each item receives the index of the block in which it lies, where blocks are numbered by first occurrence.

Let $(\alpha,\beta;\alpha',\beta')$ be a canonical bipair. Let $\pi$ be a partition containing blocks $\alpha$ and $\beta$, and let $\pi'$ be obtained from $\pi$ by replacing $\alpha,\beta$ with $\alpha',\beta'$.

Let $s$ be the smallest item occurring in any of $\alpha,\beta,\alpha',\beta'$. By condition (i) of canonicity, $s \in \alpha$ and $s \in \alpha'$. Since $s$ is the smallest item in the entire union, it is the first among all involved items in the linear order.

In the construction of restricted growth strings, the block containing $s$ is the first block created in both $\pi$ and $\pi'$. Hence the entry corresponding to $s$ in the restricted growth strings of $\pi$ and $\pi'$ is the same, equal to $1$.

Consider the set difference between $\alpha$ and $\alpha'$. Since $\alpha$ is lexicographically smaller than $\alpha'$, there exists an item $x \in \alpha \triangle \alpha'$ such that $x$ is the smallest element where the sorted characteristic sequences of $\alpha$ and $\alpha'$ differ. In particular, $x \in \alpha$ and $x \notin \alpha'$, and every item smaller than $x$ belongs to both or neither of $\alpha$ and $\alpha'$ in the same way.

For every item $y < x$, the membership of $y$ in $\alpha$ or $\alpha'$ agrees in a way that preserves the same block structure between $\pi$ and $\pi'$, because all items $< s$ are irrelevant and $s$ lies in both $\alpha$ and $\alpha'$, fixing the first block. Therefore the restricted growth strings of $\pi$ and $\pi'$ coincide up to position $x-1$.

At item $x$, in $\pi$ we have $x \in \alpha$, hence $x$ is assigned the block index $1$, since $\alpha$ is the block created at the first occurrence $s$. In $\pi'$, the item $x \notin \alpha'$, so $x$ belongs either to $\beta'$ or to a block disjoint from $\alpha'$. By construction, $\beta'$ does not contain $s$, hence its first element is strictly larger than $s$, so its block index in the restricted growth string is strictly greater than $1$. Therefore the entry of the restricted growth string of $\pi$ at position $x$ is $1$, while the corresponding entry for $\pi'$ is greater than $1$.

Thus the first position where the two restricted growth strings differ is $x$, and at this position the string for $\pi$ is smaller. Hence the restricted growth string of $\pi$ is lexicographically smaller than that of $\pi'$.

This completes the proof. ∎