Maths Olympiad Prep

Library / /115 of 520

Combinatorics Difficulty 5.2 AIME, harder Find the answer

\qquad * Let m,nN+,mnm, n \in \mathbf{N}_{+}, m \leqslant n. Sets A={a1,,am},B={b1,,bn}A=\left\{a_{1}, \cdots, a_{m}\right\}, B=\left\{b_{1}, \cdots, b_{n}\right\}.
(1) Find the number of all mappings from AA to BB;
(2) Find the number of all injections from AA to BB;
(3) Does there exist a surjection from AA to BB?

A number or a short expression. Spacing and $ signs are ignored.

Solution

(1) Since each element in AA has nn elements in BB that can serve as its image, the number of mappings from AA to BB is nmn^{m}.
(2) Determine the images of elements a1,,ama_{1}, \cdots, a_{m} in AA sequentially, with the number of methods being n,n1,,n(mn, n-1, \cdots, n-(m-
1). Therefore, the number of injections from AA to BB is n(n1)(nm+1)(=Anm)n(n-1) \cdots(n-m+1)\left(=\mathrm{A}_{n}^{m}\right).
(3) When n=mn=m, there exist surjective mappings from AA to BB, and the number of surjective mappings is nn!. When n>mn>m, there are no surjective mappings from AA to BB.

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.