Counting number of functions which are neither 1-1 nor onto

Question

Let $A = \left \{1, 2, 3, 4  \right \}$. Number of functions possible on $A$ which are neither $1-1$ nor on-to is _________.

Answer 1

232 (Ans)

f  : A → A            Function from set A to A itself.

Total Functions possible from A → A     are  4⁴           {$\because$ Number of Functions

                                                                                                 from A → B  are  |B|^|A| }

Now we have a property that if |A| = |B|  , then

        if function is one-one then it is onto and vice-versa.

Now Number of one-one & onto functions from A → A   are  4!   

       $\because$ 1 has 4 choices

             2 has 3 choices {we assigned a number to 1}

             3 has 2 choices

             4 has 1 choice left.

So, Total Number of Functions = 4⁴ = 256

         Number of functions which are one-one/ onto  = 4! = 24

       So, Number of functions possible on A which are neither

                 one-one nor onto is 256 - 24 = 232 (Ans)

Answer 2

Look,the number of one to one function a set to itself is basically permutation on this set.let a set has n element,no one to one function to itself is,n!.cause,first element has choice of n,next has n-1,next to next has n-2......thus... (n).(n-1)......1= n!.

Now here the set has 4 elements,so the no of one to one functions are 4!.

Now,if a function is one to one to itself,it is also onto,

Ref:http://math.stackexchange.com/questions/366146/a-one-to-one-function-from-a-finite-set-to-itself-is-onto-how-to-prove-by-indu

And basically both one to one and onto functions to the set itself are permutation of the elements of that set.

So,the number of onto functions are 4! Also.

Now as both are same ,the intersection is also 4!.

Now the number of  one to one or onto functions are 4! + 4! -4! = 4!.

Now as u already know,the no of functions to itself is n^n..that is 4^4.

So required ans is , 256-24= 232

Comments

Nice answer. Thanks!