Question

If a set A has n elements, then the number of functions defined from A to A that are not one - one is

• A. $(n)^{n^2}$
• B. $n!- (^n C_0 + ^n C_1 + ^n C_2 + ...... + ^n C_n)$
• C. $n^n - n!$
• D. $n^n$

Answer 1

Answer: (C)

$n^n - n!$

Answer 2

Let A be a set with $n$ elements. We are considering functions defined from A to A. The domain of the function is A, and the codomain of the function is A. Both the domain and codomain have $n$ elements.

The total number of functions from a set with $m$ elements to a set with $k$ elements is $k^m$. In this case, $m=n$ and $k=n$, so the total number of functions from A to A is $n^n$.

A function $f: A \to A$ is one-one (or injective) if for any two distinct elements $x_1, x_2 \in A$, their images are distinct, i.e., if $x_1 \neq x_2$, then $f(x_1) \neq f(x_2)$. For a function from a finite set to itself, being one-one is equivalent to being onto (surjective) and being a bijection. To define a one-one function from A to A, we need to assign each element in the domain A to a unique element in the codomain A. This is equivalent to finding a permutation of the elements of the codomain. For the first element in the domain, there are $n$ choices in the codomain. For the second element in the domain, there are $n-1$ remaining choices in the codomain (since the image must be distinct from the first element's image). For the third element, there are $n-2$ remaining choices, and so on. For the $n$-th element, there is only 1 choice left. So, the number of one-one functions from A to A is $n \times (n-1) \times (n-2) \times \dots \times 1 = n!$.

We are asked to find the number of functions from A to A that are not one-one. The set of all functions from A to A can be partitioned into two disjoint sets: the set of one-one functions and the set of functions that are not one-one. Therefore, the number of functions that are not one-one is equal to the total number of functions minus the number of one-one functions. Number of functions that are not one-one = (Total number of functions) - (Number of one-one functions) Number of functions that are not one-one = $n^n - n!$.

The result $n^n - n!$ matches option (3).