Combinatorics: How to find the number of sets of numbers in increasing order? The problem is the following one:
Let $n$ and $m$ be natural numbers and $m < n$. Find $m$-permutations of the set $\{1, 2,\dots, n\}$ such that permutations are in non-decreasing order (for both cases where repetition is allowed and where it is not allowed).
Tried to solve, still have no ideas.
Thanks in advance.
 A: If repetitions are not allowed, then you are interested in counting the number of subsets of $\{1,2,\ldots,n\}$ of size $m$. This is a typical first problem in enumerative combinatorics, with solution (by definition) $\binom{n}{m}$. One can prove $\binom{n}{m} = \frac{n!}{m!(n-m)!}$ as follows.
If $\binom{n}{m}$ is the number of subsets of size $m$ from $\{1,\ldots,n\}$, or as you put it, non-decreasing $m$-permutations, then $m!\binom{n}{m}$ is the total number of such $m$-permutations. But these can be counted another way too: there are $n$ ways to choose the first element, $n-1$ ways to choose the second element, ..., and $n-m+1$ ways to choose the $m$th element. We thus find
$$m!\binom{n}{m} = n(n-1)(n-2)\cdots(n-m+1) = \frac{n!}{(n-m)!},$$
so $\binom{n}{m} = \frac{n!}{m!(n-m)!}$.
If repetitions are allowed, then you are counting "multisets" of size $m$. The answer turns out to be $\binom{n+m-1}{m}$. This answer can be got as follows. We can choose an $m$-multiset in the following slightly funny way. Imagine $m$ balls in a line. These will be our elements, but they are currently missing names. We will name in them in order, e.g., 11123345555. To do this, we just need to indicate where the "fences" are, i.e., where one label ends and the next begins. There are $m+1$ places for our $n-1$ fences, and so we just have to choose an $(n-1)$-multiset from a set of $m+1$ elements! Interesting though this is, it doesn't help.
Here is a slightly stranger way of choosing where the fences will be. Add $n-1$ more balls to our line, so we have $m+n-1$ balls in all. Now we just have to choose $n-1$ of those balls to turn into fences. Thus the number of $m$-multisets of $\{1,\dots,n\}$ is $\binom{n+m-1}{n-1} = \binom{n+m-1}{m} = \frac{(n+m-1)!}{m!(n-1)!}$
A: We have a numbers $a_1, ..., a_k$, where ${a_1}\le{a_2}...\le{a_n}$. In this set is ${n}\choose{m}$ options to organize these numbers in non-decreasing order. Each such arrangement may be present $(n-m)!$ times. Count of permutations with non-decreasing order is:
$${{n}\choose{m}}(n-m)!$$

Note: If we search numbers in increasing order: If we have numbers $a_1, ..., a_k$, where $k\ge{m}$, taking the number of $a_1$ may be repeated $r_1$ times in set, $a_2$ number $r_2$ times and so on. The $a_1 \lt a_2 \lt ... \lt a_k$. Additionally, $\sum_{i=1}^k{r_i} = n$. In this set is ${k}\choose{m}$ options to organize these numbers in increasing order. Each such arrangement may be present $(n-m)!$. Also, $m\le{n}$. So number of permutations having $m$ numbers in increasing order(${a_1}\lt{a_2}...\lt{a_k}$) is:
$${{k}\choose{m}}(n-m)!$$
