Derive a closed formula representing the number of surjectiv

Derive a closed formula representing the number of surjective (onto) functions from the set A = {1, 2, 3, ... , n} of first n positive integers to the set B = {0, 1} . Your formula must be expressed in terms of n. Explain briefly why your formula is correct. No formal proof is required.

Solution

total number of functions from A to B

= 2^n

Exclude the two functions which map all elements of A to single element of B

So the required number of functions are

2^n-2

The number of ways to distribute n elements into m non-empty sets is given by the Stirling numbers of the second kind, S(n,m). However, each element of A can be associated with any of these sets, so you pick up an extra factor of n!: the total number for surjective functions should be S(n,m)m!

and S(n,2) = 2^{n-1}-1

Hence total number = 2^n - 2

.