Introduction to Counting

Videos

• Introducing Counting (4:01)
• Addition Principle for OR Problems (12:57)
• Multiplicative/Product Principle for Sequential Choice (4:29)
• Combining Counting Principles (9:17)

Readings

• DMOI Chapter 1.1

Warmup

Problem 1

Note: Counting the size of \(B\) below requires an intuitive idea which we haven’t yet covered in videos or readings. Can you figure it out?

Consider the set \(A\) of all strings of letters \(a-f\) of length \(5\). Here are a few elements of this set:

• \(dcbac\)
• \(ebafe\)
• \(abafa\)

What is the cardinality of each of the following sets? (This is another way of asking how many strings there are with the specified property)

1. \(A\) itself, the set of all strings of letters \(a-f\) of length \(5\).
2. \(B\), the subset of \(A\) in which strings contain no repeated letters.
3. \(C\), the subset of \(A\) in which every sequence starts with the three letters “\(bee\)”.
4. \(D\), the subset of \(A\) in which every sequence either starts with “\(bee\)” or ends with “\(eab\),” or both.
5. \(E\), the subset of \(A\) in which every sequence either starts with “\(bee\)” or ends with “\(cab\)”, or both.
6. \(F\), the subset of \(B\) (the set of strings with no repeated letters) which do not contain the substring “\(bad\)” in any position.
   • Hint: figure out how many strings contain the substring “\(bad\)” and then subtract this number from the cardinality of \(B\).

Problem 2

How many positive integers less than or equal to 1,500 are multiples of either 3 or 5?

© Phil Chodrow, 2024