Counting principles, permutations, combinations, generating functions, and graph theory — the complete guide to combinatorics from fundamentals through advanced topics.
The multiplication rule is the bedrock of combinatorics. When a sequence of choices is made independently, the total number of outcomes is the product of the individual choice counts.
If two events are mutually exclusive (cannot both occur), the number of ways either can occur is the SUM of their individual counts. Example: choosing a red card OR a face card from a deck — use addition when the word 'or' means distinct alternatives.
If two events are independent (one does not affect the other), the number of ways both can occur is the PRODUCT of their counts. Example: 5 shirt choices and 4 pant choices give 5 x 4 = 20 outfits.
Visually enumerate outcomes by branching at each decision point. The number of leaves equals the total outcomes. Useful for small problems — use the multiplication rule when the tree would be too large to draw.
Sometimes it is easier to count what you do NOT want. Total outcomes minus unwanted outcomes equals desired outcomes. Example: count passwords with at least one digit by subtracting (all-letter passwords) from (all passwords).
A permutation is an arrangement of items where order matters. Swapping two elements creates a different permutation.
Arrange r items chosen from n distinct items, where each item can be used at most once. The formula counts ordered selections.
P(5, 3) = 5! / (5-3)! = 120 / 2 = 60
Example: 60 ways to arrange 3 of 5 books on a shelf.
When items can be reused (like digits in a PIN), each of the r positions has n choices independently.
4-digit PIN from digits 0-9: 10^4 = 10,000 possible PINs.
3-letter strings from 26 letters: 26^3 = 17,576.
When arranging n items where some are identical, divide by the factorials of the repeated item counts to avoid overcounting.
Arrangements of MISSISSIPPI (11 letters: 1 M, 4 I, 4 S, 2 P):
11! / (1! x 4! x 4! x 2!) = 39,916,800 / 1,152 = 34,650
When n distinct objects are arranged in a circle, rotations of the same arrangement are identical. Fix one object to remove rotational equivalence.
8 people seated at a round table: (8-1)! = 7! = 5,040 arrangements.
If the table can also be flipped (like a necklace), divide by 2: (n-1)!/2.
A combination selects items from a set where the order of selection does not matter. The binomial coefficient C(n, r) is read "n choose r."
Choose r items from n distinct items with no repeats and order ignored.
C(10, 3) = 10! / (3! x 7!) = 120
Example: 120 ways to pick a 3-person committee from 10 candidates.
Choose r items from n types where repetition is allowed and order does not matter. This is equivalent to stars and bars.
Choose 3 scoops from 5 ice cream flavors (repeats allowed): C(5+3-1, 3) = C(7,3) = 35.
Pascal's triangle arranges binomial coefficients. Each entry is the sum of the two entries above it. Row n lists C(n,0), C(n,1), ..., C(n,n).
(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4
Coefficients 1, 4, 6, 4, 1 are row 4 of Pascal's triangle.
| Feature | Permutation | Combination |
|---|---|---|
| Order matters? | Yes | No |
| Formula | n! / (n-r)! | n! / (r! (n-r)!) |
| Keyword clue | arrange, order, sequence | choose, select, group |
| P(4,2) vs C(4,2) | 12 | 6 |
Stars and bars solves distribution problems — placing identical objects into distinct bins. The "stars" represent objects; the "bars" are dividers between bins.
n identical objects into k distinct bins. The formula counts the number of ways to place k-1 bars among n+k-1 positions.
Example: 5 cookies, 3 children (bins empty allowed): C(5+3-1, 3-1) = C(7,2) = 21.
Pre-assign one object to each bin, reducing to n-k remaining objects. Then apply stars and bars with the new total.
Example: 5 cookies, 3 children (each gets at least 1): C(5-1, 3-1) = C(4,2) = 6.
Distributing 5 objects into 3 bins uses 2 bars. One arrangement:
Bin 1 gets 2, Bin 2 gets 3, Bin 3 gets 0. Each arrangement of 5 stars and 2 bars is a distribution.
If n + 1 objects are placed into n pigeonholes, at least one pigeonhole contains 2 or more objects.
If kn + 1 objects are placed into n pigeonholes, at least one pigeonhole contains k + 1 or more objects.
In any group of 13 people, at least 2 must share a birth month. There are only 12 months, and 12 + 1 = 13 people forces a collision.
To guarantee a matching pair of socks when drawing from a drawer with 3 colors, draw 3 + 1 = 4 socks. With 3 colors (holes) and 4 socks (objects), at least one color appears twice.
Place 5 points inside a unit square. Divide the square into 4 quadrants of side 0.5. By pigeonhole, at least one quadrant contains 2 points, which are at most sqrt(2)/2 apart.
Among any n + 1 integers, two must have the same remainder when divided by n, meaning their difference is divisible by n. This is used in number theory proofs.
To count elements in the union of overlapping sets, alternately add and subtract intersection sizes to avoid double-counting.
Adding |A| and |B| double-counts elements in the intersection, so subtract |A and B| once.
Example: of 50 students, 30 play chess, 25 play checkers, 10 play both. Players of at least one: 30 + 25 - 10 = 45.
The pattern alternates: add singletons, subtract pairs, add triples, subtract quadruples, and so on.
Let A_i be the set of permutations where element i is in its correct position. The number of derangements equals the total permutations minus those where at least one element is fixed. Applying inclusion-exclusion across all subsets of fixed points gives the derangement formula.
A derangement is a permutation where no element occupies its original position. Also called a "hat-check" problem — n people check their hats and receive them back in random order. D(n) counts distributions where nobody gets their own hat.
Approximately n!/e for large n. The probability that a random permutation is a derangement approaches 1/e ≈ 36.79%.
Base cases: D(1) = 0 (only one permutation, it is fixed), D(2) = 1 (swap is the only derangement).
| n | n! | D(n) | D(n)/n! |
|---|---|---|---|
| 1 | 1 | 0 | 0.000 |
| 2 | 2 | 1 | 0.500 |
| 3 | 6 | 2 | 0.333 |
| 4 | 24 | 9 | 0.375 |
| 5 | 120 | 44 | 0.367 |
| 6 | 720 | 265 | 0.368 |
The ratio D(n)/n! converges to 1/e ≈ 0.36788... as n increases.
Catalan numbers appear in an astonishing variety of counting problems involving non-crossing structures, balanced sequences, and binary trees.
C_0 = 1 C_1 = 1 C_2 = 2
C_3 = 5 C_4 = 14 C_5 = 42
C_6 = 132 C_7 = 429 C_8 = 1430
Each Catalan number is the sum of products of all pairs of earlier Catalan numbers that partition the index.
Valid sequences of n pairs of matched parentheses — for n=3: ((())), (())(), ()(()), ()()()
Ways to triangulate a convex polygon with n+2 sides — for n=3 a pentagon has 5 triangulations
Full binary trees with n internal nodes (n+1 leaves)
Monotonic lattice paths from (0,0) to (n,n) that stay on or below the diagonal
Ways to connect 2n points on a circle with n non-crossing chords
Stack-sortable permutations of length n (avoiding the pattern 231)
Generating functions encode sequences as formal power series, converting combinatorial identities into algebraic manipulations. They are one of the most powerful tools in advanced combinatorics.
For a sequence a_0, a_1, a_2, ..., the OGF is the formal power series A(x). Used for combinations and unlabeled structures.
OGF of (1, 1, 1, ...): A(x) = 1/(1-x) (geometric series)
OGF of C(n,k) for fixed n: (1+x)^n (binomial theorem)
OGF of Fibonacci numbers: x / (1 - x - x^2)
The EGF weights each term by 1/n!, making it natural for permutations and labeled structures.
EGF of (1, 1, 1, ...): e^x
EGF of permutations of n: 1/(1-x)
EGF of derangements D(n): e^(-x) / (1-x)
EGF of set partitions (Bell numbers): e^(e^x - 1)
Count the number of ways to make change for n cents using pennies, nickels, and dimes. Each coin type contributes an independent geometric factor to the OGF.
The coefficient of x^n in A(x) gives the number of ways to make n cents.
A graph G = (V, E) consists of a vertex set V and an edge set E. Graph theory provides a language for networks, circuits, scheduling, and countless other combinatorial problems.
The fundamental unit — a point in the graph. Vertices represent objects, people, cities, or states depending on context.
A connection between two vertices. Edges can be undirected (mutual relationship) or directed (one-way). Weighted edges carry a numeric value.
The degree of a vertex is the number of edges incident to it. The handshaking lemma: the sum of all degrees equals 2|E|. Every graph has an even number of odd-degree vertices.
A tree is a connected graph with no cycles. Key properties:
A tree on n vertices has exactly n - 1 edges.
There is exactly one path between any two vertices.
Removing any edge disconnects the tree; adding any edge creates exactly one cycle.
A rooted tree designates one vertex as the root, inducing parent-child relationships.
Cayley's formula: the number of labeled trees on n vertices is n^(n-2).
An Euler path uses every edge exactly once. An Euler circuit is an Euler path that returns to its starting vertex. The classic problem: the Seven Bridges of Konigsberg.
Euler Circuit Exists When:
The graph is connected and every vertex has even degree.
Euler Path Exists When:
The graph is connected and exactly 2 vertices have odd degree. The path starts and ends at those vertices.
A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit also returns to the start. Unlike Euler paths, no simple degree condition determines existence — this problem is NP-complete.
Dirac's Theorem: if every vertex of a graph on n vertices (n ≥ 3) has degree at least n/2, a Hamiltonian circuit exists.
Ore's Theorem: if for every pair of non-adjacent vertices u,v the sum of their degrees is at least n, a Hamiltonian circuit exists.
These are sufficient conditions, not necessary ones — a graph can have a Hamiltonian circuit even without satisfying them.
A proper graph coloring assigns colors to vertices so no two adjacent vertices share a color. The chromatic number X(G) is the minimum number of colors needed.
Bipartite graphs (no odd cycles) have chromatic number 2.
Complete graph K_n requires n colors.
Four Color Theorem: every planar graph can be properly colored with at most 4 colors.
Applications: scheduling (vertices = tasks, edges = conflicts), register allocation in compilers, frequency assignment.
Ramsey theory proves that complete disorder is impossible in any sufficiently large structure. No matter how a large enough structure is colored or partitioned, some organized substructure must appear.
In any group of 6 people, there must exist either 3 mutual acquaintances or 3 mutual strangers. This is equivalent to saying that every 2-coloring of the edges of K_6 contains a monochromatic triangle.
Proof sketch: fix one person — they know at least 3 of the remaining 5, or they don't know at least 3. In either case, among those 3, any mutual knowledge creates a triangle.
R(s, t) is the smallest n such that every red/blue coloring of K_n contains a red K_s or a blue K_t.
R(3,3) = 6
R(3,4) = 9 R(3,5) = 14
R(4,4) = 18 R(3,6) = 18
R(5,5) = unknown (43-48)
R(s, t) = R(t, s) by symmetry.
R(1, t) = 1 and R(2, t) = t.
Bound: R(s,t) ≤ R(s-1,t) + R(s,t-1).
Even R(5,5) is currently unknown despite decades of effort — the search space is astronomical.
Van der Waerden's theorem: color the integers 1..N with k colors; for large enough N, some color class contains an arithmetic progression of length n.
Hales-Jewett theorem: the underlying engine behind many Ramsey-type results; ensures monochromatic combinatorial lines in high-dimensional grids.
Schur's theorem: for any k-coloring of positive integers, there exist x, y, z of the same color with x + y = z.
Format: 3 letters followed by 4 digits. No restrictions on repeats.
Letters: 26 choices each position, 3 positions → 26^3 = 17,576
Digits: 10 choices each position, 4 positions → 10^4 = 10,000
Total plates = 17,576 x 10,000 = 175,760,000
175.76 million possible plates.
Choose 4 people from 7 men and 5 women; committee must have at least 2 women.
Case 1 (exactly 2 women): C(5,2) x C(7,2) = 10 x 21 = 210
Case 2 (exactly 3 women): C(5,3) x C(7,1) = 10 x 7 = 70
Case 3 (exactly 4 women): C(5,4) x C(7,0) = 5 x 1 = 5
Total = 210 + 70 + 5 = 285
285 valid committees.
Distribute 12 identical apples among 4 children so each child gets at least 2.
Pre-assign 2 apples to each child: 12 - 4x2 = 4 apples remain.
Distribute 4 identical apples among 4 children (empty bins now OK).
C(4 + 4 - 1, 4 - 1) = C(7, 3) = 35
35 ways to distribute the apples.
How many integers from 1 to 100 are divisible by 2, 3, or 5?
|A| = floor(100/2) = 50 (divisible by 2)
|B| = floor(100/3) = 33 (divisible by 3)
|C| = floor(100/5) = 20 (divisible by 5)
|A and B| = floor(100/6) = 16 (divisible by 6)
|A and C| = floor(100/10) = 10 (divisible by 10)
|B and C| = floor(100/15) = 6 (divisible by 15)
|A and B and C| = floor(100/30) = 3 (divisible by 30)
Total = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 74
74 integers from 1-100 are divisible by at least one of 2, 3, or 5.
A graph has 6 vertices with degrees: 2, 3, 4, 3, 4, 2.
Odd-degree vertices: those with degree 3 — there are 2 of them.
Exactly 2 odd-degree vertices → an Euler path exists (not a circuit).
Sum of degrees = 2 + 3 + 4 + 3 + 4 + 2 = 18 = 2 x |E|, so |E| = 9 edges.
An Euler path exists. It starts and ends at the two degree-3 vertices.
The fundamental counting principle (multiplication rule) states that if one event can occur in m ways and a second independent event can occur in n ways, then both events together can occur in m x n ways. Example: if you have 4 shirt colors and 3 pant styles, you have 4 x 3 = 12 possible outfits. This extends to any number of independent events: multiply all the individual counts together.
Order matters in permutations but not in combinations. A permutation counts the number of ways to arrange r items from n distinct items where order is important — P(n,r) = n! / (n-r)!. A combination counts the number of ways to choose r items from n where order does not matter — C(n,r) = n! / (r! x (n-r)!). Example: choosing 3 letters from A,B,C,D. Permutations include ABC and BAC as different — P(4,3) = 24. Combinations count ABC and BAC as the same — C(4,3) = 4.
Stars and bars counts the number of ways to distribute n identical objects into k distinct bins. If each bin can be empty, the answer is C(n+k-1, k-1). If each bin must contain at least one object, substitute n' = n-k and use C(n-1, k-1). Example: distribute 7 identical cookies among 3 children (bins can be empty) gives C(7+3-1, 3-1) = C(9,2) = 36 ways. The 'stars' represent the cookies and the 'bars' are dividers between the children's shares.
The pigeonhole principle states that if n+1 or more objects are placed into n containers, at least one container must hold 2 or more objects. The generalized form says that if kn+1 objects are placed into n containers, at least one container holds k+1 or more objects. Example: in any group of 13 people, at least 2 must share a birth month, since there are only 12 months. The principle proves existence without constructing an example.
Inclusion-exclusion counts elements in the union of sets by adding individual set sizes, then subtracting pairwise intersections, then adding triple intersections, and so on. For two sets: |A union B| = |A| + |B| - |A intersect B|. For three sets: |A union B union C| = |A| + |B| + |C| - |A intersect B| - |A intersect C| - |B intersect C| + |A intersect B intersect C|. Example: of 100 students, 60 study math, 50 study science, and 30 study both. Students studying at least one subject = 60 + 50 - 30 = 80.
A derangement is a permutation where no element appears in its original position. The number of derangements of n elements is D(n) = n! x (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!). For large n, D(n) is approximately n!/e, where e is Euler's number. So roughly 1/e (about 37%) of all permutations are derangements. Example: D(3) = 2 — for [1,2,3] the derangements are [2,3,1] and [3,1,2].
The nth Catalan number is C_n = C(2n,n) / (n+1). The sequence begins 1, 1, 2, 5, 14, 42, 132, ... Catalan numbers count an enormous variety of combinatorial structures: the number of valid sequences of n pairs of matched parentheses, the number of ways to triangulate a convex polygon with n+2 sides, the number of full binary trees with n+1 leaves, and the number of monotonic lattice paths from (0,0) to (n,n) that do not cross above the diagonal.
An ordinary generating function (OGF) for a sequence a_0, a_1, a_2, ... is the formal power series A(x) = a_0 + a_1*x + a_2*x^2 + ... It is used when order does not matter (combinations). An exponential generating function (EGF) is A(x) = a_0 + a_1*(x/1!) + a_2*(x^2/2!) + ... It is used when order matters (permutations) or for labeled structures. For example, the EGF for the number of permutations of n elements is 1/(1-x), and the EGF for derangements is e^(-x)/(1-x).
An Euler path traverses every edge of a graph exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex. A graph has an Euler circuit if and only if every vertex has even degree. A graph has an Euler path (but not circuit) if exactly two vertices have odd degree. A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit visits every vertex exactly once and returns to the start. Unlike Euler paths, no simple polynomial-time criterion is known for Hamiltonian paths — determining their existence is NP-complete.
Ramsey theory studies the conditions under which order must appear within a large enough structure. The classic result: in any group of 6 people, either 3 know each other or 3 are mutual strangers (R(3,3) = 6). Formally, the Ramsey number R(s,t) is the smallest n such that any 2-coloring of the edges of the complete graph K_n contains either a red K_s or a blue K_t. Known values are sparse — even R(5,5) is only known to lie between 43 and 48. Ramsey theory says complete disorder is impossible in sufficiently large structures.
Sample spaces, events, conditional probability, Bayes's theorem, and discrete distributions
Divisibility, primes, modular arithmetic, the Chinese Remainder Theorem, and Fermat's Little Theorem
Logic, set theory, proof techniques, recursion, and the foundations of computer science
Interactive counting problems with step-by-step solutions and private tutoring — free to try.
Start Practicing Free