counting the number of loop runs

I have the following loop structure:

for $i_1=1$ to $m$
for $i_2=i_1$ to $m$
$\vdots$
for $i_n=i_{n-1}$ to $m$

Of course, all indices $i_k$ are integers, and $m$ and $n$ are also positive integers.

How can I count how many times the inner loop will run?

-
Can you do it for $n=1$? Can you use the answer for $n=1$ to get an answer for $n=2$? Can you use the answer for $n=2$ to get an answer for $n=3$? Can you find a pattern in the answers? – Gerry Myerson Oct 5 '12 at 5:27

Each loop is characterized by the $n$-tuple $(i_k)_{1\leq k\leq n}$, where $$1\leq i_1\leq i_2\leq\ldots\leq i_n\leq m\ .$$ It can be encoded as a sequence of $n$ zeros and $m-1$ ones in the following way: The $n$ zeros symbolize the $n$ $i$'s in increasing order. Write $i_1-1$ ones in front of the first zero, for $2\leq k\leq n$ write $i_k-i_{k-1}$ ones between the $(k-1)$th and the $k$th zero, and write $m-i_n$ ones after the last zero.

Now there are $\displaystyle{{n+m-1 \choose m-1}}$ such sequences.

-
Very nice. Note that the list of $i$'s can be found by taking for every $0$ in the sequence one more than the sum of the digits to its left (which might explain the particular way $0$ and $1$ are used). The "one more" here is due to the fact that the loops start at $1$ rather than at the (for me) more usual starting value $0$ (and then of course ending just before $m$). – Marc van Leeuwen Oct 5 '12 at 9:30

Since the loop variables are called $i_1,\ldots,i_n$, there are clearly $n$ nested loops.

This is probably not what you were after, but it is the answer, as per "What You Ask For Is What You Get". (Well actually you asked "How can I count ..."; I'll spare you the answer to that.)

-

This is a problem in which it really helps to look at some small examples or to start with the simplest version and work up (or both!). The simplest version is $n=0$, which isn’t very interesting. The next simplest is $n=1$, which is also pretty trivial. The first interesting case is $n=2$, but it turns out to be helpful to have looked at some variants of the $n=1$ case first.

Suppose that there’s one instruction $I$ inside the nest of loops. If there are no loops, $I$ is executed once. If there’s one loop running from $i$ to $m$, $I$ is executed $m-i+1$ times. In particular, if there’s one loop running from $1$ to $m$, it’s executed $m$ times.

Now suppose that there are two loops. The inner loop runs from $i_1$ to $m$ for each value of $i_1$ from $1$ to $m$. Thus, $I$ is executed $m-i_1+1$ times for each value of $i_1$ from $1$ to $m$, for a total of

$$\sum_{i_1=1}^m(m-i_1+1)=\sum_{k=1}^mk=\binom{m+1}2\;.$$

How many times is $I$ executed if the outer loop runs from $j$ to $m$ instead of from $1$ to $m$? That would be

$$\sum_{i_1=j}^m(m-i_1+1)=\sum_{k=1}^{m-j+1}k=\binom{m-j+2}2\;.$$

Now suppose that there are three loops. The second loop runs from $i_1$ to $m$ for each value of $i_1$ from $1$ to $m$, so $I$ is executed a grand total of

$$\sum_{i_1=1}^m\binom{m-i_1+2}2\tag{1}$$ times. You’ve probably seen an identity involving binomial coefficents that will let you simplify $(1)$ to a single binomial coefficient.

You may now already be able to generalize to get the result for arbitrary $n$; if not, try repeating the argument to derive the result for $n=4$. Once you have the result, you’ll need to prove it by induction.

-