| Author |
Message |
![[Post New]](/templates/default/images/icon_minipost_new.gif) 18 May 2007 20:27:40 IST
|
|
|
the number of onto functions that can b formed from a finite set containing n elements and a finite set containing 2 elements is??
xplain
|
    
Animated Letters
it is good to hav an end to journey but its d journy that mattrs in the end |
|
|
|
18 May 2007 20:46:58 IST
|
|
|
You mean "from a finite set containing n elements to a finite set containing 2 elements"
|
this reply: 0 points
(with 0 
in 0 votes ) [?]
|
|
You have to be logged on to rate
|
|
|
18 May 2007 20:48:36 IST
|
|
|
yes
|
Animated Letters
it is good to hav an end to journey but its d journy that mattrs in the end |
this reply: 0 points
(with 0
in 0 votes ) [?]
|
|
You have to be logged on to rate
|
|
|
19 May 2007 01:06:32 IST
|
|
|
As the functions to be formed are onto, the two elements in the co-domain set must have at least one pre-image.
For the first of these two elements, the number of ways of selecting a pre-image is n & for the second element is n-1
No. of ways of selecting one distinct pre-image is n(n-1).
The rest n-2 elements in the domain set can link to either of the two elements in the co-domain set. Basically the problem reduces to dividing this set of n-2 elements into two sets, each containing atleast one element. The number of ways to do this is n-3.
Hence the total number of ways to do this is n(n-1)(n-3)
This formula is valid only for n>3.
For n=1, no onto functions are possible.
For n =2, only one onto function is possible.
For n= 3, the no. of ways of selecting one preimage for the two elements is 3x2 = 6. For the remaining one element in the domain there are only two choices. Hence the total number of functions is 6 x 2 = 12. But out of these only 6 are distinct.
|
|
this reply: 2 points
(with 0
in 1 votes ) [?]
|
|
You have to be logged on to rate
|
|
|
19 May 2007 07:10:54 IST
|
|
|
pls give the generalised solution
the ans is 2n -2
|
Animated Letters
it is good to hav an end to journey but its d journy that mattrs in the end |
this reply: 0 points
(with 0
in 0 votes ) [?]
|
|
You have to be logged on to rate
|
|
|
19 May 2007 13:01:04 IST
|
|
|
Well I went way wrong with that. Sorry dude ... the occasional slip !
The number of ways in which each element in the domain can be linked to either of the two elements in the co-domain = 2n
Now, there are two possibilities that we must overrule to make it onto, that no element in the co-domain is devoid of a pre-image. The above linkings will have 2 such cases, when either one of the elements in the codomain is unlinked.
So total number of onto functions = 2n -2
|
|
this reply: 0 points
(with 0
in 0 votes ) [?]
|
|
You have to be logged on to rate
|
|
|
|
|
Moderation Team
![[Up]](/templates/default/images/icon_up.gif "[Up]"){kind=icon}
