Let $S = \{1,2,3,4\}$. How many nonstrict monotonic increasing functions $f:S\to S$ are there? Let $S = \{1,2,3,4\}$. Let $f:S\to S$ be a function such that $f(x) \le f(y)$ if $x<y$. How many such $f$ are there?
How should I proceed? $f(1)$ has $4$ choices. But the number of possible values of $f(2)$ depends on $f(1)$. For example, if $f(1) =1$ then $f(2)$ can be $1,2,3,4$. But if $f(1)=2$, then $f(2)$ cannot be $1$.
 A: Split cases according to the range of $f$. If the range of $f$ has four elements, we have only the identity function. If the range of $f$ has three elements $a<b<c$, $f$ has three different kinds, according to $(1,2,3,4)$ being mapped to $(a,a,b,c),(a,b,b,c)$ or $(a,b,c,c)$. It follows that we have $12$ weakly increasing function from $S$ to $S$, such that $|f(S)|=3$. If the range of $f$ has just two elements $a<b$, we have three kinds, according to $(1,2,3,4)$ being mapped to $(a,a,a,b),(a,a,b,b)$ or $(a,b,b,b)$, hence $18$ functions. If the range of $f$ has only one element, we have four functions. Summarizing, the answer is given by
$$ 1+12+18+4 = \color{red}{35} = \binom{7}{3}.$$
This number is also the sum of the coefficients of $1,x,x^2,x^3$ in $(1+x+x^2+x^3)^4$, not by chance. Can you figure out why?
A: The number of non-decreasing functions is completely determined by the number of times each element occurs in the range.  For instance, if $1$ occurs once, $2$ occurs twice, and $4$ occurs once, then the requirement that the function is non-decreasing forces $f(1) = 1$, $f(2) = f(3) = 2$, and $f(4) = 1$.  
Let $x_k$ be the number of times the integer $k$ appears in the range.  The number of non-decreasing functions $f:\{1, 2, 3, 4\} \to \{1, 2, 3, 4\}$ is the number of solutions of the equation
$$x_1 + x_2 + x_3 + x_4 = 4$$ 
in the non-negative integers.  A particular solution corresponds to the placement of three addition signs in a row of four ones.  For instance, 
$$1 + 1 1 + + 1$$ 
corresponds to the solution $x_1 = 1$, $x_2 = 2$, $x_3 = 0$, and $x_4 = 4$ (and the function given above), while 
$$1 + 1 + 1 + 1$$
corresponds to the solution $x_1 = x_2 = x_3 = x_4 = 1$ (and the identity function $f(x) = x$).  The number of such solutions is equal to the number of ways we can select which three of the seven symbols (four ones and three addition signs) are addition signs, which is 
$$\binom{4 + 3}{3} = \binom{7}{3} = 35$$
