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?
$\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.

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 $\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 7. 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}$