s
Section 5.4 Functions
399
If A is a set with 0 A0 = n, then the number of permutations of A is n!. This
number can be obtained by any of three methods:
1. A combinatorial argument (each of the n elements in the domain must map
to one of the n elements in the range with no repetitions)
2. Thinking of such functions as permutations on a set with n elements and
noting that P(n, n) = n!
3. Using result (2) in the previous theorem with m = n
We propose to count the number of derangements on A. Our plan is similar
to the one we used in counting onto functions. We’ll use the principle of inclusion
and exclusion to compute the number of permutations that are not derangements
and then subtract this value from the total number of permutation functions.
Enumerate the elements of set A as a 1 , … , a n . For each i, 1 ≤ i ≤ n, let A i
be the set of all permutations that leave a i fixed. (These sets are not disjoint, but
every permutation that is not a derangement 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
(3)
For any i, 0 A i 0 is the number of permutations that leave a i fixed. By the multiplication principle we can count the number of such functions by counting for
each of the n domain elements, beginning with a i , its possible images. There is
only one choice of where to map a i because it must map to itself; the next element
can map anywhere except to a i , so there are n − 1 outcomes; the next element can
map anywhere except the two images already used, so there are n − 2 outcomes,
and so on. Continuing, there are
(1)(n − 1)(n − 2) c (1) = (n − 1)!
example 41
Let S = 5A, B, C6 and T = 5a, b6. Find the number of functions from S onto T.
Here m = 3 and n = 2. By our theorem on the number of functions, there are
2
3
− C(2, 1)(1)
3
= 8 − 2 # 1 = 6
such functions.
PRaCtiCe 38 One of the six onto functions in Example 41 can be illustrated by the following diagram:
A
B
C
a
b
Draw diagrams for the remaining five onto functions.
■
Section 5.4 Functions
399
If A is a set with 0 A0 = n, then the number of permutations of A is n!. This
number can be obtained by any of three methods:
1. A combinatorial argument (each of the n elements in the domain must map
to one of the n elements in the range with no repetitions)
2. Thinking of such functions as permutations on a set with n elements and
noting that P(n, n) = n!
3. Using result (2) in the previous theorem with m = n
We propose to count the number of derangements on A. Our plan is similar
to the one we used in counting onto functions. We’ll use the principle of inclusion
and exclusion to compute the number of permutations that are not derangements
and then subtract this value from the total number of permutation functions.
Enumerate the elements of set A as a 1 , … , a n . For each i, 1 ≤ i ≤ n, let A i
be the set of all permutations that leave a i fixed. (These sets are not disjoint, but
every permutation that is not a derangement 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
(3)
For any i, 0 A i 0 is the number of permutations that leave a i fixed. By the multiplication principle we can count the number of such functions by counting for
each of the n domain elements, beginning with a i , its possible images. There is
only one choice of where to map a i because it must map to itself; the next element
can map anywhere except to a i , so there are n − 1 outcomes; the next element can
map anywhere except the two images already used, so there are n − 2 outcomes,
and so on. Continuing, there are
(1)(n − 1)(n − 2) c (1) = (n − 1)!
example 41
Let S = 5A, B, C6 and T = 5a, b6. Find the number of functions from S onto T.
Here m = 3 and n = 2. By our theorem on the number of functions, there are
2
3
− C(2, 1)(1)
3
= 8 − 2 # 1 = 6
such functions.
PRaCtiCe 38 One of the six onto functions in Example 41 can be illustrated by the following diagram:
A
B
C
a
b
Draw diagrams for the remaining five onto functions.
■