# Number of functions from $A$ to $B$ such that $i \lt j$ then $f(i) \le f(j)$

Number of functions from $A=\left\{1,2,3,4,5\right\}$ to $B=\left\{1,2,3\right\}$ such that if $i \lt j$, then $f(i) \le f(j)$.

My try:

It is equivalent to finding number of five-digit numbers with digits $1,2,3$ with repetition such that digits are in non-decreasing order i.e.,

$$f(1) \le f(2) \le f(3) \le f(4) \le f(5)$$

Let $d_1d_2d_3d_4d_5$ be the five digit number satisfying $$d_1 \le d_2 \le d_3 \le d_4 \le d_5$$ where $d_1,d_2,d_3 \in \left\{1,2,3\right\}$

So we have

$$a_1=d_1-1 \ge 0$$

$$a_2=d_2-d_1 \ge 0$$ $$a_3=d_3-d_2 \ge 0$$ $$a_4=d_4-d_3 \ge 0$$ $$a_5=d_5-d_4 \ge0$$

$$a_6=3-d_5 \ge0$$

Using stars and bars, the number of nonnegative integer solutions of

$$a_1+a_2+a_3+a_4+a_5+a_6=2$$ is $$\binom{2+6-1}{6-1}=21$$

Is this approach right?

A different approach: Let $A = \{1, 2, 3, 4, 5\}$; let $B = \{1, 2, 3\}$. The number of functions $f: A \to B$ satisfying $i < j \implies f(i) \leq f(j)$ is completely determined by how many times each element of $B$ appears in the range. For instance, if $1$ appears once, $2$ appears twice, and $3$ appears twice, then $f$ is the function defined by \begin{align*} f(1) & = 1\\ f(2) & = 2\\ f(3) & = 2\\ f(4) & = 3\\ f(5) & = 3 \end{align*} Hence, if we let $x_k$ be the number of times $k$, $1 \leq k \leq 3$, appears in the range, the number of non-decreasing functions $f: A \to B$ is equal to the number of nonnegative integer solutions of the equation $$x_1 + x_2 + x_3 = 5$$ which is $$\binom{5 + 3 - 1}{3 - 1} = \binom{7}{2} = 21$$ as you found.