# A triple for-loop from our exam...

#### jflurrie

First of all, please move this thread if it is in totally wrong place.

Anyway, I took today in our university an exam in Discrete Mathematics. The question itself was easy and I know the answer too (by counting it with computer), but what is the formula to solve this? Here's the code as VBA code:

Code:
Sub forlooptask()
Dim i As Long, j As Long, k As Long, x As Long

For i = 1 To 200
For j = 1 To i - 1
For k = 1 To j
x = x + 1
Next k
Next j
Next i

Debug.Print x
End Sub
the result is 1333300. The question is: How does the equation for solving this go? Where does that 200 go to?

#### TKHunny

Onhan huonossa!

1) That j-loop is troublesome. First it does a brief descending count, from 1 to zero. THEN it starts a more expected path of growth. It's not wrong, per se. It just looks a little funny.

2) Why is 'x' not initialized? I guess VB doesn't mind, but I would onsider it bad form.

3) Formula for what? You want a brief, convenient expression to caclulate the total?

Other than that, it looks pretty straight-forward.

#### jflurrie

Onhan huonossa!

1) That j-loop is troublesome. First it does a brief descending count, from 1 to zero. THEN it starts a more expected path of growth. It's not wrong, per se. It just looks a little funny.

2) Why is 'x' not initialized? I guess VB doesn't mind, but I would onsider it bad form.

3) Formula for what? You want a brief, convenient expression to caclulate the total?

Other than that, it looks pretty straight-forward.
I could initialize that x to 0, but it wouldn't make difference. I just coded it quickly, the main thing here is that math problem. The exam paper itself has it like:

For i:=1 to 200 do
For j:=1 to i-1 do
For k:=1 to j do
Print "Hei"
How many times "Hei" is printed?

So the answer is 1333300, but how do I calculate that by numbers? I'm pretty sure it's about combinatory, but how?

#### HallsofIvy

MHF Helper
For k= 1 to j- 1
x= x+1
Next k

Just adds 1 to x j-1 times: the result is x+ j-1- it just adds j- 1 to x.

And it does that for j running form 1 to i-1: That is, we will have x+ 1+ 2+ 3+ ...+ i-2. it is well know that $$\displaystyle 1+ 2+ \cdot\cdot\cdot+ n= \frac{n(n+1)}{2}$$ so the result of the j loop will be x+ \frac{(i-1)i){2}[/tex]. (These are the "triangular numbers" 1, 3, 6, 10, ...)

Now, it does that for i going from i to 200 so it will be x+ 1+ 3+ 6... and the result will be x plus the sum of the first 199 (because it is "i-1", not "i" in the formula) triangular numbers.

To get those, look at $$\displaystyle \frac{i(i+1)}{2}= \frac{i^2+ i}{2}= \frac{n^2}{2}+ \frac{n}{2}$$.

$$\displaystyle \sum{i=1}^n \frac{i}{2}= \frac{1}\sum i$$ is easy- it is just 1/2 the sum above- $$\displaystyle \frac{n(n+1)}{4}$$.

And $$\displaystyle \sum{n^2}$$ is also well known: it is $$\displaystyle \frac{n(n+1)(2n+1)}{6}$$

I agree with TKHunny- it is peculiar that x is not initialized- without knowing its initial value we cannot know what the result is. I'ts been a long time since I programmed with Basic- and never with "Visual Basic" but in the dark, distant past, some versions of Basic assumed initial values of 0 (a really bad practice!). Is that still true?

#### Swlabr

First of all, please move this thread if it is in totally wrong place.

Anyway, I took today in our university an exam in Discrete Mathematics. The question itself was easy and I know the answer too (by counting it with computer), but what is the formula to solve this? Here's the code as VBA code:

Code:
Sub forlooptask()
Dim i As Long, j As Long, k As Long, x As Long

For i = 1 To 200
For j = 1 To i - 1
For k = 1 To j
x = x + 1
Next k
Next j
Next i

