Combinatorics Summary

Discrete Math · Axiom Academy

SUMMARY Counting and Combinatorics Let's review the systematic methods for counting possibilities and how these techniques connect to probability, algorithms, and algebra. Fundamental Counting Principles Addition Principle: If there are m ways to do task A and n ways to do task B, and tasks cannot be done simultaneously, there are m + n total ways (OR scenarios) Multiplication Principle: If there are m ways to do task A and n ways to do task B, and tasks are done in sequence, there are m × n total ways (AND scenarios) Key Distinction: Use addition when choosing between alternatives; use multiplication when making a sequence of independent choices Tree Diagrams: Visual tool for organizing systematic counting, particularly helpful for identifying whether to add or multiply Permutations: Arrangements where order matters. P(n,r) = n!/(n-r)! counts ways to arrange r objects from n total Combinations: Selections where order doesn't matter. C(n,r) = n!/(r!(n-r)!) counts ways to choose r objects from n total Relationship: C(n,r) = P(n,r)/r! because each combination corresponds to r! different permutations Decision Rule: If rearranging your selection gives a different outcome, use permutations. Otherwise, use combinations Circular Permutations: Arranging n objects in a circle gives (n-1)! arrangements, since rotations are considered identical

This is the written version of the interactive lesson above. See the full Discrete Math course.