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?


Your solution is correct.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.