Counting

Understanding Counting (Combinatorics)

Combinatorics answers a deceptively simple question: how many ways can something happen? Rather than listing every possibility by hand, counting techniques let us compute exact totals for arrangements (permutations), selections (combinations), and more complex overlapping scenarios (inclusion-exclusion, pigeonhole). These tools show up anywhere you need to reason about probability, resource allocation, or the size of a search space in an algorithm.

Key Definitions & Formulas

• Factorial (n!): the number of ways to arrange n distinct items in order, n × (n-1) × ... × 1.
• Permutation P(n,r): the number of ordered arrangements of r items chosen from n, = n! / (n-r)!.
• Combination C(n,r): the number of unordered selections of r items from n, = n! / (r!(n-r)!).
• Addition rule: if tasks are mutually exclusive, add the number of ways to do each.
• Product rule: if tasks are independent and sequential, multiply the number of ways to do each.
• Pigeonhole principle: if more than n items are placed into n boxes, at least one box holds more than one item.

Worked Example

How many ways can you choose a 3-person committee from 5 people, where order doesn't matter? That's C(5,3) = 5!/(3!×2!) = (5×4)/(2×1) = 10. If instead you needed to assign 3 distinct roles (president, secretary, treasurer) to 3 of the 5 people, order matters, so it becomes P(5,3) = 5×4×3 = 60.

Where This Is Used

• Probability calculations, where combinations count favorable outcomes.
• Algorithm analysis, estimating the size of search spaces (e.g. password cracking time).
• Cryptographic key-space sizing.
• Scheduling and resource allocation problems in operations research.