s
Section 5.4 Functions
397
How Many Functions
Suppose S and T are finite sets, say 0 S 0 = m and 0 T 0 = n. What can we say about
the number of functions with various properties that map S to T? First, let’s just
count the number of functions f : S S T , assuming no special properties about
the functions. The multiplication principle can be used here because we can think
of defining a function by assigning an image to each of the m elements of S. This
gives us a sequence of m tasks. Each task has n outcomes because each element of
S can map to any element in T. Therefore the number of functions is
0 n × n × n × c × n 0 = n
m
0
m factors
How many one-to-one functions are there from S to T? We must have m ≤ n
or we can’t have any one-to-one functions at all. (All the elements of S must be
mapped to T, and if m > n there are too many elements in S to allow for a oneto-one mapping. Actually, this is the pigeonhole principle at work.) We can again
solve this problem by carrying out the sequence of tasks of assigning an image to
each element in S, but this time we cannot use any image we have used before. By
the multiplication principle, we have a product that begins with the factors
n(n − 1)(n − 2) c
and must contain a total of m factors, so the result is
n(n − 1)(n − 2) c 3n − (m − 1) 4 = n(n − 1)(n − 2) c (n − m + 1)
=
n!
(n − m)!
= P(n,m)
How many onto functions are there from S to T? This time we must have
m ≥ n so that there are enough values in the domain to provide preimages for
every value in the codomain. (By the definition of a function, an element in S cannot be a preimage of more than one element in T.) Our overall plan is to subtract
the number of non-onto functions from the total number of functions, which we
know. To count the number of non-onto functions, we’ll use the principle of inclusion and exclusion.
Enumerate the elements of set T as t 1 , … , t n . For each i, 1 ≤ i ≤ n, let A i denote the set of functions from S to T that do not map anything to element t i . (These
sets are not disjoint, but every non-onto function belongs to at least one such set.)
By the principle of inclusion and exclusion, we can write
0 A 1 c c c A n 0 = ∙
1≤i≤n
0 A i 0 − ∙
1≤i
∙
1≤i
− c + (−1)
n+1
0 A 1 d c d A n 0
(1)
Section 5.4 Functions
397
How Many Functions
Suppose S and T are finite sets, say 0 S 0 = m and 0 T 0 = n. What can we say about
the number of functions with various properties that map S to T? First, let’s just
count the number of functions f : S S T , assuming no special properties about
the functions. The multiplication principle can be used here because we can think
of defining a function by assigning an image to each of the m elements of S. This
gives us a sequence of m tasks. Each task has n outcomes because each element of
S can map to any element in T. Therefore the number of functions is
0 n × n × n × c × n 0 = n
m
0
m factors
How many one-to-one functions are there from S to T? We must have m ≤ n
or we can’t have any one-to-one functions at all. (All the elements of S must be
mapped to T, and if m > n there are too many elements in S to allow for a oneto-one mapping. Actually, this is the pigeonhole principle at work.) We can again
solve this problem by carrying out the sequence of tasks of assigning an image to
each element in S, but this time we cannot use any image we have used before. By
the multiplication principle, we have a product that begins with the factors
n(n − 1)(n − 2) c
and must contain a total of m factors, so the result is
n(n − 1)(n − 2) c 3n − (m − 1) 4 = n(n − 1)(n − 2) c (n − m + 1)
=
n!
(n − m)!
= P(n,m)
How many onto functions are there from S to T? This time we must have
m ≥ n so that there are enough values in the domain to provide preimages for
every value in the codomain. (By the definition of a function, an element in S cannot be a preimage of more than one element in T.) Our overall plan is to subtract
the number of non-onto functions from the total number of functions, which we
know. To count the number of non-onto functions, we’ll use the principle of inclusion and exclusion.
Enumerate the elements of set T as t 1 , … , t n . For each i, 1 ≤ i ≤ n, let A i denote the set of functions from S to T that do not map anything to element t i . (These
sets are not disjoint, but every non-onto function belongs to at least one such set.)
By the principle of inclusion and exclusion, we can write
0 A 1 c c c A n 0 = ∙
1≤i≤n
0 A i 0 − ∙
1≤i
∙
1≤i
− c + (−1)
n+1
0 A 1 d c d A n 0
(1)