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.

We have a circular table with \(2n+1\) identical chairs. We want to seat \(n\) math majors, \(n\) philosophy majors, and one dog.

1. In how many ways can this be done if no math major can sit next to a math major, and no philosophy major can sit next to a philosophy major?

2. In how many ways can this be done if no math major can sit next to a math major?

7.

Bertie Bott's Every Flavour Beans come in the following 20 flavors: Banana, Black Pepper, Blueberry, Booger, Candyfloss, Cherry, Cinnamon, Dirt, Earthworm, Earwax, Grass, Green Apple, Lemon, Marshmallow, Rotten Egg, Sausage, Soap, Tutti-Fruitti, Vomit, Watermelon.

Bertie's Beans are packaged in bags of 50, but there is no guarantee as to how the flavours will be distributed. You might get a mixture of all 20 flavours, or just some Earwax and Vomit, or just Blueberry.

Answer the following questions by explicitly mapping each situation to a balls-and-boxes problem.

1. How many ways are there to fill a bag of Bertie Bott's Every Flavour Beans?

2. How many ways are there to fill a bag if we must distribute the flavors as evenly as possible? In other words, the bag contains either 2 or 3 jellybeans of each flavour?

3. I have one bean from each of the 20 flavours. I want to give them away to the 7 members of my quidditch team such that every team member gets at least one bean. How many different ways can I do this?

8.

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.

9.

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*}

10.

A stack sortable permutation is a permutation \(\pi = (\pi_1, \pi_2, \ldots, \pi_n)\) in which the entries can be placed one by one in a stack (always in descending order from bottom to top) and removed (from top to bottom) to ultimately yield the identity permutation \((1,2,\ldots,n)\text{.}\) This is perhaps more easily understood through example. The following figure shows that the permutation (3,1,2) is stack sortable.

This example begins with the permutation \((3,1,2)\text{.}\) We first place 3 in the stack, followed by 1. We then move the 1 to the output because we cannot place 2 on top of 1. We repeat this process again with 2 and finally remove 3. The output is the identity permutation \((1,2,3)\text{.}\)

1. There is one permutation of \([3]\) that is NOT stack sortable. What is it? (Note that this means that there are \(3!-1 = 6-1=5\) stack sortable permutations of \([3]\text{.}\))

2. There are 14 stack sortable permutations of \([4]\text{.}\) Find them all.

3. Let \(S_n\) denote the number of stack sortable permutatations of \([n]\text{.}\) Prove that \(S_n\) satisfies the Catalan recurrence

   \begin{equation*} S_n = S_0 S_{n-1} + S_1 S_{n-2} + \cdots + S_{n-1} S_0 = \sum_{k=0}^{n-1} S_k S_{n-1-k}. \end{equation*}

11.

There are two ways perform the multiplication \(abc\text{,}\) namely \((ab)c\) and \(a(bc)\text{.}\) We just need to decide how to add parentheses, which determines the order that we multiply these terms together.

1. List the 5 ways to add parentheses to the product \(abcd\text{.}\)

2. List the 14 ways to add parentheses to the product \(abcde\text{.}\)

3. Find a bijection from "trianglulating a convex \((n+2)\)-gon" to "parenthesizing a product of \(n+1\) symbols". I have started this process for you on the 5-gons below. I have labelled 4 of the 5 outer edges by the symbols \(a,b,c,d\text{.}\) Use these labels to create a natural label for each diagonal, one at a time. Finally, this will lead to a natural labeling of the unlabeled outer edge.

   

   Complete this labeling process for the 5 pentagons above. Then give a general explanation for what to do with an \((n+2)\)-gon. Give a convincing argument that you will eventually be able to label every diagonal, as well as labelling the final side of the original polygon.