Counting Problems in Computer Science
What you'll learn: How to use the combinatorial techniques you've learned to solve real counting problems in CS, from analyzing bit strings to understanding algorithm behavior.
Bringing Combinatorics to Code
Now that you've built a toolkit of counting methods—permutations, combinations, the pigeonhole principle, inclusion-exclusion, and more—it's time to see them in action on the kinds of problems computer scientists face daily.
Common CS Counting Scenarios
Bit Strings: How many 8-bit strings have exactly three 1s? This is a combination problem: you're choosing 3 positions out of 8 for the 1s, so the answer is C(8,3) = 56. Questions like "how many strings start with 10?" use the product rule: 1 choice for the first bit × 1 for the second × 2^6 for the remaining = 64.
Subset Enumeration: If you have a set of n items, how many subsets exist? Each item is either in or out (2 choices), so by the product rule: 2^n total subsets. The power set we studied has size 2^n—that's why!
Password Strength: A password with 8 characters from 62 options (a-z, A-Z, 0-9) has 62^8 possible values (permutations with repetition). Understanding this helps you analyze security requirements.
Algorithm Analysis: When studying sorting algorithms, counting comparisons or swaps often involves summing sequences (Σ notation) or understanding worst-case arrangements—permutations where data is in reverse order.
Key Takeaway: Counting techniques transform abstract CS problems—like analyzing possible inputs, measuring security, or predicting algorithm behavior—into concrete mathematical answers using permutations, combinations, and the fundamental counting rules.