Problem:
Find the number of functions from to that satisfy for all in .
Solution:
Suppose has the desired property with fixed points and additional elements that each maps to a fixed point. Then each of the remaining elements maps to one of the elements that maps to a fixed point. For a given and , there are ways to select the fixed points, ways to select the elements to map to these fixed points, ways to define a mapping of those points to the fixed points, and ways to map the remaining points. Thus the required number of functions is
Note that there are no functions with or with and . The identity function is the one function with and . The sum contains terms, of which are nonzero. The sum equals .
The problems on this page are the property of the MAA's American Mathematics Competitions