Introduction to Counting & Combinatorics

Math for CS · Axiom Academy

The art and science of counting -- why it matters for every CS student Combinatorics is the branch of mathematics concerned with counting , arranging , and selecting objects. At first glance it sounds simple -- just count things. But the problems get subtle fast, and the techniques are powerful. You've already done combinatorics without realizing it. "How many 4-digit PINs exist?" is a combinatorics question. So is "How many ways can 8 people sit around a table?" and "What's the probability of a full house in poker?" Counting isn't recreational math. It's a core tool in computer science for three critical reasons: When you analyze time complexity, you're counting operations. How many comparisons does merge sort make? How many recursive calls does naive Fibonacci spawn? These are combinatorial questions. Probability is built on counting: P( ) = | | | | . To compute probabilities, you need to count both the numerator and the denominator. Cryptographic security depends on key spaces being astronomically large. A 256-bit key has 2^ 256 possibilities. Combinatorics tells us whether brute-force attacks are feasible. All of combinatorics builds on two deceptively simple ideas: This combinatorics unit covers the essential counting techniques every CS student needs: Counting principles -- addition and multiplication rules, decision trees Permutations -- ordered arrangements, P(n,k) = (n-k)! Combinations -- unordered selections, k , Pascal's triangle

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