This activity provides an overview of the types of problems we will consider under the umbrella of “combinatorics” this semester. You should access the online textbook using the link from Canvas. We will look at several sections from Chapter 1. Our goal today is not to solve every problem presented in the text! We are thinking about the types of questions. Even if you have prior experience with combinatorics and could answer the questions now, you do not need to.
Read the list of seven questions involving Amanda, Dawn, Keesha, and Seth in Section 1.2 Enumeration. As you read the problems, discuss them to ensure that you understand what the question is asking. The discuss each of the questions below.
Compare the first fourth and fifth questions. Do you think one of these must have a bigger answer, or are they asking the same question? Explain your reasoning.
Discuss the seventh question. You might think in terms of growth factor here: If we increase the number of people by multiplying by \(1000 = 10^3\text{,}\) how (approximately) might you expect the answers to increase? Can we even make a reasonable guess?
We will not have time in this course to discuss the necklace-type counting problems introduced at the end of the section. You’re welcome to read those questions and discuss them today if you’re interested, but you’ll have to do some extra reading after the semester to study this topic.
In Section 1.3 Combinatorics and Graph Theory, we endeavor to show how intuitive many of the ideas in combinatorics can be. We will define the terms of this section precisely in Chapter 5, so don’t worry when we move on today without a careful understanding of things!
Discuss the 11 items after Figure 1.2. Which of these can you understand from the context given? What things remain unclear or unambiguous in a way that suggests we will want more precise definitions later on?
Discuss the five questions of Example 1.3. Are there any you can confidently answer today? What does your gut tell you about how easy or hard it would be for a computer algorithm to answer these questions efficiently?
For Example 1.5, spend a few minutes trying to answer the questions presented after Figure 1.6, which is reproduced below so you can draw on it if you’d like.
In Section 1.4 Combinatorics and Number Theory, you get to experience a preview of some of the integrated interactivity our textbook provides. Code in our text uses SageMath, an open source computer algebra system that uses Python as its underlying syntax.
Look over the partitions in Figure 1.11. What do you notice? What do you wonder? If time permits after you complete the other questions on this worksheet, come back and start making a list of the partitions of \(9\text{,}\) identifying those into distinct parts and those into odd parts.
In Example 1.12, I suggest starting with fewer lines. How many regions would be determined by one, two, or three lines? Can you draw five lines that meet the criteria given in this example?
For Example 1.15, work to try to redraw the graph in such a way that no edges cross. If you can’t redraw it with no crossing edges, do you think that this is simply an impossible task? What do you think about the question the text asks about Sam and Deborah’s discussion?
In this course, we will not get into the topics discussed in Section 1.6 Combinatorics and Optimization. These sorts of topics appear in I SY E/COMP SCI/MATH 425 (Introduction to Combinatorial Optimization) and MATH 444 (Graphs and Networks in Data Science). I’d encourage you to consider taking one or both of these courses in the future!
