maths-functions

[ritu]

hello guys:)
suppose set A contains "m" elements and set B contains 'n" elements..........then:
a)how many number of functions are possible from A to B?(ans:nCm.m!)
b)how many number of one-one functions are possible from A to B?
c)how many number of onto functions are possible from A to B?
d)how many number of bijective functions are possible from A to B?

actually i know the formulaes but not the reasoning behind it....so please reply to these questions........
thank you:)

[Amit Goyal]

suppose set A contains "m" elements and set B contains 'n" elements..........then:
a)how many number of functions are possible from A to B?
A has m elements and B has n elements. Let A= {x(1), x(2), ..., x(m)} and B = {y(1), y(2), ..., y(n)}. A function f : A --> B will map every element A to exactly one element in B. We can map x(1) to B in n ways. Similarly, x(2) in n ways and so on. Total number of functions possible are thus n x n x..x n (m times) = n^m.

b)how many number of one-one functions are possible from A to B?
If n < m, number of one to one functions possible is 0.
For n ≥ m, it is C(n,m) m!. (First we select m elements from B which can be done in C(n,m) ways and then we can map m elements in A to those m elements in B in m! ways such that every element in B has at most one pre-image.)

c)how many number of onto functions are possible from A to B?
For n > m, number of onto functions possible is 0.
For n = m, n!.
For n = 1 < m, there is one way. Call this count(m, 1).
For n = 2 < m, 2^{m} - 2(count(m,1)) = 2^{m} - 2. Call this count(m, 2).
For n = 3 < m, 3^{m} - 3(count(m,2)) - 3(count(m,1)) = 3^{m} - 3(2^{m} - 2) - 3
Inductively,
For n = m - 1,  
(n)^{m} -  C(n,n-1)(count(m,n-1)) - C(n,n-2)(count(m,n-2))  -......- C(n,1)(count(m,1))

d)how many number of bijective functions are possible from A to B?
If n ≠ m, there is none.
If n = m, its n!.

[ritu]

thanks a lot sir......i got the concept now 4 part a,b,d...:))))...can you please just give an example for part c.....???
than u sir

[Amit Goyal]

Lets say, A has 4 elements and B has just one element. Clearly, there is just one function and we know thats onto.
If A has 4 elements and B has two elements. We have 16 functions in total and we will subtract two from them to get the total number of onto functions. Thus count = 14.
If A has 4 elements and B has three elements. We have 3^4 functions in total. We will subtract from it the number of functions whose image set is exactly two elements from B and also the number of functions whose image set is exactly one element from B.
Hence 3^4 - C(3,2) 14 - C(3,1) 1 = 81 - 42 - 3 = 36

[ritu]

so the total onto functions are-....1+14+36=51 functions.....sir do we need to add the bijective functions as well in this count....ie.the case where m=n=4....4!=24....so total onto functions are 24+51=75????

thanks sir

[anon_econ]

@Ritu
u don't have to add 1, 14 & 36 to get the total number of functions. The total number of functions is EITHER 1 OR 1 OR 36, depending on the given value of n. And if n=4, the answer would be 24.

[ritu]

@vasudha ----and how do we calculate that there are 42 functions in all that have only two images in the example given by sir when n=3??????

[anon_econ]

The 2 elements that have pre-images can be either the 1st n 2nd elements or the 2nd & 3rd elements or the 1st & 3rd elements. In each of these cases, the number of functions would be the number of onto functions when n=2. So, v subtract 3x count(4,2)= 3x14=42. Hope u got it..if not u can ask what's not clear.

[ritu]

no i got it completely now....thanks dear ....ur concepts are really strong..and amit sir is gr8.:))))