Math 301: Homework 1

Due: Friday, September 6, 2019

While you don’t have to write formal proofs for many solutions, if you’re only writing symbols, you’re not explaining things. Make sentences by adding in a few English words to explain your reasoning to me.

  1. How many ways are there to pair up 5 students into two groups of two (leaving one odd-student-out)?

    There are \(\binom 5 2\) ways to form a first pair, then \(\binom 3 2\) to form the second pair. There are 2 pairs, and their order doesn’t matter, so the answer is:

    \[ \binom 52 \binom 32 \frac{1}{2!} \]

  2. How many subsets does that set \(A = \{1,2,3,4,5\}\) have? How many of the subsets have cardinality 3?

    There are \(2^{\vert A \vert} = 2^{5}\) subsets of \(A\), of which \(\binom 5 3\) have cardinality 3.

  3. Let \(A\) and \(B\) be sets. If \(A \cap B = \emptyset\), what is \(A \setminus B\)? \(A \Delta B\)?

    As they are disjoint, \(A \setminus B = A\) and \(A \Delta B = A \cup B\).

  4. Explain why \(\vert A \cap B \vert + \vert A \cup B \vert = \vert A \vert + \vert B \vert\). A picture will help.

    We’ll use the fact that if \(S, T\) are disjoint then \(\vert S \cup T \vert = \vert S \vert + \vert T \vert\).

    First notice that \((A \setminus B)\) and \((A \cap B)\) are disjoint and \((A \setminus B) \cup (A \cap B) = A \). So \(\vert A \vert = \vert A \setminus B \vert + \vert A \cap B \vert\). For similar reasons, \(\vert B \vert = \vert B \setminus A \vert + \vert A \cap B \vert\).

    Now notice that \(A \cup B = (A \setminus B) \cup (A \cap B) \cup (B \setminus A)\), where the three sets on the right hand side are all disjoint. So:

    \[\begin{align*} \vert A \cup B \vert &= \vert A \setminus B \vert + \vert A \cap B \vert + \vert B \setminus A\vert \\ &= \vert A \vert + \vert B \setminus A \vert \\ &= \vert A \vert + \vert B \setminus A \vert + \vert A \cap B \vert - \vert A \cap B \vert \\ &= \vert A \vert + \vert B \vert - \vert A \cap B \vert \end{align*}\]

    So \(\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert\), but this is equivalent to what we were trying to prove.

  5. If one were to roll 4 identical 3-sided dice (ignoring for a moment how a 3-sided die would look!), how many outcomes are possible?

    To any dice roll, we could sort the dice in a row so that the lower-valued dice are to the left of the higher-valued dice. We could put toothpicks between dice of a value difference by 1 (and so 2 if value difference of 2, and so on).

    There are \(4 + (3-1)\) slots to be filled with dice and toothpicks, and we place \((3-1)\) toothpicks because the dice take on 3 different values separated by 1. So the number of outcomes is:

    \[ \binom {4 + (3-1)}{3-1}\]