# Program segment question for combinatorics

1. Jan 31, 2015

### Magenta55

Consider the following segment where i,j,k,n and counter are integer variables and the value of n (a positive integer) is set prior to this segment.

counter := 0
for i := 1 to n do
for j :=1 1 to i do
for k :=1 to j do
counter := counter + 1

I am so lost as to what this program is even doing. Can anyone help explain what is does? I just need to know what it does upon first execution, second execution, etc.. and I may be able to solve it from there.

2. Jan 31, 2015

### phinds

It's a simple nested loop that will end up with counter = j*i*n, which is a waste of time since you could just do the multiplication. Where nested loops are useful is where you DO something useful inside the loops, so I assume this is just an example of a nested loop for study purposes.

EDIT: OOPS ... no, that's NOT what it is. I see now that the inner loops are using the outer loop variables for a limit, SO ... this is something like a bubble sort nested loop and can be used for something LIKE(*) # of combinations or permutations. I'd have to look more closely to see how it might relate to combinatorial forumlae, but basically it's just a nested loop which, as I said, uses the outer loop variable as the inner loop limit.

(*) LIKE is emphasized to mean "not necessarily exactly" since I have not looked at the results in detail.

Last edited: Jan 31, 2015
3. Jan 31, 2015

### chingel

This gives you ${n+2 \choose 3}$. You have n+2 elements going from 1 to n+2. first you pick the element 2+i from range $[3;n+2]$, then element 1+j from range $[2;1+i]$, then k from $[1;j]$. You are choosing all such possible combinations and by making the next choice in the range smaller than the last choice, you guarantee that you don't pick the same triple many times in a different order. The shifting starting point is necessary so that you have something to pick next, if you pick the first element at the first step, there wont be any left to pick in the next step, because in your formula the next index goes up to the previous one. So you are getting how many different triples can you take from n+2, which is the binomial coefficient ${n+2 \choose 3}$.