Math Help - Number of Iterations

1. 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?

2. 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"

i have question for you 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

lol for n = 50 there is 63 750 of executions of that loop

3. 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.

4. 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

5. 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?
$1+2+3+...+n = t_n =$ nth triangle number $=\binom{n+1}{2}$

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

The pattern continues. Notice that n+2-3 = n-1. (Combine this with the knowledge that $\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.

6. 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 $j$ the inner loop executes $j$ times.

For any value of $k$ the inner look executes $\sum_{j=1}^k j$

So the total number of executions of the inner code is $\sum_{k=1}^n \left[\sum_{j=1}^k j\right]$

With a bit of jiggery-pokery this becomes: $\dfrac{n(n+1)(n+2)}{6}$

CB

7. Here's that jiggery-pokery stuff:
$\sum_{k=1}^n \left[\sum_{j=1}^k j\right]=\sum_{k=1}^n\frac{k(k+1)}{2}=$ $=\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}$