FOLLOW AN IDEA
Combinatorics
Explore basic counting; counting structures; partitions and symmetry. Concepts and connections are available independently of video coverage.
Prerequisites and connections
Group actions
A group action assigns compatible transformations of a set to group elements.
Video explanations to be added
Basic counting
Combinatorial counting
Count finite outcomes with disjoint-case sums, successive-choice products and equal-fiber division or bijections. Check that cases are disjoint and multiplicities are constant. Multiplication of choice counts is not a probability-independence assumption.
3 reviewed resourcesPermutations
Permutations record order. Distinct n objects have n! complete arrangements; indistinguishable repeated groups require dividing out their internal exchanges. Specify the multiplicities, whether all objects are used and whether rotations count as different arrangements.
3 reviewed resourcesCombinations
Choose k distinct elements from an n-element set without order, for integers 0≤k≤n. Each chosen subset corresponds to k!(n−k)! full permutations. Repetition-allowed selections are a different counting problem and need their own assumptions.
3 reviewed resourcesPigeonhole principle
More objects than boxes force at least one box to contain multiple objects.
Video explanations to be added
Counting structures
Inclusion–exclusion
Alternating intersection counts correct double-counting in unions of finite sets.
Video explanations to be addedBinomial theorem
Binomial coefficients give the expansion of an integer nonnegative power of a sum.
Video explanations to be addedRecurrence relations
A recurrence specifies sequence terms using earlier terms and initial data.
Video explanations to be addedGenerating functions
A sequence encoded as series coefficients supports algebraic counting and recurrence calculations.
Video explanations to be added
Partitions and symmetry
Integer partitions
A partition writes a positive integer as an unordered sum of positive integers.
Video explanations to be addedCatalan numbers
Catalan numbers count several recursively structured objects, including balanced parenthesis strings.
Video explanations to be addedBurnside's lemma
For a finite group action, orbit count equals the average number of fixed points.
Video explanations to be addedRamsey theory
Sufficiently large structures force specified regular substructures under suitable coloring conditions.
Video explanations to be added