Counting & Combinatorics

1.The multiplication and addition principles

Most counting problems are built from two operations: putting independent choices together, and splitting a count into disjoint cases. The multiplication principle handles the first. If a task has two steps, the first step can be done in $a$ ways, and the second can be done in $b$ ways no matter which first step was chosen, then the whole task can be done in $a\cdot b$ ways.

Why this is true: write each complete outcome as an ordered pair (first choice, second choice). Each of the $a$ first choices can be paired with each of the $b$ second choices, and no pair repeats. Laying the pairs out in an $a$-by-$b$ grid shows $ab$ cells, one per outcome. The same reasoning extends to any number of steps: $n$ independent steps with $a_1,\dots,a_n$ options give $a_1a_2\cdots a_n$ outcomes.

The addition principle handles 'or'. If an outcome must come from one of several cases that cannot happen at the same time, the total is the sum of the case sizes. The key word is disjoint. If two cases can overlap, adding them counts the overlap twice, and the overlap must be subtracted. That correction is the seed of inclusion-exclusion (Concept 5).

Most errors come from using the wrong operation. A useful test: ask whether every step must be carried out (then multiply) or whether one of several options is chosen (then add). Three soups and four sandwiches give $3\cdot 4=12$ lunches if the diner takes one of each. If the diner takes either a soup or a sandwich, but not both, the count is $3+4=7$.

A subtler trap: the number of options at a later step can depend on an earlier choice. Choosing two different cards from a 52-card deck gives $52\cdot 51$ ordered pairs, not $52\cdot 52$, because the second card cannot repeat the first. When the count of later options changes with the earlier choice, either split into cases on the earlier choice, or choose the objects in an order that makes each later count constant.

Overcounting is the other danger in products. The multiplication principle is exact only when each outcome corresponds to exactly one sequence of choices. If two different sequences produce the same final object, the product is too large and must be divided by the number of sequences that give the same object. That division is exactly what permutations and combinations do in the next concept.

• Product rule: independent steps with $a$ and $b$ options give $a\cdot b$ outcomes
• Sum rule: disjoint cases of sizes $a$ and $b$ give $a+b$ outcomes
• Dependent counts: if later options depend on earlier choices, split into cases or change the order of choosing

• Adding when every step must be made, or multiplying when only one option is chosen.
• Using a fixed count for a later step when an earlier choice changes its size.

2.Permutations and combinations

A permutation is an ordered selection. The number of ways to fill $k$ distinct positions from $n$ distinct objects is $P(n,k)=n(n-1)\cdots(n-k+1)=\frac{n!}{(n-k)!}$. The first position has $n$ choices, the next has $n-1$ because one object is used, and so on. This is the multiplication principle applied to a falling product.

A combination is an unordered selection: the number of $k$-element subsets of an $n$-set is $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$. Derivation: every $k$-subset can be listed in $k!$ orders, and each ordered list of $k$ distinct objects comes from exactly one subset. Therefore $P(n,k)=\binom{n}{k}\cdot k!$, which rearranges to the binomial formula.

This relationship is the most useful fact in the topic. When a problem asks for a committee, a pair of cards, or a set of marbles, the order does not matter, so divide by $k!$ or count the set directly. When the chosen items receive roles, seats, or positions, the order matters and you should count permutations. Many problems are a combination followed by an assignment: choose the set first, then multiply by the number of ways to label it.

Standard identities to recognize: $\binom{n}{k}=\binom{n}{n-k}$ (choosing who is left out is the same as choosing who is in), $\binom{n}{0}=\binom{n}{n}=1$, and $\binom{n}{1}=n$. The first identity is also a bijection: complementing a subset is a one-to-one correspondence between $k$-subsets and $(n-k)$-subsets, so the two counts are equal.

Worked idea: a club of 8 members must choose a president and a secretary, who must be different people. That is ordered, so there are $P(8,2)=56$ choices. If instead the club sends two people to a conference with no roles, the count is $\binom{8}{2}=28$, exactly half, because each pair appears once in each of its two orders in the permutation count.

