I'm programming a loop and I would like to know the loop size before executing the loop so I can display a nice progress bar for the user.
The loop will iterate over a set of $N$ elements, $S=|S_n, S_{n-1}, S_{n-2}, ... S_{0}|$. Every element will start with an initial positive integer value of $M$. In each loop iteration, $S_0$ will be decremented by 1. If $S_0 < 0$ then we set $S_0 = max(S_1 - 1, 0)$ and repeat the process for the next element $S_{i+1}$. An example:
For $N=1$ and $M=2$
- Iteration 1: $S = (2)$
- Iteration 2: $S = (1)$
- Iteration 3: $S = (0)$
For $N=2$ and $M=2$
- Iteration 1: $S = (2, 2)$
- Iteration 2: $S = (2, 1)$
- Iteration 3: $S = (2, 0)$
- Iteration 4: $S = (1, 1)$
- Iteration 5: $S = (1, 0)$
- Iteration 6: $S = (0, 0)$
For $N=3$ and $M=2$
- Iteration 1: $S = (2, 2, 2)$
- Iteration 2: $S = (2, 2, 1)$
- Iteration 3: $S = (2, 2, 0)$
- Iteration 4: $S = (2, 1, 1)$
- Iteration 5: $S = (2, 1, 0)$
- Iteration 6: $S = (2, 0, 0)$
- Iteration 7: $S = (1, 1, 1)$
- Iteration 8: $S = (1, 1, 0)$
- Iteration 9: $S = (1, 0, 0)$
- Iteration 10: $S = (0, 0, 0)$
I would like to know in advance the number of iterations. For $N=1$ iterations are just equal to $M + 1$. For $N=2$ the number of iterations will be $(M + 1) + M + (M - 1) + ... + 2 + 1$ which can also be written as $(M+1)(M+2)/2$. When $N=3$ however, I have calculated it to be $\sum{R_i}$ where:
$R_0 = (M + 1) + (M - 0) + (M - 1) + ... + 2 + 1$
$R_1 = (M - 0) + (M - 1) + (M - 2) + ... + 2 + 1$
$R_2 = (M - 1) + (M - 2) + (M - 3) + ... + 2 + 1$
$...$
But I have not been successful in obtaining a general and compact formula for any $N$ and $M$.
Thanks for your help
We must note the following two facts:
Theorem: the sequence $S$ of integers of length $N$ is always a non-increasing sequence, and all elements of $S$ are always between $0$ and $M$.
Proof: this is a simple loop invariant.
Theorem: for every non-increasing sequence $S$ of integers of length $N$ where all values are between $0$ and $M$, $S$ occurs at some point in the program.
Proof: this one is harder. We proceed by induction on $N$.
Clearly, the base case of $N = 0$ is trivial, since in this case the sequence is empty to begin with, which is the only sequence of length $0$.
Now, consider the case $N = k + 1$ where the proposition holds for $k$. We proceed by induction on $M$.
In the case that $M = 0$, we are done immediately since the sequence of all zeroes is the only one to be concerned about.
In the case $M = j + 1$, we consider the first element of $S$; call it $x$. If $x = M$, then we can get from $(M, M, ..., M)$ to $S$ by only modifying the last elements of the sequence, so this case follows from our $N$-inductive hypothesis. If $x < M$, then we can get from $(M, M, ..., M)$ to $(M, 0, ..., 0)$ through the above case, and from there get to $(j, j, ..., j)$ by going one more step. We can then get to $S$ through the $M$ inductive hypothesis.
So the set of sequence values we attain is exactly the set of nondecreasing sequences of $N$ integers with values between $0$ and $M$ of length $N$.
These sequences correspond in an obvious way with strictly decreasing sequences of $N$ integers with values between $0$ and $M + N - 1$, which in turn correspond to subsets of $\{0, ..., M + N - 1\}$ with $N$ elements. There are exactly $\binom{M + N}{N}$ of these.
Edit: it may not be totally obvious how nonincreasing sequences in $\{0, ..., M\}$ correspond with strictly decreasing sequences in $\{0, ..., M + N - 1\}$. The correspondence is: $x_1, ..., x_N$ corresponds to $x_1 + (N - 1), x_2 + (N - 2), ..., x_N - (N - N)$.
So the final answer is $\binom{M + N}{N} = \frac{(M+N)!}{M! N!}$.