Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers
Suppose that the image of your mapping has size $k$. This implies a division of $\{1,\ldots,M\}$ into $k$ contiguous intervals. By identifying each such interval with its largest point, we see that there are $\binom{M-1}{k-1}$ such partitions (since $M$ is always one of the $k$ largest points). For the actual colors chosen, the number of choices is $N(N-1)\cdots(N-k+1) = N!/(N-k)!$. The total number of mappings is thus
$$
 \sum_{k=1}^N \frac{N!}{(N-k)!} \binom{M-1}{k-1}.
$$
Using this argument, it is not too hard to construct an algorithm to list all such mappings; the algorithm completely mirrors the argument.