Typical contest traps: choosing a set and then also ordering it when the problem does not care; forgetting that restrictions such as 'at least one woman' change which combinations are allowed, which is why such problems are split into cases; and mixing $P$ and $\binom{}{}$ inside one count, where the treatment of order must stay consistent throughout.

Combinations are the bridge to the rest of the topic. Pascal's identity (Concept 9) comes from counting subsets with and without a fixed element, and stars and bars (Concept 6) reduces distributions to choosing positions for bars among a row of symbols. Learning to say 'this is a set' or 'this is a sequence' in one sentence is the habit that prevents most errors.

• $P(n,k)=\frac{n!}{(n-k)!}$ counts ordered selections of $k$ items from $n$
• $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}=\frac{P(n,k)}{k!}$ counts unordered selections
• $\binom{n}{k}=\binom{n}{n-k}$ and $\binom{n}{k}=0$ when $k<0$ or $k>n$

• Counting a set and also multiplying by its orderings when the problem does not care about order.
• Using a single formula for a count that has a restriction, instead of splitting into cases.

3.Arrangements with repeats and circular arrangements

When letters repeat, the usual $n!$ overcounts. Take the word BOO. Treating the three letters as distinct gives $3!=6$ orders, but only three words exist: BOO, OBO, OOB. Each word arises from $2!=2$ labelings of the two O's. In general, if a word has $n$ letters with $n_1$ copies of one kind, $n_2$ of another, and so on, the number of distinct arrangements is the multinomial coefficient $\frac{n!}{n_1!\,n_2!\cdots}$.

Derivation by division: label the copies so that all $n$ items become distinct. This gives $n!$ labeled arrangements. Each distinct word corresponds to exactly $n_1!\,n_2!\cdots$ labeled arrangements, since the identical copies can be permuted among themselves without changing the word. Divide by that product. A second viewpoint is to choose positions for each kind in turn: $\binom{n}{n_1}$ ways for the first kind, then $\binom{n-n_1}{n_2}$ for the second, and so on. The product telescopes into the multinomial formula.

Circular arrangements: seat $n$ distinct people around a round table, where two seatings are the same if one is a rotation of the other. Fix one person in a reference seat. The remaining $n-1$ people can be placed in the other seats in $(n-1)!$ ways, and each circular seating corresponds to exactly one such placement. So the count is $(n-1)!$, not $n!$; the factor $n$ disappears because rotations are identified.

If reflections are also identified (a necklace turned over counts as the same), divide by 2 further when $n\ge 3$ and the arrangement has no symmetry of its own. For bead necklaces with two colors and rotations only, Burnside's lemma averages the number of fixed colorings over the rotation group. It is a useful upgrade once the basic ideas feel comfortable, and it appears in the problems below.

A common mistake is to treat a block as a single person without counting its internal orders. For two people who must sit next to each other around a table of $n$ people, glue them into one unit: there are $n-1$ units around the table, giving $(n-2)!$ arrangements of units, and each unit has $2$ internal orders. The answer is $2\,(n-2)!$, which is worth checking on a small case.

Testing a formula on a small case is the fastest check. For three distinct letters around a round table with rotations identified there are $2!=2$ arrangements, while in a row there are $3!=6$. For the word BOO the formula gives $3!/2!=3$, matching the list above. Whenever a formula feels right, list the answer for two or three objects and compare.

• Multinomial: $\frac{n!}{n_1!\,n_2!\cdots n_m!}$ distinct arrangements of a multiset
• Circular arrangements of $n$ distinct objects: $(n-1)!$ when rotations are identified
• Adjacent block of two among $n$ people around a table: $2\,(n-2)!$

• Using $n!$ when some letters repeat, which overcounts by the factorial of each repeat count.
• Forgetting to fix a reference seat, which counts each circular seating $n$ times.

4.Complementary counting

Many problems ask for 'at least one' or 'not all'. Counting such a condition directly often forces a messy union of overlapping cases. The complementary principle says that $\#(\text{desired})=\#(\text{all})-\#(\text{undesired})$, where the undesired set is usually a single, clean condition.

