398
Relations, Functions, and Matrices
For any i, 0 A i 0 is the number of functions that do not map anything to t i but
have no other restrictions. By the multiplication principle, we can count the number of such functions by counting for each of the m domain elements its n − 1
possible images. The result is that 0 A i 0 = (n − 1)
m
. Therefore the first summation
in Equation (1) adds together terms that are all of the same size. There is one such
term for each distinct individual set A i out of the n sets, so there are C(n, 1) such
terms.
For any i and j, 0 A i d A j 0 is the number of functions that do not map anything
to t i or t j , leaving n − 2 possible images for each of the m elements of S. Thus
0 A i d A j 0 = (n − 2)
m
. The second summation adds one such term for each distinct
group of two sets out of n, so there are C(n, 2) such terms.
A similar result holds for all the intersection terms. If there are k sets in the
intersection, then there are (n − k)
m
functions in the intersection set and there are
C(n, k) distinct groups of k sets to form the intersection. Equation (1) can thus be
written as
0 A 1 c c c A n 0 = C(n, 1)(n − 1)
m
− C(n, 2)(n − 2)
m
+ C(n, 3)(n − 3)
m
− c + (−1)
n+1
C(n, n)(n − n)
m
(2)
Now the expression on the left of Equation (2) represents the number of all functions that fail to map to at least one of the elements of T, that is, all the non-onto
functions. If we subtract the value of this expression from the total number of
functions, which we know is n
m
, we will have the number of onto functions. Thus
the number of onto functions is
n
m
− C(n, 1)(n − 1)
m
+ C(n, 2)(n − 2)
m
− C(n, 3)(n − 3)
m
+ c + (−1)
n−1
C(n, n − 1) 3n − (n − 1) 4
m
+ (−1)
n
C(n, n)(n − n)
m
where we’ve added the next-to-last term. The last term is zero, so the final answer is
n
m
− C(n, 1)(n − 1)
m
+ C(n, 2)(n − 2)
m
− C(n, 3)(n − 3)
m
+ … + (−1)
n−1
C(n, n − 1)(1)
m
We’ll summarize these results.
theoRem on tHe nuMBeR oF FunctionS witH Finite doMainS
and codoMainS
If 0 S 0 = m and 0 T 0 = n, then
1. The number of functions f: S S T is n
m
.
2. The number of one-to-one functions f: S S T , assuming that m ≤ n, is
n!
(n − m)!
3. The number of onto functions f: S S T , assuming that m ≥ n, is
n
m
− C(n, 1)(n − 1)
m
+ C(n, 2)(n − 2)
m
− C(n, 3)(n − 3)
m
+ … + (−1)
n−1
C(n, n − 1)(1)
m
Relations, Functions, and Matrices
For any i, 0 A i 0 is the number of functions that do not map anything to t i but
have no other restrictions. By the multiplication principle, we can count the number of such functions by counting for each of the m domain elements its n − 1
possible images. The result is that 0 A i 0 = (n − 1)
m
. Therefore the first summation
in Equation (1) adds together terms that are all of the same size. There is one such
term for each distinct individual set A i out of the n sets, so there are C(n, 1) such
terms.
For any i and j, 0 A i d A j 0 is the number of functions that do not map anything
to t i or t j , leaving n − 2 possible images for each of the m elements of S. Thus
0 A i d A j 0 = (n − 2)
m
. The second summation adds one such term for each distinct
group of two sets out of n, so there are C(n, 2) such terms.
A similar result holds for all the intersection terms. If there are k sets in the
intersection, then there are (n − k)
m
functions in the intersection set and there are
C(n, k) distinct groups of k sets to form the intersection. Equation (1) can thus be
written as
0 A 1 c c c A n 0 = C(n, 1)(n − 1)
m
− C(n, 2)(n − 2)
m
+ C(n, 3)(n − 3)
m
− c + (−1)
n+1
C(n, n)(n − n)
m
(2)
Now the expression on the left of Equation (2) represents the number of all functions that fail to map to at least one of the elements of T, that is, all the non-onto
functions. If we subtract the value of this expression from the total number of
functions, which we know is n
m
, we will have the number of onto functions. Thus
the number of onto functions is
n
m
− C(n, 1)(n − 1)
m
+ C(n, 2)(n − 2)
m
− C(n, 3)(n − 3)
m
+ c + (−1)
n−1
C(n, n − 1) 3n − (n − 1) 4
m
+ (−1)
n
C(n, n)(n − n)
m
where we’ve added the next-to-last term. The last term is zero, so the final answer is
n
m
− C(n, 1)(n − 1)
m
+ C(n, 2)(n − 2)
m
− C(n, 3)(n − 3)
m
+ … + (−1)
n−1
C(n, n − 1)(1)
m
We’ll summarize these results.
theoRem on tHe nuMBeR oF FunctionS witH Finite doMainS
and codoMainS
If 0 S 0 = m and 0 T 0 = n, then
1. The number of functions f: S S T is n
m
.
2. The number of one-to-one functions f: S S T , assuming that m ≤ n, is
n!
(n − m)!
3. The number of onto functions f: S S T , assuming that m ≥ n, is
n
m
− C(n, 1)(n − 1)
m
+ C(n, 2)(n − 2)
m
− C(n, 3)(n − 3)
m
+ … + (−1)
n−1
C(n, n − 1)(1)
m