How many functions $ f : A \rightarrow A$ can be defined such that $\text{f(1) < f(2) < f(3)?}$

Question

Question

Let $A = \left \{ 1, 2, 3, 4, 5, 6, 7, 8 \right \}$. How many functions $ f : A \rightarrow A$ can be defined such that $\text{f(1) < f(2) < f(3)?}$

My Approach

I selected $f(3)$ from range-: $\text{8 choice}$

I selected $f(2)$ from range-: $\text{7 choice}$

I selected $f(1)$ from range-: $\text{6 choice}$

Remaining range of the function can be mapped to $5^8$ ways

so # functions possible =$8 \times 8 \times 7 \times 5^{8}$

I think i am making mistake.Please help me out.

Answer 1

There are fewer than $8$ options for $f(3)$. For example, you cannot choose $f(3)=1$, because then $f(2)$ cannot be defined so that $f(2)<f(3)$ is satisfied.

---

Instead, think about it this way:

1. It's not important what $f(4)\dots, f(8)$ are, you just need to count the number of ways you can define $f(1),f(2), f(3)$ and then multiply that by $8^5$. NOTE: it's $8^5$ because you can map any of the $5$ elements $4,5,6,7,8$, and each of them can be mapped to any of $8$ options. So, $8$ options for $4$, $8$ for $5$ and so on, a total of $8^5$ options.
2. For the function values on $\{1,2,3\}$, every function that satisfies the contidion $f(1)<f(2)<f(3)$ can "uniquely" determine a subset of size three $\{f(1), f(2), f(3)\}\subseteq A$.

Answer 2

Hint. There are $\binom{8}{3}$ options for the triplet $(f(1),f(2),f(3))$ with $f(1)<f(2)<f(3)$: $\binom{8}{3}$ is the number of subsets of $A$ with three (distinct) elements which can be arranged in ascending order. Moreover for $f(k)$ with $k=4,\dots,8$ there are no restrictions, therefore we have $8$ ways for each of such values.

Answer 3

Clearly if you are provided with 3 elements, you can arrange them in increasing order in just one way. So, just choose 3 elements from the set of 8 which will be in $^8C_3$ ways and for each choice, you will have exactly one way of arranging them in increasing order. For all other input entries of $f$ you will have 8 choices for each. So, total no. of ways will be $^8C_3\times8^5$