Combinatorics
What is Combinatorics?
An arrangement of objects in a specific order.
Key formula / rule: Permutations (n objects taken r at a time)
Key points
- Understand and apply the fundamental principles of counting.
- Differentiate between permutations and combinations and apply them correctly.
- Calculate the number of ways to arrange and select objects.
- Solve problems involving restricted arrangements and selections.
Common exam trap
Confusing permutations with combinations (i.e., using combinations when order matters, or vice versa).
Definitions
- Term
Permutation
- Meaning
An arrangement of objects in a specific order.
- Term
Combination
- Meaning
A selection of objects where the order of selection does not matter.
- Term
Factorial
- Meaning
The product of all positive integers up to a given integer n, denoted by n!.
- Term
Pigeonhole Principle
- Meaning
A principle stating that if more items than containers are present, at least one container must hold more than one item.
Learning objectives
Understand and apply the fundamental principles of counting.
Differentiate between permutations and combinations and apply them correctly.
Calculate the number of ways to arrange and select objects.
Solve problems involving restricted arrangements and selections.
Understand and apply the Pigeonhole Principle.
Formulae
- Name
Permutations (n objects taken r at a time)
- Note
Used when the order of selection matters.
- Expression
P(n, r) = n! / (n-r)!
- Name
Combinations (n objects taken r at a time)
- Note
Used when the order of selection does not matter. Also denoted as (n choose r).
- Expression
C(n, r) = n! / (r! * (n-r)!)
- Name
Factorial
- Note
By definition, 0! = 1.
- Expression
n! = n * (n-1) * (n-2) * ... * 2 * 1
- Name
Pigeonhole Principle
- Note
A fundamental principle for proving existence in counting problems.
- Expression
If n items are put into m containers, with n > m, then at least one container must contain more than one item.
Prerequisites
Basic Arithmetic
Set Theory concepts
Understanding of basic probability
Common mistakes
Confusing permutations with combinations (i.e., using combinations when order matters, or vice versa).
Incorrectly applying the multiplication or addition principle.
Forgetting to account for repetitions when objects are not distinct.
Miscalculating factorials or binomial coefficients.
Overcounting or undercounting scenarios.
Keywords
Combinatorics
Counting
Permutation
Combination
Factorial
Pigeonhole Principle
Arrangement
Selection
Enumeration
Practice preview
In how many ways can 5 distinct books be arranged on a shelf?…
easy
A restaurant offers 3 types of appetizers, 5 main courses, and 2 desserts. How many different 3-course meals (one of each type) can be ordered?…
easy
How many distinct arrangements can be made from the letters of the word "ENGINEERING"?…
medium