Discrete Mathematics: Activities and Exercises

1. Bus Stop.

Four adults and seven children are waiting at a bus stop.

1. How many ways can they sit in a row? Solution.

   \begin{equation*} 11! \end{equation*}

2. How many ways can they sit in a row if the adults must sit together and the children must sit together? Solution.

   \begin{equation*} 2 \times 4! \times 7! \end{equation*}

   The factor of 2 comes from the fact that the children can be to the left or the right of the adults.

3. How many ways can they sit in a row if the the children must sit together? Solution.

   \begin{equation*} 7! \times 5! \end{equation*}

   We seat the children in \(7!\) ways and them treat them as one "person" who must be seated with the four adults.

4. How many ways can they sit in a row if just the children are sitting together (and the adults must not sit together)? Solution.

   Let's use "good = all - bad." We count the ways that the children can sit together and subtract the number of ways that both the children and the adults are sitting together.

   \begin{equation*} 7! \times 5! - 2 \times 4! \times 7! \end{equation*}

2. In the Queue.

How many ways can 10 adults and 5 children stand in a line so that no two children are standing next to each other? (Hint: place the adults first, and then the children.) Solution.

3. Forming a Circle.

In how many ways can \(n\) people stand in a circle? (How is this problem different from standing in a line?) Solution.

4. Five Digits, No Zeros.

1. How many 5-digit numbers are there where no digit repeats and only the digits 1-9 appear? Solution.

   \begin{equation*} (9)_5 = P(9,5) \end{equation*}

2. Use inclusion-exclusion to determine how many numbers in part (a) contain a 3 and a 6. (Hint: you will need to use "good = all - bad.") Solution.

   The bad numbers are the ones that don't contain both a 3 and a 6. Using inclusion-exclusion, there are

   \begin{equation*} (8)_5 + (8)_5 - (7)_5 = P(8,5) + P(8,5) - P(7,5) \end{equation*}

   bad numbers. Therefore we have

   \begin{equation*} (9)_5 - 2 (8)_5 + (7)_5 = p(9,5) - 2 P(8,5) + P(7,5) \end{equation*}

   good numbers.

5. Coin Toss.

A coin is tossed 10 times and a sequence of heads and tails is observed.

1. How many different sequences are possible? Solution.

   \begin{equation*} 2^{10} \end{equation*}

2. In how how many of these sequences are there exactly 4 heads? Solution.

   \begin{equation*} {10 \choose 4} \end{equation*}

6. Dinner Party.

A woman has 9 close friends.

1. In how many ways can she invite 6 of them to dinner? Solution.

   \begin{equation*} {9 \choose 6} \end{equation*}

2. Repeat (a) if two of her friends don't get along and will not attend together. Solution.

   We give three solutions.

   • First, we have

     \begin{equation*} {7 \choose 5} + {7 \choose 5} + {7 \choose 6} = 49 \end{equation*}

     corresponding to inviting friend one (and not friend two), inviting friend two (and not friend one), and inviting neither of them.

   • Second, we have

     \begin{equation*} {9 \choose 6} - {7 \choose 4} = 49 \end{equation*}

     using the classic "good = all - bad" theorem. There are \({9 \choose 6}\) ways to invite any six people, and there are \({7 \choose 4}\) ways to invite the two people who don't get along.

   • Finally, let's use inclusion-exclusion. We have

     \begin{equation*} {8 \choose 6} + {8 \choose 6} - {7 \choose 6} = 28 + 28 - 7 = 49 \end{equation*}

     corresponding to \(|A \cup B| = |A| + |B| - |A \cap B|\) where \(A\) is the set of the parties with the first friend but not the second and \(B\) is the set of parties with the second friend but not the first.

3. Repeat (a) if her friends consist of 3 single people and 3 married couples, so that she must invite both spouses, or neither of them. Solution.

   We must invite two or three couples, which gives:

   \begin{equation*} {3 \choose 2} {3 \choose 2} + {3 \choose 3} = 3 \times 3 + 1 = 10. \end{equation*}

7. 10 Points.

Ten points in a plane, no three colinear, are given.

1. Every pair of points determines a unique line. So how many different lines are formed by joining pairs of these points? Solution.

   \begin{equation*} {10 \choose 2} \end{equation*}

2. Assume that none of the lines in part (a) are parallel and no three lines intersect at a single point. How many different triangles are formed by these lines? (Note that the corners of many of these triangles are at points other than the original 10 points!) Solution.

   \begin{equation*} {{10 \choose 2} \choose 3} \end{equation*}

   We need to choose a 3-set of the lines.

8. Executive Board.

How many ways can a club with 20 members choose an executive board consisting of a president, a secretary, a treasurer, and two other members? Solution.