Number of lists of n sorted elements of m values I am trying to count the number of sorted lists of $n$ elements where each element is in the set $\\{1, ..., m\\}$. I have made some progress by observing the following things:

*

*There can be from $1$ to $min(m, n)$ different values in any list

*If $k$ denotes the number of different values in the list, there are $\binom{m}{k}$ ways of chosing the $k$ different values among the $m$ available ones

*For each of those ways, there are $\binom{n-1}{k-1}$ ways of building a sorted list (think of it as placing $k-1$ bars between the $n$ numbers of the sorted list, to chose how to distribute the k different values to the n numbers)

Putting all of that together, the total number of sorted lists is :
$$\sum_{k=1}^{min(m,n)}{\binom{m}{k}\binom{n-1}{k-1}}$$
That's all good, but I would like to simplify that expression. I tinkered with that a lot without success (trying to somehow apply Vandermonde's identity, telescoping sums, induction, ...). Then, I typed it in Wolfram Alpha, and it told me that this whole sum simplifies down to $\frac{m(m+n-1)!}{m!n!}$, so I suppose that this expression is actually simplifiable.
My question is hence how to simplify that expression (which identity should I use in particular, since binomial coefficients have dozens of identities).
If anyone can help me, I would be very glad ! Thank you anyway !
 A: Say $A = \{a_1 = 1, a_2 = 2, ..., a_m = m\}$, $m$ distinct elements in sorted order.
You are making a sorted list of $n$ elements with values from $A$.
This is equivalent to making a set of $(m+n)$ elements where I first place $a_1$ to $a_m$ in sorted order in m places and then there is only one way to place our sorted list in the remaining $n$ places. Say, the values of all elements of our sorted list equal to the preceding element of $A$. So, for example, if $k$ positions are free after $a_i$, all of them will have value $a_i$. Since our list follows elements of $A$, we fix the first position for the first element of $A \, (a_1)$ and choose rest $(m-1)$ places for $A$ from $(m+n-1)$ places.
So number of sorted list with $n$ elements and values between $a_1$ and $a_m$ = ${m+n-1} \choose {m-1}$.
Also, you can apply Vandermonde's identity to your result.
$\sum_{k=1}^m{\binom{m}{k}\binom{n-1}{k-1}} = \sum_{i=0}^{m-1}{\binom{m}{i+1}\binom{n-1}{i}} = \sum_{i=0}^{m-1}{\binom{n-1}{i} \binom{m}{(m-1)-i}} = {{m+n-1} \choose {m-1}}$
