Chapter 8 introduced the fundamental tools of combinatorics: permutations, combinations, factorials, and counting-based probability. Those tools answer many questions precisely and efficiently. But some counting problems resist these approaches. They involve distributions, repetition, structural constraints, or patterns that repeat in a predictable way. Chapter 9 extends the counting toolkit into these more sophisticated situations.

This chapter develops the pigeonhole principle, which proves that certain arrangements must exist even without constructing them; combinations with repetition and the stars and bars method, which count selections from categories when items may be reused; integer solutions to equations, a powerful reframing of distribution problems; introductory partition theory, which studies the ways to break a number into parts; and recurrence relations, which define counting sequences by their own patterns.

The chapter closes with combinatorial identities and combinatorial proofs, which are a distinctive kind of argument that explains why counting formulas are true rather than simply verifying them algebraically.

Advanced counting is not about memorizing more formulas. It is about understanding the structure of a problem clearly enough to choose the right representation. The strategies in this chapter will prepare students for algorithm analysis, data structures, probability theory, cryptography, and theoretical computer science.

Counting appears throughout mathematics and computer science, but the problems that arise in real applications are rarely as clean as "how many ways can five students sit in five chairs?" More commonly, the question involves resources distributed among categories, patterns in sequences, or overlapping constraints.

The techniques in this chapter appear in algorithm analysis, where recurrence relations describe how the running time of a recursive program grows; in database design, where counting distinct records with repeated categories matters for storage and performance; in cryptography, where the number of valid key distributions affects security analysis; in scheduling and resource allocation, where distributing identical tasks among workers is a combinations-with-repetition problem; and in data science, where feature selection and partitioning of data sets rely on advanced combinatorial reasoning.

Understanding these methods deeply — not as formulas to apply, but as ideas to think with — gives students a foundation for nearly every quantitative field.

The counting methods from Chapters 7 and 8 answer a wide range of questions. The multiplication principle counts sequential independent choices. Permutations count ordered arrangements. Combinations count unordered selections. Inclusion-exclusion counts overlapping collections.

But some counting problems have structures these tools alone cannot handle cleanly. Consider four examples that illustrate the kinds of problems this chapter is built to solve.

Each of these problem types requires a different extension of the counting toolkit. The first is addressed by combinations with repetition and the stars and bars method (Sections 9.4–9.6). The second is addressed by the pigeonhole principle (Sections 9.2–9.3). The third is addressed by recurrence relations (Sections 9.8–9.10). The fourth is addressed by combinatorial identities and combinatorial proofs (Sections 9.11–9.12).

Section by section, this chapter builds these extensions. By the end, you will have a broader and more flexible view of what counting can do — and, just as importantly, a clearer sense of when each tool applies.

Imagine twelve pigeons returning to a coop that has only eleven holes. No matter how the pigeons arrange themselves, at least one hole must contain at least two pigeons. This observation — obvious in the physical setting — becomes a powerful mathematical tool when stated precisely.

The principle does not tell us which container holds more than one object. It does not tell us how many objects that container holds. It only guarantees that the overcrowded situation must occur. This makes the pigeonhole principle an existence theorem — it proves that something exists without constructing it.

To use the pigeonhole principle, identify the objects being distributed, the containers receiving them, and explain why the number of objects exceeds the number of containers. Then conclude that some container holds at least two objects.

The basic pigeonhole principle guarantees at least one container holds at least two objects. The generalized version tells us more precisely how full at least one container must be.

The symbol \(\lceil x \rceil\) denotes the ceiling of \(x\) — the smallest integer greater than or equal to \(x\). For example, \(\lceil 7/3 \rceil = \lceil 2.33\ldots \rceil = 3\).

Suppose 10 objects are placed in 3 containers. Is it possible that every container holds at most 3 objects? If each holds at most 3, the total is at most \(3 \times 3 = 9\) — but there are 10 objects. Contradiction. So at least one container must hold at least 4. And indeed \(\lceil 10/3 \rceil = \lceil 3.33\ldots \rceil = 4\).

The ceiling function captures the smallest integer large enough to force the overcrowding.

In Chapter 8, a combination counted the number of ways to choose \(r\) objects from \(n\) distinct objects without replacement. Each object could be chosen at most once, and order did not matter. The formula was:

Now suppose repetition is allowed: each object may be selected more than once, and order still does not matter. This is the problem of combinations with repetition, also called multiset coefficients.

For example, suppose a café sells coffee, tea, and juice. A customer orders 4 drinks. Order does not matter; only the count of each type matters. How many selections are possible? The customer might order 4 coffees, or 2 coffees and 2 teas, or 1 of each plus 1 extra coffee, and so on. This is a selection with repetition from 3 categories.

