2.1. Show that if A and B are finite sets, Card(A^{B}) = Card(A)^{Card(B)}.

Solution. (Due to Eric Suh.) Let Card(A) = m, Card(B) = n; denote the elements of A and B by A = {a_{1}, …, a_{m}}, and B = {b_{1}, …, b_{n}}. Obvious as it is, we can “rigorously” show that A^{n} has cardinality m^{n} by constructing a bijection f : A^{n} → \overline{J}_{m^{n}}, where \overline{J}_{m^{n}} = {0, …, m^{n} − 1}, by sending (a_{i_{1}}, …, a_{i_{n}}) to a number whose base m expansion has digits i_{1} ⋯ i_{n}; every number between 0 and m^{n} − 1 has a unique base m expansion with n digits, so f is bijective. We can then map g : A^{B} → A^{n} by sending ϕ : B → A to (x_{1}, …, x_{n}), where x_{i} = ϕ(b_{i}). g is surjective, as every n-tuple x_{i} defines a function ϕ(i) = x_{i}; and if for two ϕ, ψ ∈ A^{B}, (x_{i}) = g(ϕ) = g(ψ) = (y_{i}), then ϕ(b_{i}) = x_{i} = y_{i} = ψ(b_{i}) for all i ∈ J_{n} and ψ = ϕ. thus, Card(A^{B}) = Card(\overline{J}_{m^{n}}) = m^{n}.

2.2. (i) (\begin{matrix}n \\ k \end{matrix}) = (\begin{matrix}n − 1 \\ k \end{matrix}) + (\begin{matrix}n − 1 \\ k − 1 \end{matrix})

Solution. For any S ∈ P_{k}(J_{n}), if n ∉ S we may consider S as an element of P_{k}(J_{n−1}), while if n ∈ S, S \ {n} ∈ P_{k−1}(J_{n−1}). Define a function f : P_{k}(J_{n}) → P_{k}(J_{n−1}) ⊔ P_{k−1}(J_{n−1}) by