Why this helps: 'at least one 7 among five digits' has several overlapping cases (exactly one 7, exactly two 7s, and so on). Its complement, 'no 7 at all', is one case: each digit has 9 choices, giving $9^5$ strings. Subtracting from the total $10^5$ leaves $10^5-9^5$ strings with at least one 7.

Use complements when the undesired condition is restrictive: 'no digit repeats', 'no vowel appears', 'no two adjacent letters are equal', 'every letter appears'. If the desired condition is the restrictive one, count it directly instead.

Complements combine with other tools. In 'at least two of each' problems, the bad set may be several small events. Subtract the cases violating each condition, then add back the overlaps, which is inclusion-exclusion (Concept 5). The cleanest decomposition is one where the bad cases are disjoint or nested.

Complement traps: using the wrong total (for instance, a total that excludes leading zeros while the complement includes them); taking the complement of 'at least one' as 'at most one' rather than 'none'; and subtracting overlapping bad events twice. Each is a symptom of not fixing one universe before counting.

A sanity check is built in. A complementary count must lie between $0$ and the total. If the subtraction gives a negative number or a number larger than the total, the bad set was mis-specified. Complementary counting is the identity $|A|+|A^c|=|U|$ applied on one fixed universe $U$, and it should be the first tool tried whenever the condition has the form 'at least'.

• $|\text{desired}|=|\text{all}|-|\text{undesired}|$ on a single fixed universe
• 'At least one' has complement 'none'; 'at least two' has complement 'zero or one'

• Taking the complement of 'at least one' as 'at most one'.
• Using a total that is not the universe the bad set lives in.

5.Inclusion-exclusion

For two sets, $|A\cup B|=|A|+|B|-|A\cap B|$. The reason is that adding $|A|$ and $|B|$ counts every element of $A\cap B$ twice, so one copy must be removed. Picture two overlapping circles: the sum double-counts the lens in the middle.

For three sets, $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$. Check element by element: an element in exactly one set is counted once. An element in exactly two sets is counted $2-1=1$ times. An element in all three is counted $3-3+1=1$ time. The alternating signs are forced, because each element must be counted exactly once.

General principle: $\left|\bigcup_{i=1}^{n} A_i\right|=\sum_{S\neq\varnothing}(-1)^{|S|+1}\left|\bigcap_{i\in S} A_i\right|$. For an element lying in exactly $m\ge 1$ of the sets, the alternating contributions form $\sum_{j=1}^{m}(-1)^{j+1}\binom{m}{j}=1$, which follows from the binomial theorem applied to $(1-1)^m=0$.

Divisibility problems are the standard application. The number of multiples of $d$ in $\{1,\dots,N\}$ is $\lfloor N/d\rfloor$, and the multiples of both $a$ and $b$ are the multiples of $\operatorname{lcm}(a,b)$. So the count of integers divisible by 3 or 5 is $\lfloor N/3\rfloor+\lfloor N/5\rfloor-\lfloor N/15\rfloor$. The same idea works for three divisors, where the triple intersection term matters.

Exactly-one counts: the number of elements in exactly one of $A$ and $B$ equals $|A|+|B|-2|A\cap B|$. This is the symmetric difference. When a problem says 'or, but not both', use this form rather than the union formula.

Traps: stopping after the pairwise intersections and forgetting the triple term; using the formula when some intersections are empty but not checking; confusing 'at least one' with 'exactly one'. A check is that the answer must not exceed the sum of the set sizes, and must not be smaller than the largest single set.

• $|A\cup B|=|A|+|B|-|A\cap B|$
• $|A\cup B\cup C|=\sum|A_i|-\sum|A_i\cap A_j|+|A\cap B\cap C|$
• Multiples of $d$ in $\{1,\dots,N\}$: $\lfloor N/d\rfloor$; exactly one of $A,B$: $|A|+|B|-2|A\cap B|$

• Omitting the triple intersection term when there are three sets.
• Using $\operatorname{gcd}$ where $\operatorname{lcm}$ is needed for the overlap of divisibility conditions.

6.Stars and bars