This formula will be derived carefully in Section 9.5 using stars and bars. For now, note how it works. For the café example, \(n = 3\) categories and \(r = 4\) drinks:

The formula \(\binom{n+r-1}{r}\) for combinations with repetition might seem to appear from nowhere. The stars and bars method gives a concrete picture of where it comes from.

Suppose we want to distribute \(r\) identical objects into \(n\) categories. Represent each object as a star (\(\star\)) and use bars (\(\mid\)) to separate the categories. For \(n\) categories, we need exactly \(n-1\) bars to create \(n\) groups.

The total number of symbols is \(r\) stars plus \(n-1\) bars, giving \(r + n - 1\) symbols in total. A valid arrangement corresponds to choosing which \(r\) positions among the \(r+n-1\) total positions are stars (equivalently, which \(n-1\) positions are bars). This gives exactly \(\binom{r+n-1}{r}\) arrangements.

Distribute 4 drinks among 3 categories: coffee (C), tea (T), juice (J). Each arrangement of 4 stars and 2 bars (\(n-1=2\)) represents a valid order.

Each of the 15 distinct arrangements of 4 stars and 2 bars corresponds to exactly one drink selection. The number of arrangements is the number of ways to choose which 4 of the 6 positions are stars: \(\binom{6}{4} = 15\), which matches the formula from Section 9.4.

Many distribution problems can be reframed as questions about integer solutions to equations. This reframing connects the stars and bars method to algebra in a useful way.

A partition of a positive integer \(n\) is a way of writing \(n\) as an unordered sum of positive integers. The summands are called parts.

For example, the partitions of 4 are: \(4\); \(3+1\); \(2+2\); \(2+1+1\); \(1+1+1+1\). So there are 5 partitions of 4. This count is written \(p(4)=5\).

Partitions differ from the integer-solution problems above in one important way: the order of the parts does not matter. The partition \(2+1+1\) and the partition \(1+2+1\) are the same partition.

The partition function \(p(n)\) grows, but without a simple closed-form formula. Partition theory is a deep area of mathematics. At this level, students should be able to list partitions of small integers systematically.

To list all partitions of \(n\): start with the partition \(n\) (only one part equal to \(n\)); decrease the largest part and distribute the remainder into parts no larger than the current largest part; continue until you reach \(1+1+\cdots+1\) (\(n\) ones).

A recurrence relation defines each term of a sequence using earlier terms. Rather than giving a direct formula for the \(n\)-th term, a recurrence describes how each term is built from its predecessors.

The most important requirement for a recurrence is a base case (or several base cases) that provides the starting values from which all subsequent terms are computed.

The Fibonacci sequence is defined by:

The first several terms are: \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\). Each term is the sum of the two before it. This is a recurrence relation.

Many counting problems have recursive structure: the count for size \(n\) naturally depends on the count for smaller sizes. When this happens, writing a recurrence relation captures the structure of the problem.

For example, let \(a_n\) be the number of binary strings of length \(n\) that do not contain two consecutive 1s. Then \(a_1 = 2\) (strings: 0, 1) and \(a_2 = 3\) (strings: 00, 01, 10). For \(n \geq 3\): a string of length \(n\) either starts with 0, followed by any valid string of length \(n-1\), or starts with 10, followed by any valid string of length \(n-2\). So \(a_n = a_{n-1} + a_{n-2}\) — exactly the Fibonacci recurrence.

The simplest technique for solving a recurrence is unwinding (also called iteration or back-substitution): repeatedly apply the recurrence rule, replacing each term with its definition, until a pattern appears.

For recurrences of the form \(a_n = c_1 a_{n-1} + c_2 a_{n-2}\) (second-order homogeneous linear recurrences), there is a systematic method using characteristic equations.

Assume a solution of the form \(a_n = r^n\). Substituting:

Dividing by \(r^{n-2}\):

This is the characteristic equation. Solve for \(r\). If the two roots \(r_1\) and \(r_2\) are distinct, the general solution is:

where \(A\) and \(B\) are determined by the base cases.

Many important algorithms solve a problem of size \(n\) by splitting the input into smaller pieces, solving each piece recursively, and combining the results. The running time of such an algorithm satisfies a divide-and-conquer recurrence.

A common divide-and-conquer recurrence has the form:

where \(a\) = number of subproblems, \(b\) = factor by which the input size shrinks, and \(f(n)\) = time to split and combine.

This chapter introduces the structure of such recurrences without formal asymptotic analysis. The key insight is that the recurrence captures how much work is done at each level of the recursion.