768 Combinatorics and Probability
paths pass through(r, s). To apply the inclusion–exclusion principle, we also need to
count the number of paths that go simultaneously through(p, q)and(r, s). This number is
(
p+q
q
)
·
(
r+s−p−q
s−q)
·
(
m+n−r−s
n−s)
.
Hence, by the inclusion–exclusion principle, the number of paths avoiding(p, q)and
(r, s)is
(
m+n
n
)
−
(
p+q
q)
·
(
m+n−p−q
n−q)
−
(
r+s
s)
·
(
m+n−r−s
n−s)
+
(
p+q
q)
·
(
r+s−p−q
s−q)
·
(
m+n−r−s
n−s)
.
899.LetE={ 1 , 2 ,...,n}andF={ 1 , 2 ,...,p}.There arepnfunctions fromEtoF.
The number of surjective functions ispn−N, whereNis the number of functions that
are not surjective. We computeNusing the inclusion–exclusion principle.
Define the sets
Ai={f:E→F|i/∈f(E)}.Then
N=∣
∣∪pi= 1 Ai∣
∣=
∑
i|Ai|−∑
i =j∣
∣Ai∩Aj∣
∣+···+(− 1 )p−^1∣
∣∩pi= 1 Ai∣
∣.
ButAiconsists of the functions fromEtoF{i}; hence|Ai|=(p− 1 )n. Similarly, for all
k,2≤k≤p−1,Ai 1 ∩Ai 2 ∩···∩Aikis the set of functions fromEtoF{i 1 ,i 2 ,...,ik};
hence|Ai 1 ∩Ai 2 ∩···∩Aik|=(p−k)n. Also, note that for a certaink, there are
(p
k)
terms of the form|Ai 1 ∩Ai 2 ∩···∩Aik|. It follows that
N=
(
p
1)
(p− 1 )n−(
p
2)
(p− 2 )n+···+(− 1 )p−^1(
p
p− 1)
.
We conclude that the total number of surjections fromEtoFispn−(
p
1)
(p− 1 )n+(
p
2)
(p− 2 )n−···+(− 1 )p(
p
p− 1)
.
900.We count instead the permutations that are not derangements. Denote byAithe set
of permutationsσwithσ(i)=i. Because the elements inAihave the value atialready
prescribed, it follows that|Ai|=(n− 1 )!. And for the same reason,|Ai 1 ∪Ai 2 ∪···∪Aik|=
(n−k)!for any distincti 1 ,i 2 ,...,ik,1≤k≤n. Applying the inclusion–exclusion
principle, we find that