Maths Olympiad Prep

Library / /15 of 520

Combinatorics Difficulty 6.2 National olympiad Find the answer

A={1,2,3,4,5,6,7,8}.A=\{1,2,3,4,5,6,7,8\} . How many functions f:AAf: A \rightarrow A are there such that f(1)<f(2)<f(3)f(1)<f(2)<f(3)

- (83){{8}\choose{3}}

- (83)58{{8}\choose{3}}5^{8}

- (83)85{{8}\choose{3}} 8^{5}

- 8!3!\frac{8 !}{3 !}

Multiple choice: answer with the letter of the option you want.

Solution

1. We need to count the number of functions f:AA f: A \rightarrow A such that f(1)<f(2)<f(3) f(1) < f(2) < f(3) .
2. First, we choose 3 distinct values from the set A={1,2,3,4,5,6,7,8} A = \{1, 2, 3, 4, 5, 6, 7, 8\} for f(1),f(2), f(1), f(2), and f(3) f(3) . The number of ways to choose 3 values out of 8 is given by the binomial coefficient:
(83) \binom{8}{3}
3. Once we have chosen 3 values, there is exactly one way to assign these values to f(1),f(2), f(1), f(2), and f(3) f(3) such that f(1)<f(2)<f(3) f(1) < f(2) < f(3) .
4. For the remaining 5 elements f(4),f(5),f(6),f(7), f(4), f(5), f(6), f(7), and f(8) f(8) , each can be any of the 8 elements in A A . Therefore, there are 85 8^5 ways to assign values to these 5 elements.
5. Combining these, the total number of functions f f is:
(83)×85 \binom{8}{3} \times 8^5

The final answer is (83)×85 \boxed{ \binom{8}{3} \times 8^5 }

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.