Find the number of Onto functions ?

Question

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 ?

Answer 1

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)

Comments

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 :)