Let us consider some sample value of n and m.
The value of n decides the number of outer loops . And the value of m decides the number of inner loops we have.
First case : take n=1 and m=1.
So we have only one loop For i1=1 to 1. K=k+1. [ K = 0 so K = 0+1 = 1 ]
K = 1.
Second case : take n=2 and m=1
For i=1 to 2 . K=k+1 = 1+1 = 2
K = 2.
Third case : take n=3 and m=2
So the pseudo code can be represented in this case :
K:=0
for i:= 1 to n
for m:= 1 to i
K:=K+1
For the value of n=3 and m=2, the value of K would be incremented in the following manner.
i |
m |
K |
1 |
1 |
1 |
2 |
1 |
2 |
2 |
2 |
3 |
3 |
1 |
4 |
3 |
2 |
5 |
3 |
3 |
6 |
The value of i ranges from 1 to n where n=3 in this case .
The value of K is K =6 at the end of the iterations.
Now we have to check with each option , by substituting the value of n and m in the given options .
First take option A, C(n + m – 1, m )
put n = 3 and m =2 here
C(n+m-1,m)=C(3+2-1,2)=C(4,2)=4!/2!*2!=6.
so we get k = 6
again put n ,m value with option B , C(n – m + 1, m)
C(3-2+1, 2) = C(2,2) = 2!/2! = 1
option C , C(n + m – 1, n)
C(3+2 - 1,3) = C(4,3) = 4! / (3! 1!) = 4
option D, C(n – m + 1, n)
C(3-2+1, 3) = C(2,3) = 2!/3! -1!
so we can see only K = C(n + m – 1, m) gives us correct answer for K which is K = 6 when n=3 and m =2 .
Hence value of K is K= C(n + m – 1, m) .
Even if we put n=2 and m=1 as we took in our 2nd case , the value of k would be :
K =C(n + m – 1, m) =C(2+1 -1,1) = C(2,1) = 2!/1! 1! = 2
which match with our K value , we got as K = 2 .( our second case )
same way we can check with our first case also !
P.S C(n+m-1,m) is equal to n ! / ( m ! * (n-m) !).