第 5 章 · 22 分钟

Reducing the size: recurrences and generating functions

Turning 'what to split on' into something you can run.

概念地图

Recurrence

Split on the last step and reduce to a smaller instance.

深色为本章概念，浅色为其他章

陪练模式

不想只是读？让它带你走一遍。

导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。

对话只存在本机

Locus01

延伸阅读

Fibonacci · thirteenth century · the rabbit recurrence

Wrote $F_n = F_{n-1} + F_{n-2}$, among the earliest reductions of a counting problem to smaller instances. He argued against enumerating month by month; the cost is that the recurrence gives an algorithm and no closed form.

Foundational

de Moivre and Euler · eighteenth century · generating functions

Packed sequences into power series so that a recurrence becomes an equation about a function, from which a closed form can be extracted. They argued against computing term by term; the cost is that convergence was largely ignored early on, until the formal power series view settled the matter.

Turn

The formal power series view · twentieth century

Pointed out that generating functions in combinatorics need not converge: they are formal objects on which addition, multiplication and differentiation are defined. A direct correction to 'convergence must come first', and what makes this chapter's second mechanism legitimate.

Revision

Brualdi · the chapters on recurrences and generating functions

The subject of this course. The textbook gives the standard methods for solving recurrences; this chapter says a generating function is not a new tool but chapter 3's act — 'what to split on' — made mechanical.

Subject of this course

机制02

Split on the last step

Chapter 3's act was to fix on a particular element. In problems carrying an order, the most useful 'particular element' is usually the last step: climbing to stair $n$ , the last stride was either one step or two, the two classes are disjoint and exhaust the whole, and the addition principle hands you a recurrence. The first mechanism of this chapter is that one sentence: change what you split on and you change the recurrence.

机制A counting problem of size n, through being split on how the last step was taken, reduces to several smaller instances of itself.

可迁移性测试

Move it to schedule estimation: an n-day plan, split by what happens on the last day, becomes a set of n−1-day or n−2-day plans of the same kind. The isomorphism breaks in that real projects may have resource conflicts between the classes, while here they must be disjoint and exhaustive.

机制03

Pack the sequence into a series

Having a recurrence you still have to solve it. Write the whole sequence as a generating function and the recurrence becomes an algebraic equation in that function; solve and expand and the closed form falls out. Its value is not that it is faster but that it replaces an act needing inspiration — finding the closed form — with a procedure you can follow.

机制A recurrence, through the sequence being packed into a power series, becomes an algebraic equation you can solve step by step.

可迁移性测试

Move it to signal processing: after a transform, convolution becomes multiplication and the awkward operation becomes an easy one. The isomorphism breaks in that signal processing must worry about convergence, while combinatorial power series are formal — a notation for a sequence and nothing more.

Derivation04

From recurrence to closed form: the Catalan case

What is being proved is the Catalan recurrence and its closed form, with each step's class marked.

Let Cn​ be the number of balanced bracket strings of length 2n, with C0​=1
A hypothesis. The initial value must be stipulated separately; the recurrence does not supply it.
Every non-empty balanced string factors uniquely as (A)B with A, B balanced
A hypothesis, and the whole content of the recurrence: uniqueness of the factorisation is what makes it neither over- nor under-count.
Generating functions are taken formally, with no discussion of convergence
A hypothesis. It is what makes the algebra below legitimate without any analytic conditions.

推导 · 0 / 4

裂缝05

The boundary of this chapter's claims

争议地形06

本书主张

Recurrences and generating functions are the standard pipeline: split some way to get a recurrence, then use a generating function to extract the closed form.

另一种看法

The bijective line holds that where a closed form can be obtained by an explicit bijection, that bijection is worth more than the generating-function derivation — the reflection proof of the Catalan numbers gives

(n 2 n) - (n + 1 2 n)

directly and explains where the factor

\frac{1}{n + 1}

comes from.

分歧扎在

The disagreement is rooted in whether solving or explaining comes first, not in the mathematics. Both routes give the same closed form; at issue is which is more modifiable on a variant problem.

什么证据能裁决

What would settle it is performance on variants: have two groups reach the Catalan numbers by generating functions and by bijection respectively, then give a variant (restricting how often some bracket appears) and compare solve rates. A markedly higher rate in the bijective group supports its claim.

The evidence points to 'it depends on the type of variant': linear constraints suit generating functions, structural constraints suit bijections. What is missing is a criterion for classifying the variant in advance.

Boundary and counterexample07

The 'split on the last step' commitment as a testable specification

The modelling commitment under test: a real recursive structure has a unique decomposition, so splitting on the last step neither over- nor under-counts.

Hypothesis dropped: the decomposition is unique
The whole ground for the recurrence being exact; without it the same object is counted several times.
The counterexample: splitting a workflow by 'its last stage' where some workflows have two ways of identifying the last stage
The same workflow then enters two classes and the count overshoots.
The observable: the classification produced by independent executions of the decomposition rule on the same set of objects
The same rule, the same objects, executed independently.
What counts against it: the share of objects assigned to different classes exceeds a pre-registered threshold
The threshold is fixed in advance on how blurred the objects' boundaries are.
Pre-registered failure condition: the share above threshold, or the recurrence's total differing from direct enumeration beyond the threshold
Either counts as the commitment failing.

推导 · 0 / 3

接口08

Which slot it hangs on

挂在哪个槽位The conclusion you already hold is probably 'break a complex problem into smaller ones' — a judgement about divide and conquer. This chapter goes at the condition it leaves out.

Does this chapter (a) replace 'break it into smaller problems', or (b) constrain it: the split must be unique for every object, or the sub-answers overlap when added?

慢变量Register two slow variables: how many of your recursive decompositions have had uniqueness checked, and how many have been verified against small-scale enumeration. Look at the second first.

小结09

本章小结

01A recurrence comes from splitting on the last step; change what you split on and you change the recurrence.

02A recurrence constrains only neighbouring terms, so initial values must be stipulated separately.

03A generating function turns the recurrence into an algebraic equation, replacing inspiration with procedure.

04Combinatorial generating functions are formal power series and need no discussion of convergence.

05The only step carrying observational risk is that a real decomposition is unique, not any closed form.

提取练习 · 合上书，先自己答一遍。

?Is the Catalan closed form (a) obtained from the recurrence plus algebra or (b) a modelling commitment about reality?

?Do different initial values giving different Fibonacci sequences show that the recurrence (a) fails or (b) constrains only neighbouring terms?

Forced choice10

A · Identify the mechanism

Which of these is a mechanism?

二选一

Forced choice11

D · Judge the interface

Which one hangs on a slot in your existing structure?

二选一

读到这里，把它记为已读。