TAOCP 5.1.4 Exercise 7

Let $P$ be a tableau of shape $(m_1,m_2,\dots,m_k)$, with $m_1 \ge m_2 \ge \dots \ge m_k > 0$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.4: Tableaux and Involutions

Exercise 7. [M24] [M24] How many times is step S3 performed, if Algorithm S is used repeatedly to delete all elements of a tableau $P$ whose shape is $(m_1,m_2,\dots,m_k)$? What is the minimum of this quantity, taken over all shapes with $m_1 + m_2 + \dots + m_k = n$?

Verified: no
Solve time: 42m04s

Solution

Let $P$ be a tableau of shape $(m_1,m_2,\dots,m_k)$, with $m_1 \ge m_2 \ge \dots \ge m_k > 0$. Let $n = m_1 + \cdots + m_k$ be the total number of elements. We analyze the number of times step S3 of Algorithm S is performed when all elements of $P$ are deleted, and we determine the minimum of this quantity over all shapes of size $n$.

1. Number of times S3 is executed for a single deletion

Recall that Algorithm S deletes the entries of a tableau repeatedly by applying Algorithm D to the bottom row, removing one element at a time. Step S3 of Algorithm S corresponds to step D2 in Algorithm D, where we increment the column index $j$ while comparing the current element in the row with the element being deleted, until the correct position is found.

Consider the deletion of the bottom-right element of the tableau. This element is in row $i$ and column $m_i$. In the deletion process, it may "bump" elements along a path through the tableau. We observe the following:

  • Each execution of step S3 corresponds precisely to a comparison along a row in Algorithm D.
  • When deleting all elements repeatedly, each element of the tableau is eventually deleted exactly once.
  • The number of times step S3 is executed for a given element equals its current column index at the moment it is deleted.

To justify this, we use induction on the number of elements remaining in the tableau.

Base case: If a row has only one element, deleting it executes S3 exactly once, which equals the column index.

Inductive step: Suppose the claim holds for tableaux with fewer than $n$ elements. Let $x$ be an element to delete from row $i$, column $j$. When $x$ is deleted:

  1. It is compared with elements along the row until it reaches its final position. This requires exactly $j$ executions of step S3, because the algorithm moves from left to right until the comparison fails.
  2. Any "bumped" elements move to higher rows, but by the inductive hypothesis, the total number of S3 executions caused by these elements equals the sum of their column indices in their original positions.

Therefore, summing over all deletions, each element contributes exactly its column index to the total number of S3 executions.

2. Total number of S3 executions

Let row $i$ have $m_i$ elements in columns $1,2,\dots,m_i$. By the previous argument, each element in column $j$ contributes $j$ executions of step S3. Therefore, the total number of S3 executions is

$$ \sum_{i=1}^{k} \sum_{j=1}^{m_i} j = \sum_{i=1}^{k} \frac{m_i(m_i+1)}{2}. $$

This formula is exact for any tableau of shape $(m_1,\dots,m_k)$.

3. Minimizing the total over all shapes with $n$ elements

We now minimize

$$ F(m_1,\dots,m_k) = \sum_{i=1}^{k} \frac{m_i(m_i+1)}{2} $$

subject to

$$ m_1 \ge m_2 \ge \dots \ge m_k > 0, \quad m_1 + \cdots + m_k = n. $$

Observe that for any $a,b>0$:

$$ \frac{a(a+1)}{2} + \frac{b(b+1)}{2} > \frac{(a+b)(a+b+1)}{2}. $$

This inequality shows that splitting a row into two smaller rows increases the total sum. Equivalently, merging rows decreases the total sum. Hence, the minimum of $F$ is achieved when all row lengths are as small as possible, that is, $m_i = 1$ for all $i$, giving $k = n$ rows.

4. Minimal shape and minimal value

The minimal shape is therefore

$$ (1,1,\dots,1) \quad \text{(with $n$ rows of length $1$)}. $$

The total number of S3 executions in this case is

$$ \sum_{i=1}^{n} \frac{1\cdot 2}{2} = n. $$

5. Conclusion

For a tableau $P$ of shape $(m_1,\dots,m_k)$, the exact number of times step S3 is performed when all elements are deleted is

$$ \boxed{\sum_{i=1}^{k} \frac{m_i(m_i+1)}{2}}. $$

The minimal total number of S3 executions over all tableau shapes with $n$ elements is

$$ \boxed{n}, $$

achieved by the tableau of shape $(1,1,\dots,1)$.

∎