Problem 1940

Answer. $\frac{(n-1)!}{(n-m-1)!}$. Set $B_i = \{1, 2, \dots, i\}$. By induction on $m$ we prove that for any $n > m$ the number of injective functions $f: B_m \to B_n$, that satisfy the condition of the problem equals $(n-1)(n-2)\dots(n-m)$.

For $m=1$ we have $f(1) \neq 1$, i.e. there are $n-1$ possible values for $f(1)$ and the base case is true. Assume the statement is true for $m-1$ and consider function $f: B_m \to B_n$ satisfying the condition for arbitrary nonempty subset of $B_{m-1}$.

Case 1. Assume $m \notin f(B_{m-1})$. There are $m$ "forbidden" values for $f(m): f(B_{m-1}) \cup \{m\}$. The first $m-1$ because the function is injective and the last one because $= \{m\}$ does not satisfy the condition. Therefore there are $n-m$ values.

Case 2. Assume $m \in f(B_{m-1})$ and let $a_1 = f^{-1}(m) \in B_{m-1}$. By analogy if $a_1 \in f(B_{m-1})$ then let $a_2 = f^{-1}(a_1) \in B_{m-1}$ and so on. Since $m \in f(B_{m-1})$ and $m \notin B_{m-1}$ the two sets have the same cardinality and we arrive to a number $a_k \in B_{m-1}$ such that $f(a_k) = a_{k-1} \in f(B_{m-1})$ but $a_k \notin f(B_{m-1})$. Then all forbidden values of $f(m)$ are $f(B_{m-1}) \cup \{a_k\}$ (due to the injectivity or because of the set $A' = \{a_1, a_2, \dots, a_k, m\}$). All remaining $n-m$ values are possible. Indeed, consider nonempty set $A \subseteq B_m$. If $m \notin A$ then $f(A) \neq A$ according to the induction hypothesis. If $m \in A$ and $f(A) = A$ then it follows from $m \in f(A)$ that $a_1 \in A$ and $A' \subseteq A$. Thus $a_k \in A$ and $a_k \notin f(B_m) \notin f(A)$, a contradiction. In both cases we have $n-m$ possible values and the answer is $(n-1)(n-2)\dots(n-m)$.