Section5.1The Multiplicative and Additive Principles
In this section we begin our quest to start answering a question that sounds simple enough: “how many elements are in a set?” Counting the number of sets is common enough that we gave it its own symbol, \(|S|\text{,}\) in Section 1.2. Numbers of elements in the domain and codomain of functions determine whether a function is bijective, as we saw in an exercise in the functions section
We start with basic counting rules that help us count \(|A\times B|\) and \(|A\cup B|\) for sets \(A \and B\text{.}\)
Subsection
Note5.1.1.
It’s common to count “hands of cards,” so we’ll note that a standard deck of playing cards contains four suits (spade, heart, club, diamond). There are 13 cards in each suit (2,3,4,5,6,7,8,9,10, Jack, Queen, King, Ace). Face cards refers to jacks, queens, and kings. Spades and clubs are black and hearts and diamonds are red.
Our first principle counts \(A\times B\text{:}\)
Definition5.1.2.Multiplication Principle.
The multiplication principle states that if an event \(A\) can occur \(m\) ways and an event \(B\) can occur \(n\) ways, then the event “\(A \and B\)” can occur \(m\cdot n\) ways.
The multiplication principle generalizes to more than two events.
Example5.1.3.
If in your closet you have five ironic t-shirts, three pairs of pants, and three collegiate hats, how many different outfits do you have? Here an outfit is pants, shirt, hat.
Our second principle (almost) counts \(A\cup B\text{;}\) we need \(A \and B\) to be disjoint sets.
Definition5.1.6.Addition Principle.
The addition principle states that if event \(A\) can occur \(m\) ways and event \(B\) can occur \(n\) ways and the two events are disjoint, then the event “\(A \text{ or } B\) (but not both)” can occur \(m + n\) ways.
Example5.1.7.
If in your closet you have five ironic t-shirts, three pairs of pants, and three collegiate hats, how many different items do you have in your closet?
Definition5.1.8.Counting principles in terms of sets:.
Let \(A \and B\) be two sets. Then:
\(|A \times B| = |A| \cdot |B|\text{.}\)
If \(A \cap B = \emptyset\text{,}\) then \(|A\cup B| = |A| + |B|\)
In order to count \(A\cup B\text{,}\) regardless of how the two sets intersect, we introduce the following:
Definition5.1.9.The Principle of Inclusion-Exclusion.
If \(A \and B\) are two sets, then \(|A \cup B| = |A| + |B| - |A \cap B|\)
Note that this is like the additive principle, except we’re removing the occurrences that are in common between \(A\) and \(B\text{.}\)
It helps, when working counting problems with unions, even if using the principle of inclusion-exclusion, to draw a Venn diagram and label the number of elements in each section.
Example5.1.10.
Suppose a company receives 350 applications from college graduates for a job. Suppose 220 of these applicants majored in computer science, 147 majored in business, and 51 majored in both computer science and business. How many majored in neither computer science nor business?
We will now consider bit strings which are strings of characters containing only \(0\) and \(1\text{.}\) For example, these are bit strings: \(0011, 1010, 110,\) etc.
How many bit strings of length eight either start with a 1 bit or end with two bits 00?
There are 30 people in a club. Assuming everyone is qualified to serve in any position, how many different ways are there to assign a president, vice-president, secretary, and treasurer?
In fact, we could generalize it further, but I’ll leave that to you to write the formula if you’re interested.
Example5.1.13.
Suppose we surveyed a class of 41 students, asking if they could play an Accordion, a Bassoon, or a Clarinet. 12 could play the clarinet, 8 could play bassoon, and 5 the accordion. 6 played clarinet and bassoon, 2 played clarinet and accordion, and 3 played bassoon and accordion. One student played all three.
How many students can play at least one instrument? Solve this first by Venn Diagrams, then by PIE.
Our next counting approach is pretty straight forward. If you have three cookies, but only two plates, you know that one person is eaching at least two cookies.
Definition5.1.14.The Pigeonhole Principle.
If \(k\) is a positive integer and \(k+1\) objects are placed into \(k\) boxes, then at least one box has two or more objects.
I’ll pause here to note that a “pigeonhole” is a slot on a desk or shelf for holding papers. In our scenario, if we have five slots in our desk to hold our papers, and six papers, one slot has at least two papers.
Example5.1.15.
If there are 13 people, at least two of them have the same birth month.
If there are 10 cars at a restaurant, but 11 people there, then at least two people car pooled.
If \(N\) objects are placed into \(k\) boxes, then there is at least one box with \(\left\lceil \dfrac{N}{k} \right\rceil\text{.}\)
Let’s imagine there are 100 people in a large lecture hall, then we know that at least at least \(\left\lceil \dfrac{100}{12} \right\rceil = 9\) have the same birth month. Divide the number of people by the number of months, and round up.
Example5.1.17.
How many cards must be selected from a standard deck of 52 cards in order that at least three have the same suit?
There are 255 outfits. Use the multiplicative principle.
2.
For your college interview, you must wear a tie. You own 3 regular (boring) ties and 5 (cool) bow ties.
How many choices do you have for your neck-wear?
You realize that the interview is for clown college, so you should probably wear both a regular tie and a bow tie. How many choices do you have now?
For the rest of your outfit, you have 5 shirts, 4 skirts, 3 pants, and 7 dresses. You want to select either a shirt to wear with a skirt or pants, or just a dress. How many outfits do you have to choose from?
To maximize the number of elements in common between \(A\) and \(B\text{,}\) make \(A \subset B\text{.}\) This would give \(\card{A \cap B} = 10\text{.}\)
\(A\) and \(B\) might have no elements in common, giving \(\card{A\cap B} = 0\text{.}\)
\(15 \le \card{A \cup B} \le 25\text{.}\) In fact, when \(\card{A \cap B} = 0\) then \(\card{A \cup B} = 25\) and when \(\card{A \cap B} = 10\) then \(\card{A \cup B} = 15\text{.}\)
5.
If \(\card{A} = 8\) and \(\card{B} = 5\text{,}\) what is \(\card{A \cup B} + \card{A \cap B}\text{?}\)
In a recent survey, 30 students reported whether they liked their potatoes Mashed, French-fried, or Twice-baked. 15 liked them mashed, 20 liked French fries, and 9 liked twice baked potatoes. Additionally, 12 students liked both mashed and fried potatoes, 5 liked French fries and twice baked potatoes, 6 liked mashed and baked, and 3 liked all three styles. How many students hate potatoes? Explain why your answer is correct.
7.
For how many \(n \in \{1,2, \ldots, 500\}\) is \(n\) a multiple of one or more of 5, 6, or 7?
Describe a set in terms of \(A\text{,}\)\(B\text{,}\) and \(C\) with cardinality 26.
9.
Consider all 5 letter “words” made from the letters \(a\) through \(h\text{.}\) (Recall, words are just strings of letters, not necessarily actual English words.)
How many of these words are there total?
How many of these words contain no repeated letters?
How many of these words start with the sub-word “aha”?
How many of these words either start with “aha” or end with “bah” or both?
How many of the words containing no repeats also do not contain the sub-word “bad”?
\(8^5 = 32768\) words, since you select from 8 letters 5 times.
\(8\cdot 7\cdot 6\cdot 5\cdot 4 = 6720\) words. After selecting a letter, you have fewer letters to select for the next one.
\(8 \cdot 8 =64\) words: you need to select the 4th and 5th letters.
\(64 + 64 - 0 = 128\) words. There are 64 words which start with “aha” and another 64 words that end with “bah.” Perhaps we over counted the words that both start with “aha” and end with “bah”, but since the words are only 5 letters long, there are no such words.
\((8\cdot 7\cdot 6\cdot 5\cdot 4) - 3\cdot (5\cdot 4) = 6660\) words. All the words minus the bad ones. The taboo word can be in any of three positions (starting with letter 1, 2, or 3) and for each position we must choose the other two letters (from the remaining 5 letters).
10.
For how many three digit numbers (100 to 999) is the sum of the digits even? (For example, \(343\) has an even sum of digits: \(3+4+3 = 10\) which is even.) Find the answer and explain why it is correct in at least two different ways.
11.
Suppose a drawer has a dozen brown socks and a dozen black socks (all thrown together).
How many socks must be taken out at random to guarantee a match (of any color)?
How many socks must be taken out at random to guarantee at least two are black socks?
Assuming that no one has more than 1,000,000 hairs on their head and that the population of New York City was 8,008,278 in 2010, what is the least number of people in NYC in 2010 with the same number of hairs on their heads?
14.
Suppose that \(a, b, c, d, \and e \) are five different integers. Must some pair of them differ by a multiple of four?
There are a total of four different remainders modulo 4. According to the Generalized Pigeonhole Principal, if we have 5 numbers divided among four different remainders, \(\left\lceil \dfrac{5}{4} \right\rceil = 2\) of them have to have the same remainder. Thus they differ by a multiple of four.
