1. Introduction to Counting
Combinatorics is a branch of mathematics concerned with counting, arrangement, and combination of objects. At its core, it answers a fundamental question: how many ways can we arrange or select items from a given set? The distinction between permutations and combinations lies entirely in whether the order of selection matters.
These concepts form the foundation of probability theory, cryptography, statistical analysis, and algorithm design. Mastering them requires understanding factorials, the multiplication principle, and when to apply each formula.
2. Permutations
A permutation is an arrangement of objects in a specific order. When order matters, swapping two items creates a different outcome. For example, the sequence (A, B, C) is distinct from (C, B, A).
The number of permutations of r items selected from a set of n distinct items is given by:
Where n! (n factorial) represents the product of all positive integers up to n (e.g., 5! = 5 Ć 4 Ć 3 Ć 2 Ć 1 = 120).
š Example: Password Creation
A 4-digit PIN uses digits 0ā9 without repetition. How many possible PINs exist?
P(10, 4) = 10! / (10ā4)! = 10! / 6! = 10 Ć 9 Ć 8 Ć 7 = 5,040 possible PINs.
3. Combinations
A combination is a selection of items where order does not matter. Choosing {A, B, C} is identical to choosing {C, A, B}. This is common in committee selection, lottery draws, and team formation.
The number of combinations of r items from a set of n is:
Note that C(n, r) is often read as "n choose r" and is symmetric: C(n, r) = C(n, nār).
š Example: Fruit Salad
You have 6 types of fruit. How many 3-fruit combinations can you make?
C(6, 3) = 6! / [3!(6ā3)!] = 720 / (6 Ć 6) = 20 unique combinations.
4. Key Differences
| Feature | Permutation | Combination |
|---|---|---|
| Order Matters? | Yes | No |
| Formula | P(n,r) = n!/(nār)! | C(n,r) = n!/[r!(nār)!] |
| Relationship | P(n,r) = C(n,r) Ć r! | C(n,r) = P(n,r) / r! |
| Common Use Cases | Rankings, passwords, schedules | Committees, lotteries, selections |
| Relative Count | Always larger or equal | Always smaller or equal |
5. Real-World Applications
Permutations and combinations extend far beyond textbook exercises. They are critical in:
- Cryptography: Estimating brute-force complexity for keys and passwords.
- Genetics: Modeling gene combinations and chromosomal arrangements.
- Computer Science: Algorithm analysis, scheduling, and network routing.
- Sports Analytics: Predicting match outcomes and tournament brackets.
- Quality Control: Sampling strategies in manufacturing and testing.
6. Worked Examples
š Problem 1: Bookshelf Arrangement
In how many ways can 5 distinct books be arranged on a shelf if 2 specific books must remain together?
Total = 4! Ć 2! = 24 Ć 2 = 48 arrangements.
š Problem 2: Committee Selection
A club has 12 members. How many ways can a 4-person committee be formed if it must include at least 1 woman, given there are 5 women and 7 men?
Valid committees = 495 ā 35 = 460 ways.
7. References & Further Reading
- Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics. Addison-Wesley.
- Ross, S. M. (2014). A First Course in Probability (9th ed.). Pearson.
- Aevum AI Knowledge Graph: Combinatorics ā Probability ā Statistical Mechanics
- Open Educational Resource: Discrete Math for Engineers (MIT OCW)