Introduction to Counting

Videos (~20 mins)

There are not very many videos today, so taking time with the reading is especially important.

The summation rule for disjoint unions (5:54)
Counting formula for two intersecting sets (inclusion-exclusion) (7:31)

Readings (~45 mins)

DMOI Chapter 1.1

Warmup (~45 mins)

Problem 1

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)

\(A\) itself, the set of all strings of letters \(a-f\) of length \(5\).
\(B\), the subset of \(A\) in which strings contain no repeated letters.
\(C\), the subset of \(A\) in which every sequence starts with the three letters “\(bee\)”.
\(D\), the subset of \(A\) in which every sequence either starts with “\(bee\)” or ends with “\(eab\),” or both.
\(E\), the subset of \(A\) in which every sequence either starts with “\(bee\)” or ends with “\(cab\)”, or both.
\(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? Do not answer this question by listing out all the possibilities. Instead, think carefully and use the principle of inclusion-exclusion.

Hint: think about multiples of 15…