Unit 5: Permutations and Combinations
Contents
1. Fundamental Principle of Counting
This principle forms the basis of all counting logic. It states that if one event can occur in m ways and a second independent event can occur in n ways, then:
- Multiplication Principle: The total number of ways the two events can occur together is m × n.
- Addition Principle: The number of ways either of the two events can occur is m + n (provided events are mutually exclusive).
2. Factorial Notation
The product of the first n natural numbers is called n factorial, denoted by n!.
n! = n × (n-1) × (n-2) \dots × 3 × 2 × 1
Note: 0! = 1 and 1! = 1.
Note: 0! = 1 and 1! = 1.
3. Permutations (Arrangement)
A Permutation is an arrangement in a specific order of a number of objects taken some or all at a time. Order matters in permutations.
nPr = (n!) / ((n-r)!)
(Where 0 ≤ r ≤ n)
(Where 0 ≤ r ≤ n)
- Arrangement of n distinct objects: n!
- Permutations when objects are not all distinct: (n!) / (p!q!r!) where p, q, r are counts of identical objects.
4. Combinations (Selection)
A Combination is a selection of a number of objects where the order does not matter. We are only interested in which objects are chosen, not their sequence.
nCr = (n!) / (r!(n-r)!)
(Where 0 ≤ r ≤ n)
(Where 0 ≤ r ≤ n)
Key Properties:
- nCr = nCn-r (Symmetry property)
- nC0 = nCn = 1
- Relationship: nPr = nCr × r!
5. Key Differences and Applications
Choosing the right formula depends on the problem context:
| Feature | Permutation | Combination | ||
|---|---|---|---|---|
| Focus | Arrangement / Sequence | Selection / Grouping | ||
| Order | Matters (AB ≠ BA) | Does not matter (AB = BA) | Arrange, Order, Rank, Digits | Select, Choose, Group, Committee |