S ∈ P_{k}(J_{n}), f(S) = \{ \begin{matrix}S & n ∉ S \\ S \ \{n\} & n ∈ S \end{matrix}

For any S ∈ P_{k}(J_{n−1}) ⊔ P_{k−1}(J_{n−1}), either S ∈ P_{k}(J_{n−1}) or S ∈ P_{k−1}(J_{n−1}); in the former case, f(S) = S, while in the latter, f(S \ {n}) = S, and thus f is surjective. For S_{1}, S_{2} ∈ P_{k}(J_{n}), suppose f(S_{1}) = f(S_{2}). If f(S_{1}) = f(S_{2}) has cardinality k, then n is in neither S_{1} nor S_{2}, and S_{1} = S_{2}, while if it has cardinality k − 1, then n is in both S_{1} and S_{2}, so S_{1} = f(S_{1}) ∩ {n} = f(S_{2}) ∩ {n} = S_{2}. f is therefore bijective, and the claim follows.

(ii) (\begin{matrix}n \\ k \end{matrix}) = (\begin{matrix}n − 1 \\ k − 1 \end{matrix}) + (\begin{matrix}n − 2 \\ k − 1 \end{matrix}) + ⋯ + (\begin{matrix}k \\ k − 1 \end{matrix}) + (\begin{matrix}k − 1 \\ k − 1 \end{matrix})

Solution. Certainly (\begin{matrix}n \\ 0 \end{matrix}) = 1 = (\begin{matrix}n \\ n \end{matrix}). Assuming the formula holds for (\begin{matrix}m \\ l \end{matrix}), m + 1 <

n + k, we have by the first part of the problem

(\begin{matrix}n \\ k \end{matrix}) = (\begin{matrix}n − 1 \\ k − 1 \end{matrix}) + (\begin{matrix}n − 1 \\ k \end{matrix}) = (\begin{matrix}n − 1 \\ k − 1 \end{matrix}) + ⋯ + (\begin{matrix}k − 1 \\ k − 1 \end{matrix})

and by induction on n, we prove the result.

(iii) (\begin{matrix}n \\ k \end{matrix}) = \frac{n!}{k!(n−k)!}

Solution. Once again, (\begin{matrix}n \\ 0 \end{matrix}) = 1 = (\begin{matrix}n \\ n \end{matrix}). If we assume the result is true for n − 1 and

all k,

(\begin{matrix}n \\ k \end{matrix}) = (\begin{matrix}n − 1 \\ k − 1 \end{matrix}) + (\begin{matrix}n − 1 \\ k \end{matrix}) = \frac{(n − 1)!}{(k − 1)!(n − k)!} + \frac{(n − 1)!}{k!(n − k − 1)!}

= \frac{n!}{k!(n − k)!} (\frac{k}{n} + \frac{n − k}{n} ) = \frac{n!}{k!(n − k)!}

2.3. Given n, p ≥ 1 compute Card{(x_{1}, …, x_{n}) ∈ ℕ^{n} | ∑_{i=1}^{n} x_{i} = p}.

Solution. We will prove that h(n, p) = (\begin{matrix}p + n − 1 \\ n − 1 \end{matrix}) by induction on n. For any p, the

number of ways h(1, p) to write p as a sum of one number is 1, p = p. Assuming the result for h(n − 1, p), note that an n-tuple (x_{1}, …, x_{n}) satisfies ∑_{i=1}^{n} x_{i} = p only if ∑_{i=1}^{n−1} x_{i} is a number q between 0 and p, and conversely for any n − 1-tuple (x_{1}, …, x_{n−1}) summing to a number p − q, 0 ≤ q ≤ p, we get an n-tuple (x_{1}, …, x_{n−1}, q) whose sum is p. There are h(n − 1, q) such n-tuples, so by the induction hypothesis

h(n, p) = ∑_{q=0}^{p} h(n − 1, q) = ∑_{q=0}^{p} (\begin{matrix}n + q − 2 \\ n − 2 \end{matrix})

= (\begin{matrix}n + p − 2 \\ n − 2 \end{matrix}) + (\begin{matrix}n + p − 3 \\ n − 2 \end{matrix}) + ⋯ + (\begin{matrix}n − 1 \\ n − 2 \end{matrix}) + (\begin{matrix}n − 2 \\ n − 2 \end{matrix}) = (\begin{matrix}n + p − 1 \\ n − 1 \end{matrix})

where the last line follows from 2.2.

If you did this problem assuming 0 ∉ ℕ, then by the same reasoning you would arrive at

h(n, p) = (\begin{matrix}p − 1 \\ n − 1 \end{matrix}).

2.4. The marriage lemma. Let W and M be finite sets. To every m ∈ M is associated a subset W_{m} ⊂ W. Show that the following are equivalent:

(1) There is an injection f : M → W such that f(m) ∈ W_{m} for every m ∈ M;

(2) For every nonempty X ⊂ M, Card(∪_{m∈X}W_{m}) ≥ Card(X).

Solution. (Due to Lisa Leung, Steve Howard, and Jamie Rubin) (1) ⇒ (2). If f : M → W is an injection, then for any X ⊂ M, Card(X) = Card(f(X)). Certainly f(X) ⊂ ∪_{m∈X}W_{m}, so Card(∪_{m∈X}W_{m}) ≥ Card(X).

(2) ⇒ (1). We prove the result be induction on Card(M). For Card(M) = 1 (say M = {m}), take any w ∈ W_{m}, and f(m) = w defines an injective function. Let Card(M) = n, and assume (2) ⇒ (1) for all M with Card(M) < n. To prove the induction step, we need the following lemma:

Lemma. Let B ⊂ M be such that Card (∪_{m∈B}W_{m}) = Card(B). Then \overline{M} = M \ B and \overline{W}_{m} = W_{m} \ (∪_{m∈B}W_{m}) satisfy (2), as do B and W_{m}.

Proof. Suppose Card(B) = k. For any nonempty X ⊂ \overline{M}, we clearly have

⋃_{m∈X} \overline{W}_{m} = ( ⋃_{m∈X∪B} W_{m}) \ ( ⋃_{m∈B} W_{m})

but Card(∪_{m∈X∪B}W_{m}) ≥ Card(X ∪ B), so that

Card ( ⋃_{m∈X} \overline{W}_{m}) ≥ Card(X ∪ B) − Card(B) = Card(X)

For any X ⊂ B, the fact that

Card ( ⋃_{m∈X} W_{m}) ≥ Card(X)

follows because M satisfies (2).

Thus, if there is a proper (nonempty) subset B ⊂ M satisfying the hypothesis of the lemma, then Card(\overline{M}) and Card(B) are both less than n, so by induction there exist injections \overline{M} → ∪_{m∈\overline{M}} \overline{W}_{m} and B → ∪_{m∈B}W_{m}. The images of the two functions are disjoint by definition, so we may juxtapose these two maps to get an injection M → W. If there is no such subset, then for any proper (again, nonempty) subset X,

Card ( ⋃_{m∈X} W_{m}) ≥ Card(X) + 1

Note that if (2) holds, then for any m_{0} ∈ M, Card(W_{m_{0}}) ≥ Card({m_{0}}) = 1, so we may pick an arbitrary w_{0} ∈ W_{m}. Let \overline{M} = M \ \{m_{0}\}, \overline{W}_{m} = W_{m} \ \{w_{0}\}. For any X ⊂ \overline{M}, we then have

Card ( ⋃_{m∈X} \overline{W}_{m}) ≥ Card ( ⋃_{m∈X} W_{m}) − 1 ≥ CardX

by the above. \overline{M} satisfies (2), so there is an injection f : \overline{M} → W \ \{w_{0}\}, and by taking f(m_{0}) = w_{0}, we get an injection f : M → W.