Course Theory

Book 2. Olympiad Combinatorics Methods

1. Advanced Double Counting
2. Inclusion-Exclusion
3. Bijections and Encoding Objects
4. Extremal Principle
5. Invariants II and Monovariants
6. Ramsey-Type Ideas
7. Graphs II
8. Matching and Hall's Theorem Intro
9. Generating Functions I

Back to Course

Chapter

Advanced Double Counting

This module develops double counting into counting pairs, triples, incidences, intersections, and inequalities through averages.

Key Idea Double counting means choosing one set of objects and counting it in two ways. In advanced problems, the objects are often not the original items, but pairs, triples, incidences, intersections, or paths. The method is especially strong when direct counting is hard, but row sums equal column sums, and an average value forces the existence of a “good” object. Basic Facts If \(I=\{(x,A):x\in A\}\), then \(|I|=\sum_A |A|=\sum_x d(x)\), where \(d(x)\) is the number of sets containing \(x\). Average: if a total \(S\) is distributed among \(n\) objects, then some object has value at least \(\frac Sn\). The number of pairs of elements inside sets is \(\sum_A \binom{|A|}{2}\). If each pair of elements can occur at most once, then \(\sum_A \binom{|A|}{2}\le\binom n2\). In a graph, the sum of degrees is \(2E\). When to Use This Method Use it when the statement involves “each object is connected to…”, rows and columns, set systems, intersections, acquaintances, tournaments, paths of length \(2\), or proving existence through an average. How to Recognise the Method Look for hidden pairs: “an element belongs to a set”, “a student solved a problem”, “a vertex is incident to an edge”, or “two rows share a marked column”. If such pairs can be counted from both sides, it is very likely a double-counting problem. Typical Mistakes Counting the original objects instead of the right pairs or triples. Forgetting that one object may be counted several times. Using an average without converting to an integer: \(\lceil x\rceil\) or a strict estimate may be needed. Confusing “at most one common element” with “exactly one common element”. Proving only an identity without connecting it to the required existence statement. Mini-Checklist Name the object being counted: pairs, triples, incidences. Count it “by the left objects” and “by the right objects”. If an estimate is needed, replace exact counting with an inequality. If existence is needed, compare with the average. Check that repeated counting is intentional and controlled.

Example 1. Incidences The most basic form of double counting. Problem. In a class of \(24\) students, each student attends exactly \(3\) clubs. Prove that if there are \(8\) clubs, then some club has at least \(9\) students. Solution. Count pairs \((student, club)\) where the student attends the club. By students, there are \(24\cdot3=72\) such pairs. By clubs, the average number of students is \(\frac{72}{8}=9\). Hence some club has at least \(9\) students. Comment. We do not need the exact distribution among clubs; the total number of incidences is enough. Example 2. Sum of Degrees Graphs are a natural language for many relation problems. Problem. Prove that in every graph, the number of vertices of odd degree is even. Solution. The sum of all degrees equals \(2E\), where \(E\) is the number of edges, because each edge contributes \(1\) to the degrees of its two endpoints. Thus the degree sum is even. The sum of even degrees is even, so the sum of odd degrees is also even. This is possible only if the number of odd summands is even. Comment. This double-counts pairs \((vertex, edge)\) where the vertex is incident to the edge. Example 3. Average by Elements Often we need to prove the existence of an element with large load. Problem. There are \(m\) subsets of an \(n\)-element set, each of size at least \(r\). Prove that some element belongs to at least \(\left\lceil\frac{mr}{n}\right\rceil\) subsets. Solution. Count pairs \((x,A)\), where \(x\in A\). By sets, there are at least \(mr\) such pairs. By elements, this is the sum of \(d(x)\), where \(d(x)\) is the number of sets containing \(x\). The average \(d(x)\) is at least \(\frac{mr}{n}\), so some \(d(x)\) is at least the ceiling of this number. Comment. This is the standard average argument. Example 4. An Identity by Selection A combinatorial identity is best proved by counting objects. Problem. Prove \(\sum_{k=0}^{n} k\binom nk=n2^{n-1}\). Solution. Count pairs \((A,x)\), where \(A\subseteq\{1,\ldots,n\}\) and \(x\in A\). If we first choose \(A\) of size \(k\), we get \(\sum k\binom nk\). If we first choose \(x\), there are \(n\) choices, and the remaining elements of \(A\) can be chosen freely: \(2^{n-1}\) choices. Total: \(n2^{n-1}\). Comment. The left side groups by subset size, the right side by the marked element. Example 5. Pairs Inside Sets Moving from elements to pairs makes the method much stronger. Problem. There are \(m\) subsets of size \(k\) in an \(n\)-element set. Any two subsets have at most one common element. Prove \(m\binom{k}{2}\le\binom n2\). Solution. Count pairs \((\{x,y\},A)\), where \(x,y\in A\), \(x\ne y\). Each set \(A\) gives \(\binom{k}{2}\) pairs, so the total is \(m\binom{k}{2}\). On the other hand, any pair \(\{x,y\}\) can lie in at most one of the given sets; otherwise two sets would share two elements. Hence the number is at most \(\binom n2\). Comment. This is a typical double-counting inequality. Example 6. A Zero-One Table Rows and columns often give two natural counts. Problem. In a \(10\times10\) table, \(46\) cells are marked. Prove that some row or column contains at least \(5\) marked cells. Solution. Count pairs \((marked cell, line)\), where the line is a row or column containing the cell. Each marked cell lies on exactly two lines, so there are \(92\) pairs. There are \(20\) lines, so the average number of marked cells on a line is \(4.6\). Therefore some line contains at least \(5\) marked cells. Comment. Sometimes it is better to count all rows and columns together. Example 7. Average Intersection Intersections of set families are counted through element degrees. Problem. There are \(8\) three-element subsets of a \(5\)-element set. Prove that two of them intersect in at least two elements. Solution. Let \(d(x)\) be the number of chosen subsets containing element \(x\). Then \(\sum d(x)=8\cdot3=24\). The number of triples \((x,\{A,B\})\), where \(x\in A\cap B\), is \(\sum_x\binom{d(x)}2\). With total \(24\) over \(5\) elements, this sum is minimised by the balanced distribution \(5,5,5,5,4\), giving \(46\). There are only \(\binom82=28\) pairs of subsets. If every intersection had size at most \(1\), the sum of all pairwise intersection sizes would be at most \(28\), a contradiction. Comment. This example combines double counting with convexity. Example 8. Triples Sometimes the correct object is a triple, not a pair. Problem. Prove \(\sum_{A\subseteq[n]}\binom{|A|}{2}=\binom n2 2^{n-2}\). Solution. Count pairs \((A,\{x,y\})\), where \(A\subseteq[n]\) and \(x,y\in A\). If we first choose \(A\), we get the left side. If we first choose the pair \(\{x,y\}\), there are \(\binom n2\) choices, and each of the remaining \(n-2\) elements may be included or not: \(2^{n-2}\) choices. Comment. Such identities train the choice of the object being counted.

