Results 1 to 7 of 7

Math Help - Number of Iterations

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    3

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    Quote Originally Posted by aarnold View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member yeKciM's Avatar
    Joined
    Jul 2010
    Posts
    456
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by aarnold View Post
    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}

    <br />
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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by aarnold View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Sep 2010
    Posts
    185
    Thanks
    13
    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}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: February 15th 2011, 04:13 PM
  2. Numerical Iterations -- Predictions to achieve convergence
    Posted in the Advanced Math Topics Forum
    Replies: 8
    Last Post: July 28th 2010, 03:04 AM
  3. Iterations ??
    Posted in the Calculus Forum
    Replies: 1
    Last Post: June 10th 2010, 03:34 AM
  4. Contraction Mapping/ Fixed Points/ Iterations
    Posted in the Calculus Forum
    Replies: 0
    Last Post: April 18th 2010, 01:21 PM
  5. Contraction mapping iterations
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 17th 2010, 05:34 AM

Search Tags


/mathhelpforum @mathhelpforum