DM-Sets,Relations and Functions-Q15

+2 votes

Number of onto functions from set on n elements (n>2) to set of 3 elements?

(A). 3^n-3

(B). 3^n-3.2^n-3

(C). 3^n-3.2^n+3

(D). 3^n-2^n-13

asked Jul 5 in Discrete Maths by gbeditor (21,290 points)
reshown Jul 6 by gbeditor

2 Answers

+4 votes
Best answer
This can be done using inclusion and exclusion principles.

Total functions: 3^n

Now, we find the number of functions which are not onto.

Case 1: One element of RHS is not mapped. Every element in LHS will have two choices, hence 2^n, 3 times.

Case 2: Two elements of RHS are not mapped. Every element in LHS will have only one choice. Hence, 1.3

Case 3: Three elements of RHS are not mapped. Zero functions possible.

Hence, answer will be 3^n - 3.2^n + 3
answered Jul 6 by tsgokulnath136 (4,780 points)
selected Jul 8 by getgatebook
yes nice approach
just take n=3, number of onto functions should be 6.
put 3 in options and check, only C satisfies
+1 vote
if |A|=m and |B|=n

the no of onto function is :  n^m - nc1(n-1)^m + nc2(n-2)^m - nc3(n-3)^m+......................

        ATQ |A|=n and |B|=3

so no of onto function= 3^n - 3c1(3-1)^n  + 3c2(3-2)^n-3c3(3-3)^m=3^n-3.2^n+3
answered Jul 6 by tscontactadarshkumar (8,470 points)