Chapter

Inclusion-Exclusion

This module develops inclusion-exclusion for forbidden conditions, derangements, surjections, fixed points, and distributions.

Key Idea The principle of inclusion-exclusion counts objects satisfying at least one condition, or equivalently objects avoiding forbidden conditions. The main idea is to add too much, subtract intersections, then add triple intersections back, and so on. Basic Facts \(|A\cup B|=|A|+|B|-|A\cap B|\). For three sets, pairwise intersections and the triple intersection enter with alternating signs. The number of objects avoiding forbidden properties is \(\sum (-1)^i\) times the number of objects satisfying a chosen set of \(i\) forbidden properties. The number of derangements is \(D_n=n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}\). The number of onto functions from an \(n\)-element set to an \(m\)-element set is \(\sum_{i=0}^{m}(-1)^i\binom mi(m-i)^n\). When to Use This Method Use it when the statement contains “at least one”, “none”, “fixed point”, “forbidden position”, “every colour is used”, “every box is nonempty”, or “not divisible by the given numbers”. How to Recognise the Method If direct counting with restrictions is inconvenient, count the complement. If objects can violate several restrictions at the same time, simple subtraction will be wrong; inclusion-exclusion is needed. Typical Mistakes Subtracting objects with two violations twice and not adding them back. Confusing “at least one violation” with “exactly one violation”. Forgetting that after fixing \(i\) fixed points, the remaining \(n-i\) objects are permuted. In function problems, confusing “all values are used” with “values are distinct”. Mini-Checklist Name the forbidden events \(A_1,\ldots,A_m\). Decide whether you count the union of bad events or its complement. For a chosen set of \(i\) forbidden events, count objects satisfying all of them. Use the sign \((-1)^i\). Check edge cases: \(i=0\), \(i=m\), and small \(n\).

Example 1. Two Sets The basic formula is the language for all later problems. Problem. Prove \(|A\cup B|=|A|+|B|-|A\cap B|\). Solution. In \(|A|+|B|\), each element of \(A\setminus B\) and \(B\setminus A\) is counted once, while each element of \(A\cap B\) is counted twice. To leave it counted once, subtract \(|A\cap B|\). Comment. The point is not the formula, but the reason for the minus sign. Example 2. Three Divisors Numbers with several properties often require inclusion-exclusion. Problem. How many integers from \(1\) to \(1000\) are divisible by at least one of \(2,3,5\)? Solution. We get \(\left\lfloor\frac{1000}{2}\right\rfloor+\left\lfloor\frac{1000}{3}\right\rfloor+\left\lfloor\frac{1000}{5}\right\rfloor-\left\lfloor\frac{1000}{6}\right\rfloor-\left\lfloor\frac{1000}{10}\right\rfloor-\left\lfloor\frac{1000}{15}\right\rfloor+\left\lfloor\frac{1000}{30}\right\rfloor=500+333+200-166-100-66+33=734\). Comment. Each pairwise intersection is subtracted, and the triple intersection is added back. Example 3. All Letters Used A surjection means “every value is used”. Problem. How many words of length \(7\) over the alphabet \(\{A,B,C\}\) contain all three letters? Solution. There are \(3^7\) words. Subtract words missing at least one letter. If the missing letter is chosen, there are \(2^7\) words; there are \(3\) choices. Words missing two letters were subtracted twice, so add them back: \(3\cdot1^7\). The answer is \(3^7-3\cdot2^7+3=1806\). Comment. This is the surjection formula in a small case. Example 4. Derangements Fixed points are the classical example. Problem. How many permutations of \(5\) elements have no fixed points? Solution. Let \(A_i\) be the event that element \(i\) is fixed. By inclusion-exclusion, the number of permutations with no fixed points is\[5!-\binom51 4!+\binom52 3!-\binom53 2!+\binom54 1!-\binom55 0!=44.\] Comment. After fixed points are chosen, the remaining elements are permuted freely. Example 5. Exactly \(k\) Fixed Points Sometimes we first choose the desired fixed points, then forbid all others. Problem. How many permutations of \(n\) elements have exactly \(k\) fixed points? Solution. First choose these \(k\) elements: \(\binom nk\). The remaining \(n-k\) elements must have no fixed points among themselves, so they can be permuted in \(D_{n-k}\) ways. The answer is \(\binom nkD_{n-k}\). Comment. Inclusion-exclusion is hidden inside \(D_{n-k}\). Example 6. Forbidden Positions Permutations with restrictions are naturally counted through events. Problem. How many permutations of \(1,\ldots,8\) place \(1,2,3\) away from their own positions? Solution. The restrictions apply only to the first three numbers. Inclusion-exclusion gives\[8!-\binom31 7!+\binom32 6!-\binom33 5!=40320-15120+2160-120=27240.\] Comment. Not all elements must avoid their own positions, only \(1,2,3\). Example 7. Surjections The inclusion-exclusion formula for functions. Problem. How many onto functions are there from a \(6\)-element set to a \(3\)-element set? Solution. There are \(3^6\) functions. Subtract functions missing a chosen value: \(\binom31 2^6\). Add back functions missing two values: \(\binom32 1^6\). The answer is \(3^6-3\cdot2^6+3=540\). Comment. This is the same count as words using all letters. Example 8. The General Formula The contribution of one object explains all signs. Problem. Explain why an object violating exactly \(r\) restrictions contributes \(\sum_{i=0}^m(-1)^i\binom ri\), which is \(0\) if \(r>0\) and \(1\) if \(r=0\). Solution. If an object violates exactly \(r\) restrictions, it belongs to the intersection of any chosen group of \(i\) of these \(r\) restrictions. Its total contribution is \(\sum_{i=0}^r(-1)^i\binom ri=(1-1)^r\). For \(r>0\), this is \(0\); for \(r=0\), the contribution is \(1\). Comment. This is the cleanest explanation of the general formula.

Chapter

Bijections and Encoding Objects