Distributing identical objects into distinct boxes is among the most reusable counts. The number of nonnegative integer solutions to $x_1+\cdots+x_k=n$ equals $\binom{n+k-1}{k-1}$. Picture $n$ identical stars in a row, with $k-1$ bars placed among the $n+k-1$ positions. Each arrangement of stars and bars corresponds to exactly one solution: the stars between consecutive bars give the values $x_i$.

The count follows from choosing which $k-1$ of the $n+k-1$ positions hold bars, giving $\binom{n+k-1}{k-1}$. For example, $x+y+z=10$ in nonnegative integers has $\binom{12}{2}=66$ solutions, which is verified by brute force in the example below.

Positive solutions: if every $x_i\ge 1$, substitute $x_i=y_i+1$ with $y_i\ge 0$. Then $\sum y_i=n-k$, so the count is $\binom{n-1}{k-1}$. Equivalently, place $k-1$ bars into the $n-1$ gaps between the $n$ stars, with at most one bar per gap and none at the ends.

Upper bounds break the clean formula. Use inclusion-exclusion: count all solutions, subtract those where some $x_i$ exceeds its bound (shift that variable by the bound and recount), then add back the cases where two variables exceed their bounds, and so on. When the total is small, most terms vanish, which is why this method is efficient in contest problems.

Recognizing the setting: 'distribute 12 identical candies among 4 children', 'nonnegative integer solutions', and 'choose $k$ items with repetition from $n$ types'. For the last, the count is $\binom{n+k-1}{k}$, which equals $\binom{n+k-1}{k-1}$ by the symmetry of binomial coefficients.

Off-by-one errors are the most common mistake. Shifting one variable by 1 changes the total $n$ by 1, and the bound you subtract must match the shift exactly. Writing out the substitution explicitly, with its new total, prevents nearly all such errors.

• Nonnegative solutions of $x_1+\cdots+x_k=n$: $\binom{n+k-1}{k-1}$
• Positive solutions of $x_1+\cdots+x_k=n$: $\binom{n-1}{k-1}$
• Upper bounds: shift the violating variable and subtract via inclusion-exclusion

• Using the positive formula when zeros are allowed, or the nonnegative formula when each variable must be at least 1.
• Forgetting to shift the total after substituting $x_i=y_i+c$.

7.Bijections and symmetry

A bijection proves two sets have equal size without counting either one. Build a one-to-one correspondence between a set you cannot count directly and a set you can. A classic example: subsets of $\{1,\dots,n\}$ correspond to binary strings of length $n$ (write 1 when the element is included). The product rule on binary strings then gives $2^n$ subsets.

A shifting bijection: $k$-subsets of $\{1,\dots,n\}$ with no two consecutive elements are in one-to-one correspondence with $k$-subsets of $\{1,\dots,n-k+1\}$. Given $a_1<\cdots<a_k$ with $a_{i+1}-a_i\ge 2$, define $b_i=a_i-(i-1)$. Then $b_{i+1}-b_i=a_{i+1}-a_i-1\ge 1$, so the $b_i$ are strictly increasing, and they lie in $\{1,\dots,n-k+1\}$. The inverse map adds $i-1$ back to each $b_i$. So the count is $\binom{n-k+1}{k}$.

Symmetry: when a process pairs objects up two-to-one, halve the count. Ten people shake hands pairwise. Ordered pairs $(a,b)$ with $a\neq b$ number $10\cdot 9=90$, but each handshake appears as two ordered pairs, so there are $45$ handshakes, which matches $\binom{10}{2}$.

Symmetry also reduces casework. If a condition is invariant under a relabeling (swap two colors, reflect a board, rotate a necklace), count one representative case and multiply by the number of images. Be careful with objects fixed by the symmetry, which appear once rather than in pairs. This is the logic behind Burnside's lemma, which averages over the symmetry group.

The best bijection changes a constraint you cannot count into one you can. Gaps between chosen elements become spacing, sums become stars and bars, and paths that cross a forbidden boundary can be reflected to paths with a different endpoint. Each time, ask whether the transformed object is easier to count and whether the map can be reversed.

Traps: claiming a bijection without checking it is invertible; halving a two-to-one count when some objects are fixed by the pairing; and applying a symmetry argument when the condition is not actually symmetric. A small-case check, such as $n=4$, catches all three.