Debug.Print x
End Sub
the result is 1333300. The question is: How does the equation for solving this go? Where does that 200 go to?
EDIT: Apparently, I am unable to read an entire thread before posting. I therefore appologise for reapeating, well, everything, but this took me a while to type up (I'm a slow typer) so I'm refusing that to be (entirely) wasted time! So behold! my post...

Code:
    For i = 1 To 200
For j = 1 To i - 1
For k = 1 To j
x = x + 1
Next k
Next j
Next i
becomes
Code:
    For i = 1 To 200
For j = 1 To i - 1
x=x+j
Next j
Next i
because adding 1 on j times is the same as adding on j. Now, in this bit you are just summing up all the numbers between 1 and (i-1). There is a well-known formula for this,

$$\displaystyle \sum_a^na = \frac{a(a+1)}{2}$$. Here, a = (i-1). Thus, your code becomes,
Code:
    For i = 1 To 200
x = x + i(i-1)/2
Next i
and I suppose you can just write this as $$\displaystyle \sum_i^{200} \frac{i(i-1)}{2}$$. If you want to do it more, expand it so you will have,

$$\displaystyle \frac{1}{2}\sum_i^{200} i^2 + \frac{1}{2}\sum_i^{200}i$$

and then you can just plug in some formulas to evaluate these.

#### jflurrie

For k= 1 to j- 1
x= x+1
Next k

Just adds 1 to x j-1 times: the result is x+ j-1- it just adds j- 1 to x.

And it does that for j running form 1 to i-1: That is, we will have x+ 1+ 2+ 3+ ...+ i-2. it is well know that $$\displaystyle 1+ 2+ \cdot\cdot\cdot+ n= \frac{n(n+1)}{2}$$ so the result of the j loop will be x+ \frac{(i-1)i){2}[/tex]. (These are the "triangular numbers" 1, 3, 6, 10, ...)

Now, it does that for i going from i to 200 so it will be x+ 1+ 3+ 6... and the result will be x plus the sum of the first 199 (because it is "i-1", not "i" in the formula) triangular numbers.

To get those, look at $$\displaystyle \frac{i(i+1)}{2}= \frac{i^2+ i}{2}= \frac{n^2}{2}+ \frac{n}{2}$$.

$$\displaystyle \sum{i=1}^n \frac{i}{2}= \frac{1}\sum i$$ is easy- it is just 1/2 the sum above- $$\displaystyle \frac{n(n+1)}{4}$$.

And $$\displaystyle \sum{n^2}$$ is also well known: it is $$\displaystyle \frac{n(n+1)(2n+1)}{6}$$

I agree with TKHunny- it is peculiar that x is not initialized- without knowing its initial value we cannot know what the result is. I'ts been a long time since I programmed with Basic- and never with "Visual Basic" but in the dark, distant past, some versions of Basic assumed initial values of 0 (a really bad practice!). Is that still true?
At least in VBA I usually initialize them anyway, but this one I posted here made in like 30 seconds so I really didn't pay that much attention on that program, I just thought to show that the program returns a certain result.

What comes to your and Swlabr's answers, they look pretty good to me and I think I understood it now.

Thank you!

#### awkward

MHF Hall of Honor
First of all, please move this thread if it is in totally wrong place.

Anyway, I took today in our university an exam in Discrete Mathematics. The question itself was easy and I know the answer too (by counting it with computer), but what is the formula to solve this? Here's the code as VBA code:

Code:
Sub forlooptask()
Dim i As Long, j As Long, k As Long, x As Long

For i = 1 To 200
For j = 1 To i - 1
For k = 1 To j
x = x + 1
Next k
Next j
Next i

Debug.Print x
End Sub
the result is 1333300. The question is: How does the equation for solving this go? Where does that 200 go to?
Are you sure the code isn't

Code:
Sub forlooptask()
Dim i As Long, j As Long, k As Long, x As Long

For i = 1 To 200
For j = 1 To i - 1
For k = 1 To j[COLOR=Red] - 1[/COLOR]
x = x + 1
Next k
Next j
Next i

Debug.Print x
End Sub
with k running from 1 to j-1?

With this change, the loop generates all $$\displaystyle \binom{200}{3} = 1,313,400$$ combinations of the integers from 1 to 200 taken 3 at a time.

#### jflurrie

Are you sure the code isn't

Code:
Sub forlooptask()
Dim i As Long, j As Long, k As Long, x As Long

For i = 1 To 200
For j = 1 To i - 1
For k = 1 To j[COLOR=Red] - 1[/COLOR]
x = x + 1
Next k
Next j
Next i

Debug.Print x
End Sub
with k running from 1 to j-1?

With this change, the loop generates all $$\displaystyle \binom{200}{3} = 1,313,400$$ combinations of the integers from 1 to 200 taken 3 at a time.
No, k runs from 1 to j. We had in class version

i = 1 to 10
j = 1 to i
k = 1 to j

and that gives $$\displaystyle \binom{12}{3}$$

In an earlier exam from 2006 this same teacher has asked also the version you suggested. I guess the big idea is to understand the difference of all those versions.