This module teaches bijective correspondences: subsets and strings, paths and words, compositions and bars, partitions and diagrams, and Catalan-style reflections.

Key Idea A bijection proves that two sets have the same size without computing both sizes separately. One must build a rule that assigns to every object of the first type exactly one object of the second type, and conversely. In olympiad combinatorics, a bijection often turns an inconvenient object into a code: a path into a word, a subset into a binary string, a distribution into stars and bars, or a partition into a diagram. Basic Facts Subsets of an \(n\)-element set are in bijection with binary strings of length \(n\). Monotone paths from \((0,0)\) to \((a,b)\) are in bijection with words containing \(a\) letters \(R\) and \(b\) letters \(U\). Nonnegative solutions of \(x_1+\cdots+x_k=n\) are in bijection with strings of \(n\) stars and \(k-1\) bars. Taking complements gives a bijection between \(k\)-subsets and \((n-k)\)-subsets. Reflection of bad paths often gives exact formulas for Catalan-style restrictions. When to Use This Method Use it when the answer looks simple but direct counting is bulky; when a combinatorial identity must be proved; when objects can be encoded by sequences of choices; or when paths, parentheses, partitions, or selections without adjacent elements appear. How to Recognise the Method Signals include: “prove the two numbers are equal”, “find the number of ways” for very different-looking objects, “word/path/subset/distribution”, “no adjacent elements”, “not above the diagonal”, and “partition into parts”. A useful question is: what data must be recorded to reconstruct the object? Typical Mistakes Building a map without proving that it is reversible. Losing objects with zero parts in stars and bars. Treating a path and a word as “similar” without specifying the exact step correspondence. In reflection arguments, reflecting from the wrong point instead of the first forbidden step. Confusing ordered compositions with unordered partitions. Mini-Checklist Describe the left object and the right object. State the forward map. Show how to reconstruct the original object. Check boundary cases: zeros, empty blocks, extreme paths. If there is a restriction, try a bijection with bad objects or a reflection.

