Beginner's question about loops.

[George Tsavdaris]

I wonder how someone can calculate how many times a specific type of loop will be executed.

For example the following one in pseudo-code:

Code: Select all

K=0
for a = 1 to 15 
 for b = a+1 to 16 
  for c = b+1 to 17 
   for d = c+1 to 18 
    for e = d+1 to 19 
     for f = e+1 to 20 
        K=K+1
next
next
....etc.

So how much will be the K?
Or with other words how many times the commands in the inner loop will be executed? I'm not speaking about the number, this is nothing, as one can run the code and find it out, but i'm speaking about the proof/formula that it will have that value.

I have found it to be 38760.
Which "happens" to be equal to (20 , 6). Where (20 , 6) to be the binomial coefficient or the number of combinations of 6 numbers out of 20.
That means (20 , 6) = 20!/(6!·14!)

So how one can prove the above loop will be executed (20,6) times?
►►►►►►►►►►►►►►►►►►►►►►►►

And to generalize it:
If you have a loop of:

Code: Select all

for a1 = 1 to T 
 for a2 = a1+1 to T+1 
  for a3 = a2+1 to T+2 
   ..........................
     .......................... 
       for an =  a(n-1)+1 to T+n-1   
next
next
....etc.

Then how many times the commands at the inner loop will be executed?

[Tord Romstad]

I wonder how someone can calculate how many times a specific type of loop will be executed.

For example the following one in pseudo-code:

Code: Select all

K=0
for a = 1 to 15 
 for b = a+1 to 16 
  for c = b+1 to 17 
   for d = c+1 to 18 
    for e = d+1 to 19 
     for f = e+1 to 20 
        K=K+1
next
next
....etc.

So how much will be the K?
Or with other words how many times the commands in the inner loop will be executed? I'm not speaking about the number, this is nothing, as one can run the code and find it out, but i'm speaking about the proof/formula that it will have that value.

I have found it to be 38760.
Which "happens" to be equal to (20 , 6). Where (20 , 6) to be the binomial coefficient or the number of combinations of 6 numbers out of 20.
That means (20 , 6) = 20!/(6!·14!)

So how one can prove the above loop will be executed (20,6) times?
►►►►►►►►►►►►►►►►►►►►►►►►

And to generalize it:
If you have a loop of:

Code: Select all

for a1 = 1 to T 
 for a2 = a1+1 to T+1 
  for a3 = a2+1 to T+2 
   ..........................
     .......................... 
       for an =  a(n-1)+1 to T+n-1   
next
next
....etc.

Then how many times the commands at the inner loop will be executed?

The pattern you observed for T = 16 and n=6 is true in general: The answer is the binomial coefficient (T+n-1, n). This is fairly easy to see by a simple combinatorial argument: What you do in the nested loops above is to count the number of sets of integers a1, a2, ... an such that:

Code: Select all

1 <= a1 <= T, a1 < a2 <= T+1, a2 < a3 <= T+2, ...

The conditions ai <= T+i-1 are redundant for 1 <= i <= n-1, because they follow from ai < a(i+1) and an <= T+n-1. Therefore, the above can be rewritten as:

Code: Select all

1 <= a1 < a2 < a3 < ... < an <= T+n-1

The set of all such sequences is clearly exactly the same as the number of possible selections of n different numbers from the set {1, 2, ..., T+n-1}, which equals the binomial coefficient (T+n-1, n).

Tord