Let A = {1, 2, 3, ...n} and B = {a, b}. Then the number of surjections from A into B is
Given that, A = {1, 2, 3, ...n} and B = {a, b}
Number of elements in A = n
Number of elements in B = 2
No. of possible function from A → B is n2 (i.e. number of possible ways n elements of A can be mapped to 2 elements of B.
Now, not all of these functions are surjective.
we know that function f : A → B is surjective if both the elements of B are mapped.
Out of these n2 functions there will be two functions where all the elements of A are mapped to first element of B and where all the elements of A are mapped to second element of B, those functions are not surjective.
⇒ number of surjective functions from A → B are n2 – 2.