Let $x_1, x_2, \dots, x_n$ be a finite sequence of objects of some kind, I've attempted to calculate how many subsequences of $(x_k)$ that preserve relative order have exactly $m$ elements. This means that if $x_i$ comes before $x_j$ in the subsequence, then $i < j$.
I did this by counting how many subsequences with the desired property there are in the sequence $x_k, x_{k + 1}, \dots, x_n$. If we add all of these counts for all $k$, we'll get the answer.
If $k < n - m + 1$ there are no subsequences since we're working with less than $m$ elements.
If $k = n - m + 1 - 0$, we have $1 = \binom{m + 0}{0}$ subsequences.
If $k = n - m + 1 - 1$, we have $m + 1 = \binom{m + 1}{1}$ subsequences, since we have $m + 1$ total elements, and we have to pick one to not place in the sequence.
This pattern continues: if $k = n - m + 1 - j$ we get $\binom{m + j}{j}$, until $k = 1 = n - m + 1 - (n - m)$, by the same argument, picking elements not to place in the sequence, what's left is in relative order.
So the answer should be
$$\sum_{j = 0}^{n - m} \binom{m + j}{j} = \binom{m + n - m + 1}{n - m} = \binom{n + 1}{n - m}.$$
I'm not sure if my logic is correct nor the calculation. If so, it looks like the answer has got to have some combinatorial interpretation which I'm not seeing.
This since the binomial coefficient at the end says that from $n + 1$ elements, I pick $n - m$, and that somehow counts the number of subsequence with the desired property, but I have $n$ elements originally, not $n + 1$.
Also, the formula looks very pretty if we write it in terms of multiset coefficients:
$$\binom{n + 1}{n - m} = \left( \binom{n}{n - m} \right).$$
So maybe the combinatorial interpretation comes from there, but I'm not seeing it.