# of onto functions ,# into functions,#one to one function on two sets

Question

Could anybody give me direct formule for it set A has n elements and set B has m elements.what is the direct formula for 1)number of onto functions .

2)Into function.

3)one to one function.

Answer 1

Suppose we have set X has m elements and another set Y has n elements.

(1)Number of one to one function possible

We can  map the first element of the domain to any of the n element of co-domain.

Second element to remaining choices n-1and so on.Continue in this way until you reach the last element of the domain,
which can be mapped to any of the remaining.So total possible combination are
n(n-1)(n-2)9n-3)..........(n-m+1)=nPm

                                                                                                                               

(2)Number of onto  function possible

Consider a practical case here

In how many ways can we put m guests in n rooms so that no room stays vacant.

Normally we can distribute in n^m.

Out of these there are

nC1*(n-1)^m ways if some room is vacant

nC2*(n-2)^m ways if some two room is vacant

nC3*(n-3)^m ways if some three room is vacant and so on.

Note:Some rooms in B may be there which is not occupied by any of the guest of A.So we have to subtract those function which exactly one room of B was not occupied So in this case each of m guest has only n-1 choice.So nC1*(n-1)^m ways .

But this strategy subtracted those functions two times,
which had two rooms of B not occupied ,so we have to add those functions one time in which exactly 2 rooms of B were not occupied. So if 2 rooms were not mapped, then each of the m guest  of A had n-2 choices,so we have nC2*(n-2)^m ways and we have to continue this way.

So nC1*(n-1)^m-nC2*(n-2)^m+nC3*(n-3)^m -.......... way to have vacancy.

n^m-nC1*(n-1)^m+nC2*(n-2)^m-nC3*(n-3)^m -.......... way to occupy all rooms.

The generalized formula for no of onto function given below.

Comments

Even though the question exactly asks for this, it is not a good way to answer like this. Any formula when given should be given with proper explanation unless it is something so hard. Also, explaining them will only make the concept stronger.

---

Still not clear how the "-" came. 

"into" is just a normal function. 
http://math.stackexchange.com/questions/649271/into-function-vs-injective-function