Page 582 - Discrete Mathematics and Its Applications

8.6 Applications of Inclusion–Exclusion 561

a function is onto if and only if it has none of the properties P 1 ,P 2 ,or P 3 . By the inclusion–
exclusion principle it follows that the number of onto functions from a set with six elements to
a set with three elements is

N(P P P ) = N −[N(P 1 ) + N(P 2 ) + N(P 3 )]
1 2 3
+[N(P 1 P 2 ) + N(P 1 P 3 ) + N(P 2 P 3 )]− N(P 1 P 2 P 3 ),
where N is the total number of functions from a set with six elements to one with three elements.
We will evaluate each of the terms on the right-hand side of this equation.
6
From Example 6 of Section 6.1, it follows that N = 3 . Note that N(P i ) is the number of
functions that do not have b i in their range. Hence, there are two choices for the value of the
6
function at each element of the domain. Therefore, N(P i ) = 2 . Furthermore, there are C(3, 1)
terms of this kind. Note that N(P i P j ) is the number of functions that do not have b i and b j
in their range. Hence, there is only one choice for the value of the function at each element of
6
the domain. Therefore, N(P i P j ) = 1 = 1. Furthermore, there are C(3, 2) terms of this kind.
Also, note that N(P 1 P 2 P 3 ) = 0, because this term is the number of functions that have none
of b 1 ,b 2 , and b 3 in their range. Clearly, there are no such functions. Therefore, the number of
onto functions from a set with six elements to one with three elements is

6
6
6
3 − C(3, 1)2 + C(3, 2)1 = 729 − 192 + 3 = 540.
▲
The general result that tells us how many onto functions there are from a set with m elements
to one with n elements will now be stated. The proof of this result is left as an exercise for the
reader.

THEOREM 1 Let m and n be positive integers with m ≥ n. Then, there are

m
m
m
n − C(n, 1)(n − 1) + C(n, 2)(n − 2) − ··· + (−1) n−1 C(n, n − 1) · 1 m
onto functions from a set with m elements to a set with n elements.

An onto function from a set with m elements to a set with n elements corresponds to a
way to distribute the m elements in the domain to n indistinguishable boxes so that no box is
empty, and then to associate each of the n elements of the codomain to a box. This means that
the number of onto functions from a set with m elements to a set with n elements is the number
Counting onto functions
of ways to distribute m distinguishable objects to n indistinguishable boxes so that no box is
is much harder than
counting one-to-one empty multiplied by the number of permutations of a set with n elements. Consequently, the
functions! number of onto functions from a set with m elements to a set with n elements equals n!S(m, n),
where S(m, n) is a Stirling number of the second kind defined in Section 6.5. This means that
we can use Theorem 1 to deduce the formula given in Section 6.5 for S(m, n). (See Chapter 6
of [MiRo91] for more details about Stirling numbers of the second kind.)
One of the many different applications of Theorem 1 will now be described.

EXAMPLE 3 How many ways are there to assign five different jobs to four different employees if every
employee is assigned at least one job?

Solution: Consider the assignment of jobs as a function from the set of five jobs to the set of
four employees. An assignment where every employee gets at least one job is the same as an