• Subsets of $\{1,\dots,n\}$ $\leftrightarrow$ binary strings of length $n$, so there are $2^n$ subsets
• $k$-subsets of $\{1,\dots,n\}$ with no two consecutive elements: $\binom{n-k+1}{k}$
• Two-to-one pairings: halve the count, unless some object is fixed by the pairing

• Claiming a bijection without checking that the map is reversible.
• Halving a symmetric count when some configuration is fixed by the symmetry.

8.Recursion and states

A recursion expresses the count for size $n$ in terms of counts for smaller sizes. To build one, look at the last decision, or the first. For binary strings of length $n$ with no two consecutive 1s, split by the last symbol. If it is 0, the first $n-1$ symbols form any valid string. If it is 1, the symbol before it must be 0, and the first $n-2$ symbols form any valid string.

So $a_n=a_{n-1}+a_{n-2}$, with $a_1=2$ and $a_2=3$. The values run 2, 3, 5, 8, 13, 21, 34, 55, and so on. This is the Fibonacci sequence shifted: $a_n=F_{n+2}$ where $F_1=F_2=1$. For $n=8$ the answer is $a_8=55$.

States: when the constraint depends on the previous symbol, track a small set of states, such as 'last symbol was A' and 'last symbol was B', and write a transfer rule for how counts move between states. Each step is a linear map on the state counts. This turns a long-length problem into a short table, and it is the same idea as taking a power of a transfer matrix.

Step recursions: if a climber takes steps of size 1, 2, or 3, the last step is one of these three, so $f(n)=f(n-1)+f(n-2)+f(n-3)$, with base cases $f(0)=1$, $f(1)=1$, and $f(2)=2$. Recursions with several terms need careful base cases, and most errors live there. Compute the first few values by listing to confirm the base cases.

Spacing recursions for subsets: if chosen elements must differ by at least 3, the largest element is either absent (leaving $\{1,\dots,n-1\}$) or present (forbidding $n-1$ and $n-2$, leaving $\{1,\dots,n-3\}$). This gives $a_n=a_{n-1}+a_{n-3}$ with base cases $a_0=1$, $a_1=2$, $a_2=3$. The same case analysis works for any forbidden gap.

A table of values is as much a brute force as a computer's enumeration, and it is usually the fastest reliable method. Write $a_0,a_1,\dots$ in a row, double-check two or three values by listing, and then extend. Once a recursion is established, look for a closed form only if the problem requires a large index.

• Binary strings of length $n$ with no two adjacent 1s: $F_{n+2}$, with $F_1=F_2=1$
• Fibonacci recursion: $F_{n+1}=F_n+F_{n-1}$
• Steps of size 1, 2, 3: $f(n)=f(n-1)+f(n-2)+f(n-3)$

• Wrong base cases, which shift every later value.
• Forgetting that the 'last symbol' split must account for both possibilities.

9.Binomial identities and Pascal's triangle

Pascal's triangle lists $\binom{n}{k}$. The rule $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ can be proved by counting. Fix a particular element $X$ of an $n$-set. A $k$-subset either contains $X$ (then choose the other $k-1$ from $n-1$ elements) or it does not (then choose all $k$ from the other $n-1$ elements). Adding the two cases gives the identity.

Row sums: $\sum_{k=0}^{n}\binom{n}{k}=2^n$, because each subset of an $n$-set is counted once in the row by its size. Alternating row sums vanish: $\sum_{k}(-1)^k\binom{n}{k}=0$ for $n\ge 1$, since the even-size and odd-size subsets are equinumerous. Both follow from expanding $(1+x)^n$ and substituting $x=1$ or $x=-1$.

Parity sums: for $n\ge 1$, $\sum_{k\text{ even}}\binom{n}{k}=2^{n-1}$, because the even-size and odd-size subsets split the $2^n$ subsets evenly. For $n=10$ this is $512$, a value verified by brute force in the example below.

