Question 7

Find the number of maps $$f:\{1,2,3\}\rightarrow\{1,2,3,4,5\}$$ such that $$f(i)\leq f(j)$$ whenever $$i<j$$.


Correct Answer: e

The condition $$f(i)\le f(j)$$ for $$i\lt j$$ means the sequence $$\left(f(1),f(2),f(3)\right)$$ is non-decreasing. In other words, we need to count all weakly increasing 3-tuples whose entries come from the set $$\{1,2,3,4,5\}$$.

This is a standard “combinations with repetition’’ (stars-and-bars) problem.
Let $$x_k$$ be the number of times the value $$k$$ appears in the 3-tuple, for $$k=1,2,3,4,5$$. Then

$$x_1+x_2+x_3+x_4+x_5 = 3$$
with each $$x_k\ge 0$$.

The number of non-negative integer solutions of this equation is given by the stars-and-bars formula

$$\binom{3+5-1}{5-1} \;=\; \binom{7}{4} \;=\; \binom{7}{3} = 35.$$

Hence there are $$35$$ maps $$f:\{1,2,3\}\rightarrow\{1,2,3,4,5\}$$ satisfying the required order condition.

Get AI Help

Book Free CAT Mentorship

Get personalized CAT strategy from a 99%iler

500+ students mentored
CAT mentor
banner

banner

50,000+ JEE Students Trusted Our Score Calculator

Predict your JEE Main percentile, rank & performance in seconds

Ask AI