Example 1. Subsets and Binary Strings The simplest bijection: an object is replaced by a zero-one code. Problem. Prove that an \(n\)-element set has exactly \(2^n\) subsets. Solution. Number the elements \(1,\ldots,n\). To each subset assign a binary string of length \(n\): the \(i\)-th position is \(1\) if element \(i\) is chosen, and \(0\) otherwise. The subset can be uniquely recovered from the string. Hence the number of subsets equals the number of binary strings, which is \(2^n\). Comment. Reversibility matters: the string does not merely come from the subset; it completely determines it. Example 2. Paths and Words A lattice path is naturally encoded by its sequence of steps. Problem. How many monotone paths go from \((0,0)\) to \((4,3)\), using only steps right and up? Solution. Each path consists of \(4\) steps \(R\) and \(3\) steps \(U\). Recording the steps in order gives a word of length \(7\) with four \(R\)'s and three \(U\)'s. Conversely, every such word gives a path. Therefore the number of paths is \(\binom{7}{3}=35\). Comment. This is the basic “path ↔ word” bijection. Example 3. Stars and Bars A distribution of identical objects into distinct boxes is encoded by bars. Problem. How many nonnegative solutions does \(x_1+x_2+x_3+x_4=12\) have? Solution. Write \(12\) stars in a row and insert \(3\) bars. The number of stars before the first bar is \(x_1\), between the first and second is \(x_2\), between the second and third is \(x_3\), and after the third is \(x_4\). Adjacent bars are allowed and give zero parts. Thus we choose positions of \(3\) bars among \(15\) symbols, giving \(\binom{15}{3}=455\). Comment. This is the source of many composition problems. Example 4. Selection Without Neighbours A no-adjacency restriction often disappears after shifting indices. Problem. How many \(k\)-element subsets of \(\{1,\ldots,n\}\) contain no two consecutive numbers? Solution. Let the chosen numbers be \(1\le a_1<\cdots Comment. This is a shifting bijection, not just a formula. Example 5. Complements Sometimes the bijection is so simple that it is easy to miss. Problem. Prove combinatorially that \(\binom nk=\binom n{n-k}\). Solution. To each \(k\)-element subset \(A\), assign its complement \([n]\setminus A\), which has \(n-k\) elements. The inverse map is the same operation, since the complement of the complement is the original set. Hence the two sets have equal size. Comment. This is a good example of an involutive bijection. Example 6. Ferrers Diagrams Partitions are often handled by reflecting or transposing diagrams. Problem. Prove that the number of partitions of \(n\) into at most \(k\) parts equals the number of partitions of \(n\) in which every part is at most \(k\). Solution. Draw the partition as a Ferrers diagram: rows consist of cells, and row lengths are the parts. If there are at most \(k\) rows, then after transposing the diagram, every row of the new diagram has length at most \(k\). The inverse transformation is the same transposition. Thus we get a bijection. Comment. A diagram is helpful, but the idea is an invertible transformation. Example 7. Reflection of Bad Paths The first serious Catalan-style move. Problem. How many paths from \((0,0)\) to \((n,n)\), using \(R,U\), never go above the diagonal \(y=x\)? Solution. There are \(\binom{2n}{n}\) paths in total. A bad path first goes above the diagonal with a step \(U\), landing at a point with \(y=x+1\). Reflect the part of the path up to this first crossing in the line \(y=x+1\). This gives a path from \((-1,1)\) to \((n,n)\), i.e. a word with \(n+1\) steps \(R\) and \(n-1\) steps \(U\). There are \(\binom{2n}{n-1}\) bad paths. Hence the number of good paths is \(\binom{2n}{n}-\binom{2n}{n-1}=\frac{1}{n+1}\binom{2n}{n}\). Comment. The key is to reflect up to the first violation. Example 8. Prüfer Code A strong bijection: a tree becomes a sequence. Problem. State the idea of Prüfer coding for counting trees on vertices \(1,\ldots,n\). Solution. While the tree has more than two vertices, remove the leaf of smallest label and record the label of its neighbour. This gives a sequence of length \(n-2\) with entries in \(1,\ldots,n\). Conversely, from such a sequence, repeatedly take the smallest label not currently appearing in the sequence, connect it to the first sequence entry, and delete that first entry. At the end connect the two remaining vertices. This is a bijection between labelled trees and sequences of length \(n-2\), so there are \(n^{n-2}\) trees. Comment. This is a Level 5 tool, but students should see it here.

Chapter

Extremal Principle

The module teaches how to choose a maximal or minimal object: a longest path, a minimal counterexample, a maximal configuration, or an extreme interval. The method is used in graphs, tournaments, set problems, and finite processes.

Example 1. The Largest Element This short example shows that an extremal choice alone can already create a contradiction. Problem. In a finite nonempty set of positive numbers, every number except possibly one has a strictly larger number in the same set. Prove that the number with no larger number exists and is unique. Solution. Choose a largest number \(M\) in the set. There cannot be a strictly larger number of the same set for \(M\). Thus at least one such number exists. If there were two different numbers with no larger number, then the larger of them would be strictly larger than the smaller one, so the smaller one would have a larger number. Contradiction. Hence the number is unique. Comment. The extremal object here is the maximum of the set. Example 2. The Longest Path This is a standard template for graph problems. Problem. In a finite graph, a path of maximum length is chosen. Prove that all neighbours of its endpoint lie on this path. Solution. Let the path be \(v_1v_2\ldots v_k\), and consider its endpoint \(v_k\). If \(v_k\) had a neighbour \(u\) outside the path, then \(v_1v_2\ldots v_k u\) would be a longer path. This is impossible because the original path was chosen as a longest path. Therefore every neighbour of \(v_k\) already lies on the path. Example 3. Intervals on a Line Sometimes the extremal quantity is not size, but a coordinate. Problem. Several intervals on a line intersect pairwise. Prove that there is a point belonging to all of them. Solution. Choose an interval \([a,b]\) with the smallest right endpoint \(b\). Take any other interval \([c,d]\). Since the two intervals intersect, we cannot have \(d If \(b Example 4. A Minimal Connected Subgraph Maximizing or minimizing the number of edges often helps remove redundancy. Problem. Prove that every finite connected graph has a connected subgraph containing all vertices and containing no cycles. Solution. Among all connected subgraphs containing all vertices of the original graph, choose one with the smallest number of edges. It exists because the original graph itself qualifies. If the chosen subgraph had a cycle, one edge of that cycle could be removed: connectivity would remain, since the rest of the cycle gives an alternate route. This would produce a connected subgraph with the same vertices and fewer edges, contradicting minimality. Thus there are no cycles. The subgraph is a tree. Example 5. A Maximal Configuration Here the object is not necessarily of maximum size; it is chosen so that nothing else can be added. Problem. In a graph, choose a set of pairwise disjoint edges to which no further edge can be added while preserving disjointness. Prove that any two vertices not covered by the chosen edges are not adjacent. Solution. Suppose two uncovered vertices \(x\) and \(y\) are joined by an edge. This edge has no common endpoint with any of the already chosen edges. Therefore it could be added to the chosen set while preserving disjointness. This contradicts maximality by inclusion. Hence no two uncovered adjacent vertices exist. Example 6. A Tournament and Maximum Outdegree In tournaments, an extremal player is often one with the largest number of wins. Problem. In a tournament, choose a player \(v\) with the largest number of wins. Prove that every player either lost to \(v\), or lost to someone whom \(v\) defeated. Solution. Consider a player \(u\) who did not lose to \(v\), so \(u\) defeated \(v\). Suppose that \(u\) defeated every player whom \(v\) defeated. Then \(u\) has all wins against the players defeated by \(v\), and also a win against \(v\) itself. Thus \(u\) has more wins than \(v\), contradicting the choice of \(v\). Therefore, among the players defeated by \(v\), there is a player who defeated \(u\). Example 7. A Minimal Counterexample A minimal counterexample is useful when the problem can be reduced. Problem. Prove that every integer \(n\ge 8\) can be represented as \(3a+5b\), where \(a,b\) are nonnegative integers. Solution. Check \(8=3+5\), \(9=3+3+3\), and \(10=5+5\). Suppose the statement is false, and choose the smallest \(n\ge 8\) that is not representable. Then \(n\ge 11\), so \(n-3\ge 8\). By the minimality of \(n\), the number \(n-3\) is representable as \(3a+5b\). Hence \(n=3(a+1)+5b\), a contradiction. Thus no counterexample exists. Example 8. Local Improvement The extremal principle is often hidden behind the phrase “choose an arrangement with the minimum number of failures.” Problem. The numbers \(1,2,\ldots,n\) are arranged in a row. One may swap two neighbouring numbers if the left one is larger than the right one. Prove that the process must end with the increasing order. Solution. Call a pair of positions \(i The number of inversions is a nonnegative integer, so it cannot decrease forever. The process ends. At the end there is no neighbouring inversion, and therefore the row is increasing.

Chapter

Invariants II and Monovariants

The module develops invariants beyond the basic level: parity, residues, gcd, product of signs, board colourings, weighted sums, and monovariants for proving termination of processes.

Key Idea An invariant is a quantity or property that does not change under the allowed moves. If the initial and final states have different invariant values, the transition is impossible. A monovariant is a quantity that strictly increases or strictly decreases after each move. If it is integer-valued and bounded, the process must terminate. Basic Facts Common invariants are parity, residues modulo an integer, sums, products of signs, gcd, and colouring sums. For boards, useful colourings include chessboard colouring, diagonal colouring, coordinate residues, and weights \(+1\) and \(-1\). For processes, look for a quantity moving in one direction: number of inversions, sum of squares, weighted sum, or maximum height. An invariant usually proves impossibility, while a monovariant usually proves termination or absence of an infinite game. When to Use This Method The problem contains allowed operations, moves, recolourings, swaps, or transfers of stones. You need to prove that a state is unreachable. You need to prove that a process must eventually stop. The statement contains a board, colours, residues, signs, gcd, or repeated local changes. How to Recognise the Method First compare the initial and desired states: how do they differ in parity, sum, colours, or residues? Then check what one move does to that quantity. If a direct invariant is not visible, try assigning weights to cells or objects. A good weight function gives zero contribution for every allowed move but nonzero contribution for the target state. Typical Mistakes Checking the invariant only on one sample move, not on an arbitrary move. Showing that a quantity does not increase, but not that it changes strictly; termination then does not follow. Using an invariant that is too weak: the initial and final states agree under it. Forgetting to prove sufficiency when the problem asks for a full reachability criterion, not only impossibility. Mini-Checklist Write what one move changes. Check parity, residues, sum, gcd, and product of signs. For a board, choose a colouring or weights. For a process, find an integer-valued bounded quantity with strict change. Compare the initial and final states using the found quantity.

Example 1. Parity of Black Coins The simplest invariant is parity. Problem. Some coins on a table show their black side. In one move exactly two coins are flipped. Can a position with one black coin be turned into a position with no black coins? Solution. When two coins are flipped, the number of black coins changes by \(-2\), \(0\), or \(2\). In all cases its parity is preserved. Initially the number of black coins is odd, while in the position with no black coins it is \(0\), which is even. Therefore such a position cannot be obtained. Example 2. Chessboard Colouring Colouring turns a geometric tiling problem into counting. Problem. From an \(8\times 8\) chessboard, two corner squares of the same colour are removed. Can the remaining board be tiled by \(1\times2\) dominoes? Solution. Each domino covers one black and one white square. If two squares of the same colour are removed, then the remaining board has unequal numbers of black and white squares. A domino tiling would require these numbers to be equal. Hence such a tiling is impossible. Example 3. Residues Modulo an Integer Sometimes a residue, not the quantity itself, is preserved. Problem. A token is at point \(0\) on a number line. In one move it may be shifted \(6\) units to the right or \(9\) units to the left. Can it reach point \(100\)? Solution. Both allowed shifts are multiples of \(3\). Therefore the coordinate modulo \(3\) does not change. The initial coordinate has residue \(0\), while \(100\equiv 1\pmod 3\). Therefore point \(100\) cannot be reached. Example 4. GCD as an Invariant For operations with differences, the gcd often remains unchanged. Problem. There are two positive numbers \(a\) and \(b\). In one move, the larger number may be replaced by the difference of the larger and the smaller. Prove that the gcd of the two numbers is unchanged. Solution. If \(a\ge b\), the new pair is \(a-b\) and \(b\). The common divisors of \(a\) and \(b\) are exactly the common divisors of \(a-b\) and \(b\): divisibility of \(a\) and \(b\) gives divisibility of \(a-b\), and divisibility of \(a-b\) and \(b\) gives divisibility of \(a\). Thus \(\gcd(a,b)=\gcd(a-b,b)\). The gcd is preserved. Example 5. Sum of Squares as a Monovariant For balancing processes, the sum of squares often works. Problem. Two piles contain \(a\) and \(b\) stones, where \(a\ge b+2\). One stone is moved from the first pile to the second. Prove that the sum of squares of pile sizes decreases. Solution. Compare the old and new sums: \[(a^2+b^2)-((a-1)^2+(b+1)^2)=2(a-b-1).\] Since \(a\ge b+2\), we get \(a-b-1\ge 1\). The difference is positive, so the sum of squares strictly decreases. Example 6. Product of Signs When two signs are changed, the product of all signs remains unchanged. Problem. Signs \(+\) and \(-\) are written at the vertices of a connected graph. In one move, choose an edge and change the signs at both its endpoints. Prove that the product of all signs does not change. Solution. One move changes the signs at exactly two vertices. Therefore the product of all signs is multiplied by \((-1)^2=1\). Thus the product of signs is an invariant. Example 7. Row and Column Parity Sometimes one move preserves many parities at once. Problem. On an \(8\times8\) board, all cells are white. In one move, choose a contiguous \(2\times2\) block and change the colours of all four cells. Prove that a position with exactly one black cell cannot be obtained. Solution. One move changes two cells in each of two rows and two cells in each of two columns. Therefore the parity of the number of black cells in every row and every column is preserved. Initially all these parities are \(0\). If there is exactly one black cell, its row and its column have odd parity. Contradiction. Example 8. A Weighted Sum for Termination When stones move only in one direction, a weighted coordinate sum is useful. Problem. Stones lie in several cells of a strip. In one move, one stone may be moved one cell to the right, but not beyond the \(n\)-th cell. Prove that an infinite sequence of moves is impossible. Solution. Consider the sum of the indices of the cells containing the stones, counting each stone separately. Each move increases this sum by \(1\). The sum cannot exceed \(n\) times the number of stones. Thus it strictly increases but is bounded above. Infinitely many moves are impossible.

Chapter

Ramsey-Type Ideas

The module introduces forced-structure ideas: edge colourings, monochromatic triangles, friend-stranger problems, the fact \(R(3,3)=6\), Ramsey recursion, and first multicolour bounds.

Key Idea Ramsey-type ideas say that if an object is large enough, an ordered structure is forced to appear. In the simplest form: every two-colouring of the edges of a complete graph large enough contains a monochromatic triangle. The method often combines the pigeonhole principle, choosing a vertex, splitting neighbours by edge colours, and induction on the size of the desired structure. Basic Facts Every two-colouring of the edges of \(K_6\) contains a monochromatic triangle: this is \(R(3,3)=6\). The edges of \(K_5\) can be two-coloured without a monochromatic triangle: this proves that \(5\) is not enough. The general recursion is \(R(s,t)\le R(s-1,t)+R(s,t-1)\). Proofs usually begin with one vertex and an analysis of the colours of the edges from it. When to Use This Method You need to prove that among many objects there is a group with the same relation. There are friendships and stranger relations, red and blue edges, or several types of pairwise relations. The problem asks to guarantee a triangle, a clique, an independent set, or a monochromatic chain. You need to find the minimum number of objects after which a structure is unavoidable. How to Recognise the Method If every pair of objects has one of several possible relations, think of a complete graph with coloured edges. After choosing a vertex, split the remaining vertices by the colour of the edge to that vertex. If one group is large enough, apply a smaller known result inside that group. Typical Mistakes Proving only an upper bound and forgetting the construction for the lower bound. Confusing a monochromatic triangle with a triangle that merely has two edges of the same colour. Choosing wrong group sizes in the Ramsey recursion. Forgetting in people problems that the relation must be symmetric. Mini-Checklist Translate the statement into a complete graph with coloured edges. Choose a vertex and count incident edges of each colour. If a neighbour group is large enough, search for the structure inside that group. For an exact answer, also check a construction showing that a smaller number is insufficient.

Example 1. Three Edges of One Colour from a Vertex The first step of almost every Ramsey proof is the ordinary pigeonhole principle. Problem. From a vertex \(v\), \(5\) edges leave, each red or blue. Prove that at least \(3\) of them have the same colour. Solution. Five edges are distributed between two colours. If each colour appeared at most \(2\) times, there would be at most \(4\) edges. Contradiction. Hence at least \(3\) edges have the same colour. Example 2. Proving \(R(3,3)\le6\) This is the main basic result of the module. Problem. Prove that every red-blue colouring of the edges of the complete graph on \(6\) vertices contains a monochromatic triangle. Solution. Choose a vertex \(v\). From it, \(5\) edges leave, so at least \(3\) have the same colour, say red, to vertices \(a,b,c\). If among the edges \(ab,bc,ca\) there is a red edge, it forms a red triangle together with \(v\). If none of them is red, then all three are blue, and \(a,b,c\) form a blue triangle. Example 3. Why Five Vertices Are Not Enough For an exact result, one needs not only a guarantee, but also a smaller counterexample. Problem. Colour the edges of \(K_5\) in two colours so that there is no monochromatic triangle. Solution. Place the \(5\) vertices on a circle. Colour the sides of the pentagon red and the diagonals blue. The red edges form a cycle of length \(5\), so they contain no triangle. The blue edges also form a cycle of length \(5\), so there is no blue triangle either. Example 4. The Language of Friendships Problems about people translate into edge colourings. Problem. Among any \(6\) people, there are either \(3\) pairwise acquainted people or \(3\) pairwise unacquainted people. Solution. Build a complete graph: vertices are people, a red edge means acquaintance, and a blue edge means non-acquaintance. By Example 2, this graph contains a monochromatic triangle. A red triangle is \(3\) pairwise acquainted people, and a blue triangle is \(3\) pairwise unacquainted people. Example 5. Ramsey Recursion Large bounds are built from smaller ones. Problem. Explain why \(R(s,t)\le R(s-1,t)+R(s,t-1)\). Solution. Let there be \(R(s-1,t)+R(s,t-1)\) vertices. Choose a vertex \(v\). Among the remaining vertices, either \(v\) has at least \(R(s-1,t)\) red neighbours, or at least \(R(s,t-1)\) blue neighbours. In the first case, inside the red neighbours there is either a red \(K_{s-1}\), which together with \(v\) gives a red \(K_s\), or a blue \(K_t\). The second case is analogous. Example 6. The Bound \(R(3,4)\le10\) This is the first application of the recursion. Problem. Prove that among \(10\) people, there are either \(3\) pairwise acquainted people or \(4\) pairwise unacquainted people. Solution. This corresponds to the bound \(R(3,4)\le R(2,4)+R(3,3)\). We have \(R(2,4)=4\), because a red edge already gives a red \(K_2\), while with no red edges, \(4\) vertices form a blue \(K_4\). Also \(R(3,3)=6\). Therefore \(R(3,4)\le 4+6=10\). Translating back to people gives the required statement. Example 7. Three Colours and \(17\) Vertices Ramsey ideas also work for more colours. Problem. Prove that every three-colouring of the edges of \(K_{17}\) contains a monochromatic triangle. Solution. Choose a vertex \(v\). From it, \(16\) edges leave in three colours, so at least \(6\) edges have the same colour, say red, going to a set \(A\) of \(6\) vertices. If there is a red edge inside \(A\), it forms a red triangle with \(v\). If there are no red edges inside \(A\), then all edges inside \(A\) are coloured with the other two colours. By \(R(3,3)=6\), inside \(A\) there is a monochromatic triangle in one of those two colours. Example 8. A Monochromatic Connected Tree Not every forced structure is a clique; sometimes connectivity is forced. Problem. The edges of a complete graph are coloured red and blue. Prove that one of the two colour graphs is connected. Solution. If the red graph is connected, we are done. If not, take two different red components. Any edge between them cannot be red, otherwise the components would merge. Hence all edges between different red components are blue. Then the blue graph is connected: vertices in different red components are joined by a blue edge, and two vertices in the same red component can be connected through any vertex of another component by two blue edges.

Chapter

Graphs II

The module develops graph methods: degrees, trees, forests, connectedness, cycles, bipartiteness, Euler trails, basic matchings, and planar bounds.

Key Idea Graphs in olympiad combinatorics are not about terminology; they are a language for vertices, edges, degrees, paths, cycles, and components. In Book 2, students should command several lemmas: degree sum, spanning tree, tree as a connected acyclic graph, bipartiteness via odd cycles, Euler walks, and simple planar bounds. Basic Facts The sum of degrees is \(2E\), so the number of vertices of odd degree is even. A connected graph on \(n\) vertices has at least \(n-1\) edges; a tree has exactly \(n-1\) edges. In a tree, between any two vertices there is exactly one simple path. A graph is bipartite if and only if it has no odd cycles. A connected graph has an Euler circuit if and only if all degrees are even. When to Use This Method The problem contains roads, acquaintances, pairs, undirected networks, or schedules. You need to prove the existence of a path, cycle, component, matching, or colouring. The statement involves degrees, parity of edges, connectedness, or forbidden cycles. A planar configuration gives a planar graph or a tree. How to Recognise the Method Ask: what are the vertices and what are the edges? Sometimes vertices are people, cells, sets, or regions, and an edge means conflict, adjacency, intersection, or possible transition. If the graph is connected, take a spanning tree. If degrees appear, use the degree sum. If odd cycles are forbidden, try a bipartite colouring. Typical Mistakes Forgetting to ignore isolated vertices when discussing Euler trails. Thinking that \(E=n-1\) alone means the graph is a tree, although connectedness or acyclicity is also needed. Confusing bipartiteness with colouring edges in two colours. Using Euler's formula in planar problems without checking connectedness assumptions. Mini-Checklist Define vertices and edges. Check connectedness and components. Count the sum of degrees. For a minimum number of edges, look for a tree; if there is an extra edge, look for a cycle. For walks using all edges, check the number of odd degrees.

Example 1. Sum of Degrees The main graph formula is that every edge is counted twice. Problem. Prove that the sum of all vertex degrees of a graph equals twice the number of edges. Solution. Every edge has two endpoints. In the sum of degrees, it contributes \(1\) to each endpoint, for a total contribution of \(2\). Therefore the sum of degrees is \(2E\). Example 2. Number of Odd Degrees Parity immediately gives a strong conclusion. Problem. Prove that in every graph, the number of vertices of odd degree is even. Solution. The sum of all degrees is \(2E\), so it is even. The sum of even degrees is even, hence the sum of odd degrees is also even. This is possible only if the number of odd summands is even. Example 3. Spanning Tree Connectedness is often simplified by deleting redundant edges. Problem. Prove that every finite connected graph has a spanning tree. Solution. Among all connected subgraphs containing all vertices, choose one with the minimum number of edges. If it contains a cycle, deleting one edge of that cycle does not break connectedness, contradicting minimality. Thus it has no cycles and is a tree. Example 4. Exactly One Extra Edge A spanning tree helps reveal cycles. Problem. A connected graph with \(n\) vertices has \(n\) edges. Prove that it has exactly one cycle. Solution. Take a spanning tree; it has \(n-1\) edges. The original graph has exactly one edge outside the tree. Adding one edge to a tree creates exactly one cycle. There can be no other cycle, because every cycle would have to use this single extra edge. Example 5. Bipartiteness Bipartiteness is a vertex colouring, not an edge colouring. Problem. Prove that if a graph is bipartite, then it has no odd cycle. Solution. In a bipartite graph, every edge joins different parts. While moving along a cycle, the parts must alternate. To return to the starting part, one must make an even number of steps. Hence every cycle has even length. Example 6. Euler Circuit The degree condition explains why one can traverse all edges. Problem. If a connected graph has a closed walk using every edge exactly once, prove that all vertex degrees are even. Solution. Every time the walk enters a vertex, it must leave through a different unused edge. Thus the edges at the vertex are paired as entry-exit pairs. Therefore every degree is even. Example 7. A Maximal Matching Even before Hall's theorem, a basic matching lemma is useful. Problem. A matching maximal by inclusion is chosen in a graph. Prove that every edge of the graph has at least one endpoint covered by this matching. Solution. If there were an edge whose two endpoints are both uncovered, it could be added to the matching. This contradicts maximality by inclusion. Example 8. A Planar Bound Planarity turns geometry into counting edges and faces. Problem. Prove that a simple connected planar graph with \(n\ge3\) vertices and \(m\) edges satisfies \(m\le3n-6\). Solution. By Euler's formula, \(n-m+f=2\). Every face is bounded by at least three edges, and every edge is counted twice along face boundaries, so \(3f\le2m\). Hence \(f\le\frac{2m}{3}\), and Euler's formula gives \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Therefore \(m\le3n-6\).

Chapter

Matching and Hall's Theorem Intro

The module introduces matchings, systems of distinct representatives, Hall's condition, regular bipartite graphs, and augmenting paths.

Key Idea A matching chooses edges with no common endpoints. In bipartite graphs, this is the language of assigning tasks, choosing representatives, and forming pairs. Hall's theorem gives the exact criterion: the left part \(A\) can be fully covered by a matching if and only if for every \(S\subseteq A\), the neighbour set \(N(S)\) has size at least \(|S|\). Basic Facts Hall's necessity is simple: different vertices of \(S\) must be matched to different neighbours in \(N(S)\). Hall's condition is stated for all subsets, but in problems it is often proved by counting edges. If a bipartite graph is \(d\)-regular and the parts are equal, then it has a perfect matching. A matching is not maximum if and only if there exists an augmenting path. When to Use This Method You need to choose distinct elements from several sets. You need to assign different tasks, seats, days, representatives, or partners. A bipartite graph is given and one needs to cover one part or both parts. There are local restrictions of the form “who may receive what”. How to Recognise the Method If objects of one type must receive pairwise distinct objects of another type, build a bipartite graph: requirements on the left, possible choices on the right. Then check Hall's condition: any group of requirements must have at least as many available options as its size. Typical Mistakes Checking Hall's condition only for single vertices. Confusing a maximal matching with a perfect matching. Forgetting that an SDR is a matching covering the sets, not the elements. In a regular bipartite graph, failing to prove that the two parts have equal size. Mini-Checklist Define the left and right parts. Draw an edge if the choice is allowed. State which part must be covered. For arbitrary \(S\), estimate \(|N(S)|\). If the matching is not maximum, look for an augmenting path.

Example 1. What a Matching Is A matching is a set of edges with no common endpoints. In the star \(K_{1,n}\), any matching contains at most one edge because all edges share the centre. Example 2. Necessity of Hall's Condition If a set \(S\) in the left part is covered by a matching, its vertices are matched to distinct vertices of \(N(S)\). Therefore \(|N(S)|\ge |S|\). Example 3. Systems of Representatives For sets \(A_1,\ldots,A_n\), a system of distinct representatives is a choice \(a_i\in A_i\), with all \(a_i\) distinct. This is a matching between sets on the left and elements on the right. Example 4. Regular Bipartite Graph If a bipartite graph is \(d\)-regular, then for every left-side set \(S\), \(d|S|\) edges leave \(S\). All enter \(N(S)\), and each right-side vertex receives at most \(d\) of them, so \(d|S|\le d|N(S)|\), hence \(|N(S)|\ge |S|\). By Hall, a matching exists. Example 5. Assigning Problems If every group of \(k\) students can collectively solve at least \(k\) different problems, then one can assign each student a different available problem. This is exactly Hall's condition. Example 6. Robustness If for every \(S\), \(|N(S)|\ge |S|+1\), then after deleting any one right-side object we still have \(|N(S)|\ge |S|\), so the matching remains possible. Example 7. Augmenting Path If a path starts and ends at uncovered vertices and its edges alternate: not in the matching, in the matching, not in the matching, then switching along the path increases the matching size by \(1\). Example 8. Decomposing a Regular Graph In a \(d\)-regular bipartite graph, find a perfect matching, remove it, obtain a \((d-1)\)-regular graph, and repeat. Thus the edges decompose into \(d\) perfect matchings.

Chapter

Generating Functions I

The module introduces generating functions as coefficient language for counting sums, bounded compositions, weighted subsets, partitions, and recurrences.

Key Idea A generating function turns a counting problem into a coefficient problem. If the number of ways to obtain sum \(n\) is \(a_n\), we write \(A(x)=a_0+a_1x+a_2x^2+\cdots\). Then the answer to "how many ways produce \(n\)" is the coefficient of \(x^n\). The power of the method is that multiplication automatically combines independent choices. One factor describes one object or one restriction, and the product describes all objects at once. Basic Facts The coefficient of \(x^n\) is denoted by \([x^n]A(x)\). \((1+x)^m\) encodes choosing a subset of \(m\) elements: \(x\) means "chosen", \(1\) means "not chosen". \(1+x+x^2+\cdots=\frac{1}{1-x}\) encodes an unlimited number of identical objects. \(1+x+\cdots+x^r\) encodes choosing a number from \(0\) to \(r\). The product \(A(x)B(x)\) corresponds to independently adding contributions: coefficients are summed over all splits of the total. When to Use This Method You need to count solutions of \(a_1+\cdots+a_k=n\) with restrictions. You are choosing subsets with a prescribed sum of weights. A recurrence appears, especially a Fibonacci-type recurrence. You need to count partitions, compositions, or tilings of a strip. Direct casework grows quickly, but every local choice is simple. How to Recognise the Method Look for the question "what total weight was obtained?" If each object contributes a small amount to the exponent of \(x\), then a product of factors often gives the whole count. Another sign is wording such as "at most", "exactly", "sum equals", or "how many times may be taken". These restrictions usually translate into finite or infinite geometric sums. Typical Mistakes Confusing ordered compositions with unordered partitions. Using an infinite factor when the statement has an upper bound. Forgetting the shift when a variable must be positive rather than nonnegative. Extracting the coefficient of the wrong power after a change of variables. Expanding long products by hand instead of using symmetry, inclusion-exclusion, or a recurrence. Mini-Checklist What contributes to the exponent of \(x\)? Is one choice independent of another, or does order matter? Is the factor finite or infinite? Which coefficient must be extracted? Can the coefficient be simplified by symmetry, the substitution \(x\mapsto -x\), a recurrence, or inclusion-exclusion?

Example 1. A Coefficient as a Choice We start with the essential meaning of a coefficient: each factor represents one independent choice. Problem. Find the coefficient of \(x^3\) in \((1+x)^7\). Solution. When expanding \((1+x)^7\), we choose either \(1\) or \(x\) from each of the \(7\) factors. To obtain \(x^3\), we must choose \(x\) from exactly three factors. This can be done in \(\binom{7}{3}=35\) ways. Key idea. The coefficient is the number of ways to choose the positions from which the factor \(x\) came. Example 2. Unrestricted Nonnegative Solutions A geometric series encodes a variable that can take any nonnegative value. Problem. How many nonnegative integer solutions does \(a+b+c=12\) have? Solution. Each variable gives the factor \(1+x+x^2+\cdots=\frac{1}{1-x}\). We need \([x^{12}]\frac{1}{(1-x)^3}\).Since \(\frac{1}{(1-x)^3}=\sum_{n\ge 0}\binom{n+2}{2}x^n\), the answer is \(\binom{14}{2}=91\). Key idea. This is the stars-and-bars method written in coefficient language. Example 3. An Upper Bound When a variable is bounded above, the infinite series becomes a finite polynomial. Problem. How many solutions does \(a+b+c=8\) have if \(0\le a,b,c\le 3\)? Solution. We need the coefficient of \(x^8\) in \((1+x+x^2+x^3)^3\). It is convenient to use the complement:\((1+x+x^2+x^3)^3=\left(\frac{1-x^4}{1-x}\right)^3\).Without the upper bound, there are \(\binom{10}{2}=45\) solutions. If, for example, \(a\ge 4\), then after setting \(a'=a-4\) we get \(a'+b+c=4\), giving \(\binom{6}{2}=15\) solutions. There are three variables. If two variables are at least \(4\), the remaining sum is \(0\), giving \(\binom{3}{2}=3\) cases. Therefore the answer is \(45-3\cdot 15+3=3\). Key idea. Upper bounds often lead to inclusion-exclusion. Example 4. Subset Sum by Weights The product \(\prod(1+x^{w_i})\) encodes choosing or not choosing objects with weights \(w_i\). Problem. How many subsets of \(\{2,3,5,7\}\) have sum \(10\)? Solution. We need the coefficient of \(x^{10}\) in\[(1+x^2)(1+x^3)(1+x^5)(1+x^7).\]The sum \(10\) is obtained in two ways: \(3+7\) and \(2+3+5\). Hence the coefficient is \(2\). Key idea. Each element can be taken at most once, so its factor is \(1+x^{w_i}\). Example 5. A Fibonacci Recurrence A generating function can also derive a recurrence, not just extract a coefficient. Problem. Let \(t_n\) be the number of tilings of a \(1\times n\) strip by \(1\times 1\) squares and \(1\times 2\) dominoes. Find the generating function. Solution. A tiling starts either with one square, leaving a \(1\times(n-1)\) strip, or with one domino, leaving a \(1\times(n-2)\) strip. Thus \(t_n=t_{n-1}+t_{n-2}\), with \(t_0=1\), \(t_1=1\).For \(T(x)=\sum_{n\ge 0}t_nx^n\), we get \(T(x)=1+xT(x)+x^2T(x)\). Therefore\[T(x)=\frac{1}{1-x-x^2}.\] Key idea. First build the first step, then translate the recurrence into an equation for the series. Example 6. A Parity Filter Substituting \(x=1\) sums all coefficients, while substituting \(x=-1\) subtracts odd-degree coefficients. Problem. How many subsets of an \(n\)-element set have even size? Solution. The coefficients of \((1+x)^n\) count subsets by size. The sum of even coefficients is\[\frac{(1+1)^n+(1-1)^n}{2}.\]For \(n\ge 1\), this equals \(2^{n-1}\). Key idea. This is the first filtering idea: special substitutions separate the desired degrees. Example 7. Distinct Parts and Odd Parts Sometimes a generating function proves equality between two very different descriptions. Problem. Show that the number of partitions of \(n\) into distinct parts equals the number of partitions of \(n\) into odd parts. Solution. Distinct parts are encoded by \(\prod_{i\ge 1}(1+x^i)\). Odd parts are encoded by \(\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}\).Now\[\prod_{i\ge 1}(1+x^i)=\prod_{i\ge 1}\frac{1-x^{2i}}{1-x^i}=\frac{\prod_{i\ge 1}(1-x^{2i})}{\prod_{i\ge 1}(1-x^i)}=\prod_{j\ge 1}\frac{1}{1-x^{2j-1}}.\]The coefficients of \(x^n\) are equal, so the two numbers of partitions are equal. Key idea. For the coefficient of \(x^n\), only finitely many factors up to \(i=n\) are actually relevant. Example 8. Carries in Binary Encoding In stronger problems, a generating function may hide carries between binary digits. Problem. Find the coefficient of \(x^7\) in \((1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8+x^{12})\). Solution. The coefficient counts choices \(a_0,a_1,a_2\in\{0,1,2,3\}\) such that \(a_0+2a_1+4a_2=7\).The number \(7\) has binary form \(111_2\). Count carries. In the lowest digit, \(a_0\) must be odd: \(a_0=1\) gives no carry and \(a_0=3\) gives a carry. In each following digit, the no-carry and carry states again give two transitions, but at the end the carry must be zero. This gives \(4\) ways.Indeed, the solutions are \((3,2,0)\), \((1,3,0)\), \((3,0,1)\), \((1,1,1)\). Key idea. Do not expand the whole product: in such problems, carries are usually cleaner.