Problem
COM-B2-M02-P013 General Formula for Surjections
#13
★★★★☆ Level 4 of 5
Prove that the number of onto functions from an \(n\)-element set to an \(m\)-element set is \(\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n\).
Forbidden event: a chosen value is not used.
There are \(m^n\) functions in total. If \(i\) values are chosen to be unused, then all \(n\) domain elements must map to the remaining \(m-i\) values: \((m-i)^n\) functions. The \(i\) unused values can be chosen in \(\binom mi\) ways. Alternating signs by inclusion-exclusion gives the formula.
Shows that a surjection is the absence of empty values.