Number of Iterations

• Sep 15th 2010, 02:49 PM
aarnold
Number of Iterations
How many times does the innermost loop execute:

Code:

for k = 1 to n     for j = 1 to k         for i = 1 to j             #the inner loop         end for     end for end for
I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?
• Sep 15th 2010, 03:16 PM
yeKciM
Quote:

Originally Posted by aarnold
How many times does the innermost loop execute:

Code:

for k = 1 to n     for j = 1 to k         for i = 1 to j             #the inner loop         end for     end for end for
I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?

that can't be (n+2) or (n-1) iterations in that loop with "i" :D:D:D

i have question for you :D why don't compile this ? and is it ( k=1 ; k<= n or you need k<n ; k++ )

for n=2 there are 6 , for n=3 there is 18 , for n=4 there is 40 ... repetitions :D

lol for n = 50 there is 63 750 of executions of that loop :D
• Sep 15th 2010, 03:39 PM
aarnold
Hi, I'm assuming that I am calculating for k <= n.

A quick check with python gives the following results:

Code:

>>> def iterate(n):     c = 0     for k in range(1, n + 1):         for j in range(1, k + 1):             for i in range(1, j + 1):                 c = c + 1     print c   >>> iterate(1) 1 >>> iterate(2) 4 >>> iterate(3) 10 >>> iterate(4) 20 >>> iterate(5) 35 >>> iterate(6) 56
and here's Pascal's triangle:

Code:

          1         1    1       1    2    1       1  3  3  1     1  4  6  4  1     1  5  10  10  5  1   1  6  15 20  15 6 1
If the row and column's are 0-based, look at the n+2 row and the n-1 column and you get the number of iterations.

So if n = 1, look at row 3, column 0: 1
n = 2, look at row 4, column 1: 4
n = 3, row 5, column 2: 10

etc.

I determined this to be (n+2) choose (n-1).

However, I don't think this is a mathematical enough answer.
• Sep 15th 2010, 04:00 PM
yeKciM
hm...

Code:

cin>> n ; int iter = 0 ; for (int k = 1 ; k<= n ; k++ ) { for( int j= 1 ; j <= k ; j++ ) { for( int i =1 ; i< =j i ++ ) { iter++ ; cout << << "No." << iter << "." << i << endl;}}}
and get totally something else :D
• Sep 15th 2010, 04:16 PM
undefined
Quote:

Originally Posted by aarnold
How many times does the innermost loop execute:

Code:

for k = 1 to n     for j = 1 to k         for i = 1 to j             #the inner loop         end for     end for end for
I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?

$\displaystyle 1+2+3+...+n = t_n =$ nth triangle number $\displaystyle =\binom{n+1}{2}$

$\displaystyle t_1 + t_2 + t_3 + ... + t_n =$ nth tetrahedral number $\displaystyle =\binom{n+2}{3}$

The pattern continues. Notice that n+2-3 = n-1. (Combine this with the knowledge that $\displaystyle \binom{n}{k}=\binom{n}{n-k}$.)

You can justify the triangular number formula by considering the handshake problem; given a group of n people, if everyone shakes everyone else's hand, how many handshakes took place? So the first person shakes n-1 hands. Add to that n-2 for the second person -- because if you added n-1 you would re-count the handshake with the first person. So you get (n-1) + n + ... + 1, which is the (n-1)st triangle number.

We can generalize as follows: Consider a set of n points, n > 2, such that no three points are collinear. How many triangles can we form by choosing vertices from these n points? Start with one point, and ask how many triangles can form with it. You get the (n-2)nd triangle number. (Because you are choosing any two points out of the n-1 remaining points, which is a problem we just solved above.) For the next point you get the (n-3)rd triangle number, etc.

There may be a cleaner way to state it, but that at least does the job.
• Sep 16th 2010, 05:23 AM
CaptainBlack
Quote:

Originally Posted by aarnold
How many times does the innermost loop execute:

Code:

for k = 1 to n     for j = 1 to k         for i = 1 to j             #the inner loop         end for     end for end for
I did the first few by hand to see if I noticed anything.

Looking at Pascal's triangle I saw the numbers appear in the diagonal. Eventually I came up with the answer:

(n + 2) choose (n - 1)

But I don't know how I got there. Does this have anything to do with the Principle of Inclusion and Exclusion?

For any value of $\displaystyle $$j the inner loop executes \displaystyle$$ j$ times.

For any value of $\displaystyle $$k the inner look executes \displaystyle \sum_{j=1}^k j So the total number of executions of the inner code is \displaystyle \sum_{k=1}^n \left[\sum_{j=1}^k j\right] With a bit of jiggery-pokery this becomes: \displaystyle \dfrac{n(n+1)(n+2)}{6} CB • Sep 16th 2010, 06:54 AM MathoMan Here's that jiggery-pokery stuff: \displaystyle \sum_{k=1}^n \left[\sum_{j=1}^k j\right]=\sum_{k=1}^n\frac{k(k+1)}{2}=$$\displaystyle =\frac{1}{2}\left(\sum_{k=1}^n k^2+\sum_{k=1}^n k\right)=\frac{1}{2}\left(\frac{n(n+1)(2n+1)}{6}+\ frac{n(n+1)}{2}\right)=\dfrac{n(n+1)(n+2)}{6}$