edited by
2,593 views
5 votes
5 votes

What is the value of k after the following pseudocode has been executed?

k := 0
for i1 := 1 to n
 for i2 := 1 to i1
  ·
  ·
  ·
  for im := 1 to im−1
   k := k + 1

The solution given is:
$k = C(n + m − 1,m)$

(A) C(n + m – 1, m) 
(B) C(n – m + 1, m) 
(C) C(n + m – 1, n) 
(D) C(n – m + 1, n) 

How do we reach this answer?
I'm not getting why they used the r-permutation formula here.

edited by

3 Answers

Best answer
5 votes
5 votes

Take N numbers.
1 2 3 4 . . . . . . . . . N.
Now, the task is to choose M numbers from these N numbers such that repetition is allowed.

Suppose we have chosen the sequence (Example)

1 2 3 4 5 6 7 8 ..... m (Total m numbers are there).

Now for this sequence, the value of K is incremented by 1 only. (${\color{Red} How ?}$)

Suppose if we assign ${\color{Red} i1 = 1 }$​ ​​​​​​and ${\color{Red} i2 = 2 }$ then second for loop become false. And we don't go further so there is no increment in the value of K.

To increment the value of K by 1, We should assign these values in such a way that all for loops becomes true.

To do this, i1 must have a higher value than i2, i2 must have a higher value than i3, i3 must have a higher value than i4 and so on.

Therefore i1 = m, i2 = (m - 1), i3 = (m - 2) ....... i(m-1) = 2 , im = 1 is the only solution.

Now Take any sequence we should always assign these value in such a way that i1 is higher than i2, i2 is higher than i3 and so on.

So, what ever M number we choose there is only one way to assign these value to i1, i2, i3 ..... im such that all the for loops are true and we increment the value of K by 1.

So now the problem is reduced to the problem of choosing M number from N number such that repetition is allowed.

And we already now that it can be done in C(N + M - 1, M) ways.

So the answer is C(N + M - 1, M).

PS: What if we choose the sequence 1 1 1 1  ..... (m times)? It is a valid sequence as repetition is allowed.

No problem Sort these number in decreasing order. That will be 1 1 1 1 1 ..... (m times).
And assign the first number to i1, second no. to i2 and so on. Then our all the for loop become true, And we increment the value of K by 1.
 

selected by
1 votes
1 votes

 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) !). 

0 votes
0 votes

Example 1:

for(i=1 to 4){

          for(j=1 to i) {

                    K=K+1;

                              }

                    }

i=         1               2                    3                       4

j=         1              1 2                  1 2 3                  1 2 3 4

K=        1              2 3                  4 5 6                  7 8 9 10

after terminating this loop  K's value  would be 10.

Check from the formulae K = C(n + m − 1, m)

Here in example n=4,  m=2

 putting these in formulae then,           C(5,2)=10 means K=10   // verified earlier also we get in ex K=10

 

Example 2:

for(i=1 to 3){

          for(j=1 to i) {

                    for(h=1 to j) {

                                 K=K+1;

                                          }

                              }

                    }

 

i=         1                            2                                       3                 

j=         1                            1         2                             1       2       3                 

h=        1                            1          1 2                         1       1 2    1 2 3

K=        1                            2          3 4                         5       6 7    8 9 10

after terminating this loop  K's value  would be 10.

Check from the formulae K = C(n + m − 1, m)

Here in example n=3,  m=3

 putting these in formulae then,           C(5,3)=10 means K=10   // verified earlier also we get in ex2 K=10

 

So, now it is proved that, the number of such sequences of integers is the number of ways to choose m integers from {1, 2, . . . , n}, with repetition allowed. So K's value would be K = C(n + m − 1, m) after this code has been executed.

Answer:

Related questions

1 votes
1 votes
3 answers
1
Lakshman Bhaiya asked Mar 2, 2018
4,241 views
How many ways are there to put four different employees into three indistinguishable offices when each office can contain any number of employees?
1 votes
1 votes
1 answer
2
tusharp asked Jul 5, 2018
1,701 views
I am not getting this condition. Can someone please explain that condition with that example.
2 votes
2 votes
1 answer
3
aditi19 asked Nov 16, 2018
1,902 views
How many solutions are there to the equation x1+x2+x3=17 with x1<6, x3>5?
0 votes
0 votes
1 answer
4
aditi19 asked Nov 14, 2018
504 views
Suppose that a set S has n elements. How many ordered pairs(A,B) are there such that A and B are subsets of S with A$\subseteq$ B?