We still need to insert the remaining copies of the new elements. For the next copy, there are exactly (m + 1) positions available, where it can be placed
2,-, 4, -, 5, -, 3, -, 8-, 6, -, 3, -, 11, -
The copy after that will have (m + 2) positions available, and so on.
Hmm, can I ask, why has the new copy (m+2) positions available?
Isn’t like 2,2,-,3… same as 2,-,2,3 …
Though the expression is same, we are here counting number of ways to get that.
Lets say we have {4 5} and {2a,2b,2c} where a,b,c just differentiate between 2’s. So m=2 and n=3.
Now we have three possibility {2a 4 5} {2b 4 5} {2c 4 5}
For first set, 2b have 3 places to be put i.e (m+1)
now we have {2a 2b 4 5} {2a 4 2b 5} {2a 4 5 2b}
So 2c have 4 places to be put i.e (m+2) for every above set possible after putting 2b. so just for 1st set we have
{2a 2c 2b 4 5}{2a 2b 2c 4 5}{2a 2b 4 2c 5}{2a 2b 4 5 2c}
You can see first two sequences are same(by removing a,b,c) but we will count them.
Thanks for this good paper…
Is the loop "for (int r = k - 1; r >= 0; --r) " should be "for (int r = k ; r >= 0; --r) "?? Please explain it.