find sum of products of n factors each How can one show that the sum of all products of n positive integers, each of which is less than or equal to the positive integer m, is given by the Stirling number of the second kind, S(n+m,m)? For example, for n=2 and m=3, there are 6 such products: 3x3, 3x2, 3x1, 2x2, 2x1, 1x1; and their sum = 25 = S(5,3).
 A: We have from first principles the generating function (here the term $r^k
z^k$ means that we choose the value $r$ exactly $k$  times for a
contribution to the product of $r^k$ by way of $k$ factors)
$$\prod_{r=1}^m (1 +  rz + r^2 z^2 + \cdots)$$
Hence the desired quantity is given by (extract contribution of $n$ factors)
$$[z^n] \prod_{r=1}^m \frac{1}{1-rz}
= [z^{n+m}] \prod_{r=1}^m \frac{z}{1-rz}.$$
But this last generating function is precisely the OGF of the Stirling
numbers of the second
kind and we get
$$[z^{n+m}] \sum_{p\ge m} {p\brace m} z^p
= {n+m\brace m}$$
as claimed.
A: Define the function $f(m,n)$ to return the sum of all products of the elements of $n$ positive integers, each of which is less than or equal to the positive integer $m$.
Let's first start with some terminology/syntax to make things clear. I will use a small example of $n=3$ and $m=3$ to make things clear. First consider all possible triples of integers that are multiplied together. These are
$$(3,3,3);(3,3,2);(3,3,1);(3,2,2);(3,2,1);(3,1,1);(2,2,2);(2,2,1);(2,1,1);(1,1,1)$$
Notice that elements of each of these $\mathbf{n}$-tuples are in nonincreasing order. Moreover, we have lexographically ordered all the tuples in decreasing order e.g. $(3,3,3)$ is before $(3,3,2)$ or $(3,1,1)$ is before $(2,2,2)$
In general terms for general $m,n$, let's denote the set of all $n$-tuples as $\mathcal{S}$, where the tuple starting from lexographically highest is $s_1$ and $s_i$ is lexographically higher than $s_{i+1}$ for all relevant $i$. We can show with stars-and-bars that
$$|\mathcal{S}|=\binom{m+n-1}{n}$$
Since it is not essential to the solving of the problem, I will leave that as an exercise to the reader. This means that $s_{\binom{m+n-1}{n}}$ is the lexographically smallest tuple and will be composed of $n$ $1$'s.
Moreover, denote the product of the elements in a tuple $s_i$ as $p_i$. We have that
$$f(m,n)=\sum_{i=1}^\binom{m+n-1}{n} p_i$$

Now for solving the actual problem, consider the $n$-tuples that have a first element of $m$ (most importantly, these are the only tuples that contain at least one $m$). Using a similar stars-and-bars reasoning, it is not hard to see that there are $\binom{m+n-2}{n-1}$ $n$-tuples that have a first element of $m$. Since these are the elements $s_1$ through $s_\binom{m+n-2}{n-1}$. Hence, their sum is
$$\sum_{i=1}^\binom{m+n-2}{n-1} p_i$$
Since each of these $p_i$ terms contain a factor of $m$, we can factor that out. What we are left with is all the $p_i$ terms for all the $(n-1)$-tuples that contain  positive integer elements that are at most $m$. Hence, we have
$$\sum_{i=1}^\binom{m+n-2}{n-1} p_i$$
$$=m\cdot f(m,n-1)$$
Now, consider the remaining elements of $\mathcal{S}$ that do not contain $m$. The sum of all these $p_i$ terms will of course be the sum of the $p_i$ terms for all $n$-tuples that contain positive integer elements that are at most $m-1$. Hence, we have
$$\sum_{i=\binom{m+n-2}{n-1}+1}^\binom{m+n-1}{n} p_i$$
$$=f(m-1,n)$$
Combining these ideas, we have
$$f(m,n)=\sum_{i=1}^\binom{m+n-1}{n} p_i$$
$$f(m,n)=\left(\sum_{i=1}^\binom{m+n-2}{n-1} p_i\right)+\left(\sum_{i=\binom{m+n-2}{n-1}+1}^\binom{m+n-1}{n} p_i\right)$$
$$\boxed{f(m,n)=m\cdot f(m,n-1)+f(m-1,n)}$$
We can also computationally determine that
$$f(1,1)=1$$
Now consider the stirling numbers of the second kind that are in the form $\begin{Bmatrix} m+n\\m\end{Bmatrix}$. Using the recursive definition of the stirling numbers of the second kind, we know that they follow the recursion
$$\begin{Bmatrix} m+n\\m\end{Bmatrix}=m\begin{Bmatrix} m+n-1\\m\end{Bmatrix}+\begin{Bmatrix} m+n-1\\m-1\end{Bmatrix}$$
With initial condition
$$\begin{Bmatrix} 1+0\\1\end{Bmatrix}=1$$
We see that $f(m,n)$ and $\begin{Bmatrix} m+n\\m\end{Bmatrix}$ follow the same recursion and have the same initial conditions. Hence, they must be the same.
