1
Pick the right one of four rules
Ordered or not, repetition or not. The arithmetic is easy; the classification is where the answer is won or lost.
Course · Discrete Mathematics
Combinatorics and Counting
How many? The two basic rules, the four ways to choose r from n, what changes when repetition is allowed, how to correct an over-count, and the double-counting arguments that prove identities without algebra.
P(n, r) = n!/(n−r)! ordered, no repetition
C(n, r) = n!/(r!(n−r)!) unordered, no repetition
C(n+r−1, r) unordered, with repetition
|A ∪ B ∪ C| = ΣA − Σ(pairs) + |A∩B∩C|
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 14
- Format
- Interactive
Overview
What you will be able to do
By the end you can choose the right rule, justify the choice, check the answer against a small enumeration, and invent the classification or the factor when no rule applies directly.
2
Count with restrictions
Complementary counting, cases, and knowing when to count the bad outcomes instead of the good ones.
3
Correct an over-count
Inclusion and exclusion for any number of sets, and derangements as the canonical application.
4
Prove an identity by counting
Count one set two ways and conclude the two expressions are equal — shorter and more informative than the algebra.
5
Invent the classification, or the factor
Choose the boxes so that ⌈n/k⌉ forces the conclusion, and write the factor that encodes each constraint so a generating function answers for every n at once.
Lessons
14 lessons
The basic rules come first, then the binomial coefficients and repetition, then corrections and bounds, and last the techniques that generalise them.
The Sum and Product RulesAdd for alternatives, multiply for stages.Not marked
Counting with RestrictionsCases, complements, and the order in which constraints are applied.Not marked
PermutationsOrdered selections without repetition.Not marked
CombinationsUnordered selections without repetition.Not marked
Binomial Coefficients and Pascal's TriangleThe numbers C(n, r), arranged so their identities become visible.Not marked
The Binomial TheoremWhy the same numbers count subsets and expand powers.Not marked
Permutations with RepetitionArrangements when objects may repeat, or are indistinguishable.Not marked
Combinations with RepetitionStars and bars: C(n + r − 1, r).Not marked
The Inclusion-Exclusion PrincipleAdd the sizes, subtract the pairs, add back the triples.Not marked
DerangementsPermutations with no fixed point, and the surprising limit.Not marked
The Generalised Pigeonhole Principle⌈n/k⌉ in a box, and what that proves.Not marked
Generating FunctionsEncode a sequence as coefficients and let algebra do the counting.Not marked
Combinatorial ProofCount one set two ways, or biject two sets.Not marked
Choosing a Counting MethodThe decision procedure, and how to check the answer.Not marked
Recommended background
Sets, functions and induction.
Practice suggestions
Check every formula against an enumeration while the numbers are small. The counting lab lists the actual selections up to 400 of them, and a formula that disagrees with the list is wrong however good the reasoning looked.
Say out loud whether order matters and whether repetition is allowed, before writing anything. Almost every wrong answer in this course is a right calculation of the wrong quantity.
Do the combinatorial proofs in “Combinatorial Proof” twice: once by algebra and once by counting. The second is shorter and tells you why the identity is true.
What it does not cover
Advanced enumerative combinatorics: species, the transfer-matrix method, and the deeper theory of generating functions. “Generating Functions” is an introduction, not a survey.
Design theory, Latin squares and error-correcting codes, which are the natural applications of this material but a separate subject.
Ramsey theory beyond the statement that R(3,3) = 6, which appears in “The Generalised Pigeonhole Principle” as a pigeonhole application.