Let and . Then the number of elements in the set and is not one-one is...
We have so , and so . A function assigns to every element of exactly one element of .
First, recall that the total number of all possible functions from a set with elements to a set with elements is because each element of the domain has independent choices. Here, and , so the total number of functions is
We are interested only in those functions which satisfy two simultaneous conditions:
(i) meaning that at least one element of is mapped to .
(ii) is not one-one (not injective), i.e. at least two elements of share the same image.
We shall count functions satisfying (i) first, then remove those that violate (ii). Let us denote by the number of functions satisfying (i) and by the number of those functions which are also injective. The desired count will therefore be
Counting - functions with in the image.
Consider the complementary set of functions where never appears. For every element of we then have only available, that is choices per element. Hence the number of such functions is
By subtraction, the number of functions that do include is
Counting - injective functions with in the image.
A function from a set of elements to a set of elements is injective exactly when it assigns three distinct images. The total number of injective functions is therefore the number of permutations of any distinct elements chosen from , which is the permutation number
Among these, let us identify how many avoid the value entirely; such functions must use the three values . There is only one way to choose these three values, and they can be arranged in ways. Hence
Consequently, the injective functions that do contain are
Final subtraction.
We now exclude these injective functions from the functions that contain :
So, the answer is .
Tagged One-one, onto functions and counting functions. Machine-assigned, so read it as a strong shortlist rather than a verdict.