TAOCP 2.2.6 Exercise 7
Let T_k(n)=\#\{(i_1,\ldots,i_k):0\le i_k\le\cdots\le i_1\le n\}.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 7. [**] [M23] Find a general formula to allocate storage for the $k$-dimensional tetrahedral array A[i_1,i_2,\ldots,i_k], where $0 \le i_k \le \cdots \le i_2 \le i_1 \le n$.
Verified: no
Solve time: 36s
Let
$$ T_k(n)=#{(i_1,\ldots,i_k):0\le i_k\le\cdots\le i_1\le n}. $$
By the combinations-with-repetitions formula,
$$ T_k(n)=\binom{n+k}{k}. $$
If the elements of the tetrahedral array are stored in lexicographic order of the indices, the location of $A[i_1,\ldots,i_k]$ is obtained by counting all admissible index tuples that precede $(i_1,\ldots,i_k)$. The mixed-radix analogue for tetrahedral arrays is therefore
$$ \operatorname{LOC}(A[i_1,\ldots,i_k]) = \operatorname{LOC}(A[0,\ldots,0]) + \sum_{r=1}^{k} \binom{i_r+k-r}{,k-r+1,}. $$
Indeed, fixing $i_1,\ldots,i_{r-1}$ and replacing $i_r$ by a smaller value $t<i_r$, the remaining indices satisfy
$$ 0\le i_k\le\cdots\le i_{r+1}\le t, $$
hence there are
$$ T_{k-r}(t)=\binom{t+k-r}{k-r} $$
such completions. Summing over all $t<i_r$ gives
$$ \sum_{t=0}^{i_r-1}\binom{t+k-r}{k-r} = \binom{i_r+k-r}{k-r+1}, $$
by the hockey-stick identity. Adding the contributions for $r=1,\ldots,k$ yields the stated address formula.
Therefore the general allocation formula is
$$ \boxed{ \operatorname{LOC}(A[i_1,\ldots,i_k]) = \operatorname{LOC}(A[0,\ldots,0]) + \sum_{r=1}^{k} \binom{i_r+k-r}{,k-r+1,} }. $$
For $k=2$ this becomes
$$ \operatorname{LOC}(A[J,K]) = \operatorname{LOC}(A[0,0]) + \binom{J+1}{2} + K, $$
which is formula (9). ∎