Please enable JavaScript.
Coggle requires JavaScript to display documents.
6.1 Counting: Basic Principles (Multiplication Principle (image (Think of…
6.1 Counting: Basic Principles
Multiplication Principle
Think of the steps as being an event or a choice
Examples:
Number of ways you can make a sandwich
Number of ways you can pick a fantasy team
Possibilities for a lock or password
Multiple ways of looking at the same thing
Flipping a coin twice
Tree
Helps see the steps as separate events/timelines
FOIL
addition = OR. We can get heads OR tails: (h+t)
multiplication = AND. We have a first toss AND a second toss: (h+t) * (h+t)
(h+t) * (h+t) = \(h^2 + 2ht + t^2 \)
1 possibility where both are heads
2 possibilities where head and tail are the result
1 possibility for tail being both
Grid
Useful for a 2 step process
Addition Principle
The key thing here is that the sets have to be Disjoint meaning that no 2 sets share the same elements
The reason this is important is because we'd be double counting
If we try and count the total number of elements by adding the sets we'd be wrong
|X| = 3
|Y| = 3
|X| + |Y| = 6 but notice that there are actually only 5 distinct elements
Inclusion-Exclusion Principle
THe idea of this is pretty intuitive. Add all the sets once then remove the intersections since those would have been added multiple times
In this example:
\(|X| + |Y| - |X \cap Y|\) = 3 + 3 - 1 = 5
For 3 sets idea is the same:
When we add the sets individually there's a chance we added the same element 3 times
When we get rid of the extras that each 2 sets share we get rid of the same elements 3 times
Finally if we added some distinct element 3 times then deleted that element 3 times we never counted it, so we add this element (the intersection of all the sets) one last time to guarantee it's there
Sample Questions: