HOMEWORK 6 PARTIAL SOLUTIONS - MA109
III.16: We apply the inclusion-exclusion principle to count the non-surjections from [m] to [n].
Given i ∈ [n], set Ai = {f ∈ [n][m] : i 6∈ Im(f)}, and given a non-empty S ⊆ [n], set AS =⋂
i∈S Ai = {f ∈ [n][m] : Im(f) ∩ S = ∅}. The key observation is that AS can be identified with
the set of functions from [m] to [n] \ S, and by Proposition 12.1.2, there are (n− |S|)m many such
functions. The inclusion-exclusion principle gives us:
|
⋃
i∈[n]
Ai| =
∑
S∈P+([n])
(−1)|S|−1|AS |
=
∑
S∈P+([n])
(−1)|S|−1(n− |S|)m
=
n∑
k=1
(−1)k−1
(
n
k
)
(n− k)m
The last summand is zero, so we can omit it. As the above counts non-surjections, and as nm
counts the total number of functions from [m] to [n], we obtain the formula asked for in Eccles for
the number of surjections. When m = n, every surjection is a bijection, and we obtain the desired
formula for n!.
III.17: We apply the inclusion-exclusion principle to count the non-derangements from [n] to [n].
If X is a set, write Sym(X) for the set of permutations of X. Given i ∈ [n], set Ai = {f ∈ Sym([n]) :
f(i) = i}, and given a non-empty S ⊆ [n], set AS =
⋂
i∈S Ai. The key observation is that AS can
be identified with Sym([n] \ S), implying that |AS | = (n− |S|)!. The inclusion-exclusion principle
gives us:
|
⋃
i∈[n]
Ai| =
∑
S∈P+([n])
(−1)|S|−1|AS |
=
∑
S∈P+([n])
(−1)|S|−1(n− |S|)!
=
n∑
k=1
(−1)k−1
(
n
k
)
(n− k)!
=
n∑
k=1
(−1)k−1n!
k!
As the above counts non-derangements, and as n! counts the total number of permutations of [n],
we obtain the formula asked for in Eccles for the number of derangements.
1
2 HOMEWORK 6 PARTIAL SOLUTIONS - MA109
III.18: Let X and Y be disjoint sets, and let f :
⋃k
i=0 Pi(X) × Pk−i(Y ) → Pk(X ∪ Y ) be the
function given by f(A,B) = A ∪ B. To see that f is bijective, we show that f is invertible.
Let g : Pk(X ∪ Y ) →
⋃k
i=0 Pi(X) × Pk−i(Y ) be defined via g(S) = (S ∩ X,S ∩ Y ). Then given
S ∈ Pk(X ∪ Y ), we have
f ◦ g(S) = f(S ∩X,S ∩ Y ) = (S ∩X) ∪ (S ∩ Y ) = S ∩ (X ∪ Y ) = S.
And given i ≤ k, A ∈ Pi(X) and B ∈ Pk−i(Y ), we have
g ◦ f(A,B) = g(A ∪B) = ((A ∪B) ∩X, (A ∪B) ∩ Y ) = (A,B).
Hence f and g are inverses, showing that f is bijective. The identity for
(
m+n
k
)
given in Eccles now
follows.
Remark : Another approach to prove f is bijective is to prove that f is both injective and surjective.
The alternate proof by induction is omitted from these solutions.
Starred problem:
Let m,n ∈ N. We say that a function f : [m] → [n] is non-decreasing if whenever i ≤ j ∈ [m], we
have f(i) ≤ f(j). Write ND([m], [n]) for the set of non-decreasing functions from [m] to [n].
What is |ND([m], [n])|? Give a formula, and prove that your formula is correct.
The correct formula is
(
n+m−1
m
)
.
Proof by induction: We give an induction on n. Let P (n) be the formula
∀m ∈ N
[
|ND([m], [n])| =
(
n+m− 1
m
)]
.
Base case: P (1) is the statement that for every m ∈ N, we have |ND([m], [1])| = (mm). Let m ∈ N.
Since there is only one function from [m] to [1], and as this function is non-decreasing, we see that
|ND([m], [1]) = 1. Hence P (1) is true.
Inductive step: Let k ∈ N, and assume that P (k) holds. Towards showing that P (k + 1) holds,
let m ∈ N. Given i ∈ [m] ∪ {0}, set
Xi = {f ∈ ND([m], [k + 1]) : f−1[[k]] = [i]}.
So ND([m], [k + 1]) =
⋃m
i=0Xi, and this union is disjoint. For i > 0, we can identify Xi with
ND([i], [k]). By our inductive hypothesis P (k), we have |Xi| =
(
k+i−1
i
)
. For i = 0, X0 contains
exactly one function, the function sending every element of [m] to the element k+ 1, so we can also
write |X0| =
(
k+0−1
0
)
. The proof of P (k + 1) will be finished once we prove the following lemma,
which is often called the “hockey stick” lemma (the relevant entries in Pascal’s triangle look a bit
like a hockey stick).
Lemma 0.1.
∑m
i=0
(
k+i−1
i
)
=
(
k+m
m
)
.
Proof. We give a sketch of a bijective proof. Given S ∈ Pm([k + m]), let j = max([k + m] \ S).
Note that j ≥ k. Then S ∩ [j − 1] ∈ Pj−k([j − 1]). Upon re-indexing by setting i = j − k, we
have S ∩ [k + i− 1] ∈ Pi([k + i− 1]). Then the map S → (i, S ∩ [k + i− 1]) is a bijection between
Pm(k +m) and
⋃m
i=0{i} × Pi([k + i− 1]).

欢迎咨询51作业君