Enumerative Combinatorics: Activities and Exercises

1.

Consider an integer lattice \(L\) of points given by

Show that no matter how we color the points using three colors (red, blue, yellow), there is a "monochromatic rectangle" whose corner points all get the same color.

(Hint: you have to use the Pigeonhole Principle twice. First, look at a single row. What can you conclude about the colors? Next, look at the set \(S\) of all rows in \(L\) (with their colorings). What can you conclude about the set \(S\text{?}\))

2.

Show that if 51 integers are chosen from \([100] = \{1,2, \ldots, 100 \}\) then there must be two of them with the property that one is divisible by the other.

(Hint: Write each \(a \in [100]\) as \(a=2^k b\) where \(k \geq 0\) and \(b\) is an odd number. You are now ready to use the Pigeonhole Principle.)

3.

Suppose that f: \(A \rightarrow B\) and \(g: B \rightarrow C\) are functions.

1. If \(g \circ f\) is injective and \(f\) is surjective, then show that \(g\) is injective.

2. If \(g \circ f\) is surjective and \(g\) is injective, then show that \(f\) is surjective.

4.

Let \(k \leq n\) be positive integers. Find a bijection \(f : A \rightarrow B\) between the following sets.

• \(A =\) all words of length n using the alphabet \(\{0,1,2,...,k\}\)

• \(B =\) all lists \((S_1, S_2, \cdots , S_k)\) where each \(S_i\) is a subset of \([n]\) and \(S_1 \subset S_2 \subset \cdots \subset S_k\text{.}\) And remember: \(X \subset Y\) means that \(X \subseteq Y\text{.}\)

Justify why your function is a bijection.

5.

We have defined the size \(|A|\) of a set to be the number of elements in \(A\text{.}\) In fact, what we are saying is that \(|A| = m\) if any only if there is a bijection \(f: A \rightarrow [m]\text{.}\) Let \(A\) and \(B\) be disjoint sets (so that \(|A \cap B| = \emptyset\)). Suppose that \(|A|=m\) and \(|B| = n\text{,}\) and that \(f: A \rightarrow [m]\) is a bijection and that \(g: B \rightarrow [n]\) is a bijection.

1. Give a bijective proof of the addition rule

   \begin{equation*} |A \cup B| = |A| + |B|. \end{equation*}

   In other words, find a bijective function \(h : A \cup B \rightarrow [m+n]\text{.}\) You can simply construct the function. You do not need to prove it is a bijection.

2. Give a bijective proof of the product rule

   \begin{equation*} |A \times B| = |A| \cdot |B|. \end{equation*}

   In other words, find a bijective function \(h : A \times B \rightarrow [mn]\text{.}\) You can simply construct the function. You do not need to prove it is a bijection.

6.

Let \(R(n,k)\) be the number of ways to partition the set \([n]\) into \(k\) parts so that each part contains only even numbers or only odd numbers. For example, we have \(R(1,1)=1\text{,}\) \(R(2,1)=0\) and \(R(2,2)=1\text{.}\) For \(n \geq 3\) and \(k \geq 2\text{,}\) find a formula for \(R(n,k)\) in terms of Stirling numbers of the second kind.

7.

Let \(\mbox{q}(n,k)\) denote the number of partitions of integer \(n\) into \(k\) distinct parts. The initial values are

1. Explain why \(q(n,k) >0\) if and only if \(n \geq {k+1 \choose 2}\text{.}\)

2. Prove that if \(n \geq 2\) and \(q(n,k) >0\) then

   \begin{equation*} q(n,k) = q(n-k,k) + q(n-k, k-1). \end{equation*}