I was tasked with the following question, regarding the counting of operations in the pseudo code provided that has nested for loops:
Let U ={B1,B2,...,Bn} with n >= 3. Interpret the following algorithms in the context of urn problems. How many lines does it print?
for i (member of) {1,2,...n} do
for j (member of) {i+1,i+2,...n}
for k (member of) {j+1, j+2,...n}
print Bi, Bj, Bk
I Think this would print out 27 lines, 3*3*3, but it asks for it in the context of an urn problem. In that case, I guess it implies there is no replacement, so would it instead be something like 3 factorial?
Also, the Capital B has no value, it's just my shorthand for the subscripts.
Any help is appreciated.
Combinatorially
The program prints three numbers in each line, so if we consider an urn containing $n$ enumerated bools form $1$ to $n$ the program consists of printing the corresponding numbers to every possible triple bools $B_i,B_j,B_k$ ($i< j< k$) this means that the number of printed lines is the number of different three bools in the urn so this is equal to the number of choosing $3$ bools in the urn. hence the number of lines is: $${n \choose 3}=\frac{n(n-1)(n-2)}{6} $$
Formally (calulus)
for every every $i$ we choose a $j$ between $i+1$ and $n$ and we the last loop prints $n-j$ lines, so the number of printed lines is: $$\sum_{i=1}^n\sum_{j=i+1}^n n-j=\sum_{i=1}^n\sum_{j'=1}^{n-i-1}j'=\sum_{i=1}^n \frac{(n-i-1)(n-i)}{2}=\sum_{i=1}^{n-1} \frac{i(i-1)}{2}=\frac{n(n-1)(n-2)}{6}$$