## 티스토리 뷰

**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.

#### 'Comp Sci > Tips' 카테고리의 다른 글

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 |

**댓글**

**공지사항**

**최근에 올라온 글**

- Total
- 508

- Today
- 0

- Yesterday
- 1

**링크**

**TAG**

- #BetterExplained
- Proof of Correctness
- Eulerian_Trail
- proof
- #Off_by_one
- construction_proof
- #Counting
- #경우의수
- Semi-Eulerian
- Edmonds
- HTTAA
- #Fencepost
- Induction
- Eulerian_circuit
- connected_graph
- strong_induction
- traversal
- remove_a_vertex
- Eulerian
- codomain
- Two Pointer
- proof-writing
- #Product_Rule
- subgraph
- proof_by_contradiction
- degree
- surjective
- maximal_path
- TIP
- Graph