Calculating The Total Number Of Surjective Functions
Answer : Consider f − 1 ( y ) f^{-1}(y) f − 1 ( y ) , y ∈ Y y \in Y y ∈ Y . This set must be non-empty, regardless of y y y . What you're asking for is the number of ways to distribute the elements of X X X into these sets. The number of ways to distribute m elements into n non-empty sets is given by the Stirling numbers of the second kind, S ( m , n ) S(m,n) S ( m , n ) . However, each element of Y Y Y can be associated with any of these sets, so you pick up an extra factor of n ! n! n ! : the total number should be S ( m , n ) n ! S(m,n) n! S ( m , n ) n ! The Stirling numbers have interesting properties. They're worth checking out for their own sake. Here is a solution that does not involve the Stirling numbers of the second kind, S ( n , m ) S(n,m) S ( n , m ) . The number of surjective functions from a set X X X with m m m elements to a set Y Y Y with n n n elements is ∑ i = 0 n − 1 ( − 1 ) i ( n i ) ( n − i ) m \sum_{i=0}^{n-1} (-1)^i{n \choose i}(n-i)^m...