Section 7.2.1.1: Generating All n-Tuples

Exercise 3. ▶ [M20] x 3. [M20] How many times does Algorithm M perform step M4?

Verified: yes
Solve time: 2m44s

The flaw in the previous solution is not in the identification of trailing maximal components, but in how step M4 is counted inside a single transition. Step M4 is not a simple “reset counter”, it is a repeated test of the condition $a_j = m_j - 1$, and in Algorithm M this test is executed once more on the first non-maximal position before control leaves the loop. That final failing evaluation is still an execution of M4 and must be counted.

We restart the counting from the structure of a single transition.

Consider a current tuple $a = (a_1,\dots,a_n)$ that is not the final tuple $(m_1-1,\dots,m_n-1)$. Let $t(a)$ be the number of trailing maximal components, meaning

$$ a_n = m_n - 1,; a_{n-1} = m_{n-1} - 1,; \dots,; a_{n-t+1} = m_{n-t+1} - 1, $$

and either $t=n$ or $a_{n-t} < m_{n-t} - 1$.

During the transition from $a$ to the next tuple, Algorithm M performs step M4 as follows. It checks indices from $n$ downward. For each of the $t(a)$ trailing maximal coordinates, the condition $a_j = m_j - 1$ is true, so M4 is executed once per index. After these resets, the algorithm reaches index $n-t(a)$ and performs one additional execution of M4 to test $a_{n-t(a)} = m_{n-t(a)} - 1$, which fails and terminates the loop.

Hence every non-terminal transition contributes exactly

$$ t(a) + 1 $$

executions of M4.

There are $N = \prod_{j=1}^n m_j$ tuples and $N-1$ transitions, so the total number of executions of M4 is

$$ \sum_{a \ne (m_1-1,\dots,m_n-1)} (t(a) + 1) = \sum_{a \ne \text{max}} t(a) + (N-1). $$

It remains to evaluate $\sum t(a)$. A tuple contributes $1$ to $t(a)$ for each suffix of maximal entries it has. Equivalently, for each $k \in {1,\dots,n}$, we count the tuples whose last $k$ coordinates are all maximal. The first $n-k$ coordinates are arbitrary, giving $\prod_{j=1}^{n-k} m_j$ choices. Excluding the single terminal tuple (which has no outgoing transition and contributes nothing), we obtain

$$ \sum_{a \ne \text{max}} t(a)

\sum_{k=1}^n \left(\prod_{j=1}^{n-k} m_j - 1\right). $$

Therefore the total number of executions of M4 is

$$ (N-1) + \sum_{k=1}^n \left(\prod_{j=1}^{n-k} m_j - 1\right), \quad \text{where } N = \prod_{j=1}^n m_j. $$

We can rewrite this in a slightly cleaner form by expanding the sum:

$$ \sum_{k=1}^n \prod_{j=1}^{n-k} m_j - n + (N-1). $$

Reindexing with $i = n-k$ gives

$$ \sum_{i=0}^{n-1} \prod_{j=1}^{i} m_j + N - n - 1, $$

with the convention that the empty product is $1$.

This corrects the systematic undercount in the original solution by restoring the missing final evaluation of M4 in every transition.