Hockey stick: $\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}$. Derive it by counting $(r+1)$-subsets of $\{0,1,\dots,n\}$ according to their largest element $k$. Each largest element $k$ contributes $\binom{k}{r}$ subsets, and the total is a telescoping application of Pascal's rule.

Vandermonde: $\sum_{k}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$. Count $r$-subsets of a set of $m+n$ elements split into a group of $m$ and a group of $n$, by how many elements fall in the first group. Such identities appear naturally in committee problems (Concept 10).

Binomial theorem: $(1+x)^n=\sum_k\binom{n}{k}x^k$. Substituting $x=1$, $x=-1$, or comparing coefficients gives the row sums and alternating sums above. When a problem asks for a sum of binomial coefficients, look first for a counting interpretation or a substitution before expanding by hand.

• Pascal: $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$
• $\sum_{k=0}^{n}\binom{n}{k}=2^n$ and $\sum_{k\text{ even}}\binom{n}{k}=2^{n-1}$ for $n\ge 1$
• Hockey stick: $\sum_{k=r}^{n}\binom{k}{r}=\binom{n+1}{r+1}$; Vandermonde: $\sum_k\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$

• Summing all binomial coefficients when the problem only asks for the even-indexed ones.
• Misapplying Pascal's rule by mixing up $k-1$ and $k$ in the indices.

10.Committees and casework

Committee problems often impose conditions such as 'exactly two women', 'at least one from each group', or 'the captain must be included'. The standard method is to split the count into cases by a key quantity, usually the number of members from one group. Count each case as a product of combinations, then add. The sum is valid because the cases are disjoint: each committee has exactly one value of the key quantity.

Example: a committee of 4 chosen from 5 men and 4 women with at least two women. The cases are exactly two women, $\binom{4}{2}\binom{5}{2}=60$; exactly three women, $\binom{4}{3}\binom{5}{1}=20$; and exactly four women, $\binom{4}{4}=1$. The total is $81$. Splitting by the number of men instead gives the same total, as it must.

Fixed members: when a particular person must be included, remove that person from the pool and reduce the committee size by one. When a particular person must be excluded, remove them from the pool. These reductions are often the simplest route, and they combine well with complementary counting when a condition is stated in the negative.

Choose the case variable carefully. The best variable is the one whose possible values give a small number of disjoint cases that each factor nicely. If the condition says 'more men than women' on a committee of five, the cases are $m=3,4,5$, which is much shorter than the full range of values.

Casework also handles teams and roles. For unlabeled groups of equal size, divide by the number of ways to permute the groups, because each partition is produced once per ordering of its groups. For labeled groups, such as rooms or distinct roles, multiply instead. Mixing these two situations is the most common error in partition problems.

Traps: double counting a committee that falls into two cases (the cases must be disjoint); forgetting to exclude bad cases in an 'at least' problem; and treating unlabeled groups as labeled. Before adding cases, check that they cover all possibilities and nothing else.

• Casework on a key variable: a sum over disjoint cases, each a product of combinations
• Fixed member: remove from the pool and reduce the committee size by one
• Unlabeled groups of equal size: divide by the number of orderings of the groups

• Counting a committee in two different cases, which double counts it.
• Dividing by the number of group orderings when the groups are labeled.

Example 1: Ordered codes without repeats

A three-letter code is made from the letters A, B, C, D, E, with no letter used twice. How many codes are possible?

Example 2: Arrangements of MOON

How many distinct four-letter arrangements can be made using each letter of the word MOON exactly once?

Example 3: Seating with a restricted seat

Four people, Alice among them, are to be seated in a row of four chairs. Alice may not sit in either end chair. How many seatings are possible?

Example 4: Committees with at least two women

A 5-person committee is chosen from 6 men and 4 women. The committee must contain at least 2 women. How many committees are possible?

Example 5: Positive entries with an upper bound

How many ordered quadruples $(x,y,z,w)$ of positive integers satisfy $x+y+z+w=12$ with every entry at most 5?

Example 6: Paths that stay below the diagonal

A lattice path from $(0,0)$ to $(6,6)$ uses unit steps right $(1,0)$ and up $(0,1)$. How many such paths never rise above the diagonal, so that $y\le x$ at every point of the path?