Permutation and Combination - Algorithm

Question

Given Data in the problem

1. For I= 1 to 10

   print(x)

   means executing the immediate next line after for loop command 10 times. So here it prints "x" 10 times. Typical simple for loop construct in programming/algorithm

Question

1. We have an execuation segement given as follows

   For $I_1$= $1$ to $n$

   For $I_2$= $1$ to $I_1$

   For $I_3$= $1$ to $I_2$

   ........................

   ........................

   For $I_{199}$= $1$ to $I_{198}$

   For $I_{200}$= $1$ to $I_{199}$

   print("Hello")

---

How many times this execution segment prints the word "Hello" ?(as a function of n) There is a mathematical expression for it using theorems in Permutation and combinations. I remember some one solved it years before in my college. But I lost the logic and principle for doing it

Answer 1

Basically, if the loop depth is $m$ (here $m=200$), if you print all $I_j, j = 1,2,\ldots, m$ over all the times this loop prints the word "hello", you'll see that it is manually listing all the multi-subsets of $[n] = \{1,2,\ldots,n\}$ that are of size $m$. The formula for this is $\displaystyle \binom{n+m-1}{m}$. So in this case it prints "hello" $\displaystyle \binom{n+200-1}{200}$ times.