top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find the number of Onto functions ?

+1 vote

There is a( function F) : A to B such that set A has 10 elements and set B has 4 elements . Find the number of Onto functions ?

posted Jun 5, 2015 by Ankit Kamboj

Share this puzzle
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+1 vote
Best answer

A function f from A to B is called onto if for all b in B there is an a in A such that f (a) = b. All elements in B are used.

If A and B are two sets having m and n elements respectively such that 1≤n≤m then number of onto function from A to B is

∑ (-1)^(n-r) nCr r^m r vary from 1 to n

now m = 10 and n = 4 so total number of onto functions are
(-1)^3 4C1 (1)^10 + (-1)^2 4C2 (2)^10 + (-1)^1 4C3 (3)^10 + (-1)^0 4C4 (4)^10
= -1*4*1 + 6*(2^10) - 4 * (3^10) + 4^10
= 818520

(Though not sure if formula is correct found it on net)

answer Jun 7, 2015 by Salil Agrawal
Yes Sir  for small values of m and n we can use distribution like that in  p&c , but for large values i think formula would be the last alternative , before we could find some other way to get the solution.
Thanks Ankit for asking great questions.
Glad to help :)