Combinatorics & Boolean (Quick Summary)

1. Combinatorics

Counting and arranging various patterns to find probabilities

• Permutation: Order matters (e.g., Passwords, 1st 2nd 3rd prizes) P(n, r) = n! / (n-r)!
• Combination: Order does not matter (e.g., Randomly picking balls, picking a team of 3) C(n, r) = n! / (r! * (n-r)!)
• Pigeonhole Principle: If there are $N+1$ pigeons but $N$ holes, there must be at least 1 hole with 2 pigeons (used to prove Hash Collisions)

2. Boolean Algebra

The mathematics of 0 (False) and 1 (True), widely used in Digital Logic

• Important Laws:
  • De Morgan's Laws:
    • NOT (A AND B) = (NOT A) OR (NOT B)
    • NOT (A OR B) = (NOT A) AND (NOT B)
    • (Trick: Push NOT inside and flip the AND/OR sign)
  • Distributive Law: Can distribute variables into parentheses
• Applications: Designing Hardware Logic Gates and simplifying deeply nested if-else code