Sum Rule : when the events cannot happen at the same time
Product Rule : when the events happen in conjunction AND the number of leaves for each branch of the problem space tree is the same
How to classify the problem space into events/sets :
Rule 1) Do it exhaustively
Rule 2) Avoid over-counting!
ex) There are N kids running around the field. How will you count them?
Let's say we use the groups "Boys" and "Glasses"
With this classification, it's possible we have not dealt with girls not wearing glasses and over-counted boys wearing glasses.
So remember those two rules and use the easiest way to classify, provided you meet these rules.
When you have a condition you have to meet :
Rule) Start with the cases for that condition
ex) How many 3-digit even numbers can we make with 0, 1, 2, 3, 4 :
IAW this rule, we have to start with a classification following Rule 1 to meet the given condition.
i.e. we have to start with the cases where we have 0 in the ones place OR 2, 4 in the ones place.
In the former case, the number of ways is 1 * 4 * 3 (We may use the product rule b/c the PS tree has the same number of leaves for each branch).
In the latter case, the number of ways is 2 * 3 * 3.
In the hundreds place, we may not use 2 or 4 (depending on what went to the ones place) nor can we use 0. This gives us 3 choices.
In the tens place, we may not use 2 or 4 (depending on what went to the ones place) and whatever we used in the hundreds place. This gives us 3 choices.
Total number of 3-digit even numbers are 12 + 18 = 30.
|How to Count - Number of Ways (경우의 수) (0)||2018.04.26|
|How to Count (The Fencepost Problem) - Off by One Errors! (0)||2018.04.26|
|Proof by Induction on Graphs - Why You Should Always Remove a Vertex (0)||2018.01.07|
|How to Design - Case by Case (0)||2017.12.18|
|How to Iterate over a fixed range of integers (0)||2017.12.15|
- Proof of Correctness
- Two Pointer