Consider the following pseudocode segment: K := 0 for i_1 := 1 to n for i_2 :=…

Concept — counting the tuples a dependent loop nest visits. A loop nest in which every inner loop counts from 1 up to the current value of the loop immediately enclosing it runs its body once for each tuple of counter values that satisfies one long chain of inequalities. Counting non-increasing tuples of a fixed length drawn from a fixed value set is the classical multiset-counting problem: the number of ways to choose r items from t distinct types, with repetition allowed and order irrelevant, is given by the stars-and-bars identity C(t + r – 1, r).

Application to this loop nest.

1. K is set to 0 once and is incremented only at the innermost level, so the final value of K is exactly the number of times the innermost body executes.

2. The bounds give i1 ∈ [1, n], i2 ∈ [1, i1], …, im ∈ [1, im–1]. Each execution therefore corresponds to exactly one tuple (i1, i2, …, im) satisfying n ≥ i1 ≥ i2 ≥ … ≥ im ≥ 1.

3. Because the chain already forces the tuple into non-increasing order, the tuple is completely determined by which values from {1, 2, …, n} occur in it and how many times each occurs — that is, by a multiset of size m drawn from n types.

4. Apply the identity with t = n types and r = m items chosen: the number of such multisets is C(n + m – 1, m). Hence K = C(n + m – 1, m).

Cross-check with a small case. Take n = 3 and m = 2, so the nest is two loops deep. Counting by hand: i1 = 1 contributes 1 iteration, i1 = 2 contributes 2, and i1 = 3 contributes 3, giving 6 iterations in total. The four candidate expressions evaluate as follows.

Only C(n + m – 1, m) reproduces the hand count of 6. It also survives the degenerate check m = 1, where the single loop runs n times and C(n + 1 – 1, 1) = C(n, 1) = n.